Insertion, Searching, and Deletion in AVL trees containing a parent node pointer

Shreya Deep
Last Updated: May 13, 2022

Introduction

Adelson-Velskii and Landis (AVL) is a type of Binary Search Tree. In the AVL tree, the difference between the height of the left and right subtree is at most 1. This difference is known as the balance factor.

This article will describe operations like insertion, searching, and deletion in AVL trees containing a parent node pointer. The prerequisite to understanding this article is the knowledge of AVL trees and the procedure to do basic operations like insertion, searching, and deletion in them. This article will use methods quite similar to the methods given in the above reference links.

Difference between regular AVL tree and AVL tree containing a parent node pointer

In this article, the AVL tree nodes are different from the normal AVL tree nodes. The difference is that a node has four characteristics in a normal AVL tree node. These are:

  • Data
  • Pointer to the left node
  • Pointer to the right node
  • Height of the subtree root at this node

But, in our problem, the nodes also have one more feature, which is the pointer to the parent node. As we know, each tree node has a parent. So, here, a node will also contain the pointer to its parent node. So here, the nodes will have five characteristics. These are:

  • Data
  • Pointer to the left node
  • Pointer to the right node
  • Height of the subtree root at this node
  • Pointer to the parent of the node

Modification in an AVL tree

When we do some operations in a tree, its structure changes. Since the AVL properties should always be maintained, we need to modify the tree to follow those properties. This is done using rotations. To read more about rotations in AVL trees, refer to this

An insertion or deletion involves adding or deleting a single node. This can only increase or decrease the height of a subtree by 1. After every operation, the AVL tree can be restored by using single or double rotation. Whereas in searching, the tree is not changed at all. We only need to search the element in the tree. So no rotations are required here.

Representation of AVL tree with parent node pointer

An AVL Tree with a parent node pointer is made up of nodes where each node contains - 

  • Data
  • Pointer to left subtree
  • Pointer to right subtree
  • Balance factor of the subtree rooted at this node
  • Pointer to the parent node

The structure of each node is defined as:

class AVL_Node{
public:
    int key;
    AVL_Node *left;
    AVL_Node *right;
    int height;
    AVL_Node *parent;
};

Algorithm for insertion in AVL trees with parent pointer

The insertion algorithm in AVL trees containing a parent node pointer is the same as for regular AVL trees. The only difference here is that, since we also have a parent pointer in each node, when we insert a node into the tree and the structure changes, we also have to update the parent pointer of the nodes with every insertion and rotation so that the correct parent pointers are stored. But why do we need to update the parent?

For understanding this, let's look at an example.

Suppose we have this tree:

The parent of each node is:

NodeParent
6NULL
43
106
13
36
910

 

Now, if we need to insert a node with a data value equal to 7. The insertion will be like this:

The parent of each node is:

NodeParent
6NULL
43
106
13
36
910
79

 

You can notice that, after the insertion is done, the balance factor of the node with value ten has become 2. And this violates the AVL property, as each node should only have balance factors equal 1, -1, or 0. So, it's clear that we need to do a rotation here. And the rotation will occur from the node with value 9 to the node with value 10. After the rotation, the tree will look like this:

Since we have done rotation, we also need to update the parents because the parent of the node with the value 9 is not ten anymore. Similarly, the node's parent with the value 10 is not six anymore. Therefore, while rotating, we also need to take care of the parent pointer and update it accordingly. 

After updating, the parent of each node is:

NodeParent
6NULL
43
109
13
36
96
79

Thus, the steps of the algorithm are:

  • Insert the node using the normal AVL tree insertion
  • After insertion, find the first node which violates the AVL property. The first node whose balance factor is not 1, -1, or 0. 
  • Perform the required rotation.
  • While doing the rotation, update the parent of the nodes which are getting shifted, i.e., the root, left child of the root in case of left rotation, the right child in case of right rotation, and the parent of the root. Also, update their heights after the rotation.
  • Update the height of the root after each insertion.
  • Print the preorder traversal of the tree.

C++ implementation

#include<bits/stdc++.h>
using namespace std;

class AVL_Node{
public:
    int key;
    AVL_Node *left;
    AVL_Node *right;
    int height;
    AVL_Node *parent;
};

/*
    Function to get the height of the tree
*/
int height(AVL_Node *N){
    if (N == NULL)
        return 0;
    return N->height;
}

/*
    Function to create a new AVL_Node 
    Adding the newly created node as leaf node
*/

AVL_Node* newAVL_Node(AVL_Node* par, int key){
    AVL_Node* node = new AVL_Node();
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    node->parent = par;
    return(node);
}

/*
    Function to update the heights
*/
void update_height(AVL_Node* root){
    if (root != NULL) {
        int val = 1;
        if (root->left != NULL)
            val = root->left->height + 1;
        if (root->right != NULL)
            val = max(
                val, root->right->height + 1);
        root->height = val;
    }
}

/*
    Function for right rotation
*/
AVL_Node *rightRotate(AVL_Node *y){
    AVL_Node *x = y->left;
    AVL_Node *T2 = x->right;

    if (x->right != NULL)
        x->right->parent = y;

/*
    Perform rotation
*/
    y->left = T2;
    x->right = y;

    x->parent = y->parent;
    y->parent = x;

    if (x->parent != NULL && y->key < x->parent->key) {
        x->parent->left = x;
    }
    else{
        if (x->parent != NULL)
            x->parent->right = x;
    }

    y = x;

/*
    Update the heights
*/    
    update_height(y->left);
    update_height(y->right);
    update_height(y);
    update_height(y->parent);

/*
    Return new root
*/
    return y;
}

/*
    Function for left rotation
*/
AVL_Node *leftRotate(AVL_Node *x){
    AVL_Node *y = x->right;
    AVL_Node *T2 = y->left;

/*
    Perform rotation
*/
    x->right = T2;

    if (y->left != NULL)
        y->left->parent = x;
    y->left = x;

    y->parent = x->parent;
    x->parent = y;

    if (y->parent != NULL && x->key < y->parent->key) {
        y->parent->left = y;
    }
    else{
        if (y->parent != NULL)
            y->parent->right = y;
    }

/*
    Update heights
*/

    update_height(x->left);
    update_height(x->right);
    update_height(x);
    update_height(x->parent);

/*
    Return new root
*/
    return y;
}

/*
    Function to find the Balance factor of Nodes
*/
int getBalance(AVL_Node *N){
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}


/*
    Function to construct a tree.
*/
AVL_Node* AVL_insert(AVL_Node *par, AVL_Node* root, int key){

/*
    Perform the normal BST insertion
*/
    if (root == NULL)
        return(newAVL_Node(par, key));

    if (key < root->key)
        root->left = AVL_insert(root, root->left, key);

    else if (key > root->key)
        root->right = AVL_insert(root, root->right, key);

    else 
        return root;

/*
    Step 1: Find the balance factor of parent\
*/
    int balance = getBalance(root);
/*
    If this Node becomes unbalanced, all four cases are:
*/
/*
    1. Left Left Case
*/
    if (balance > 1 && key < root->left->key)
        return rightRotate(root);

/*
    2. Right Right Case
*/
    if (balance < -1 && key > root->right->key)
        return leftRotate(root);

/*
    3. Left Right Case
*/
    if (balance > 1 && key > root->left->key){
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

/* 
    4. Right Left Case
*/
    if (balance < -1 && key < root->right->key){
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

/*
    Update the heights
*/
    update_height(root);

/*
    Return the (unchanged) Node pointer
*/
    return root;
}

/*
    AVL Tree Traversal 
*/
void PREORDER(AVL_Node *root){
    cout << "Node: " << root->key << ", Parent Node: ";

    if (root->parent != NULL)
        cout << root->parent->key << endl;
    else
        cout << "NULL" << endl;
    /* 
        Recur to the left subtree
    */
    if (root->left != NULL) {
        PREORDER(root->left);
    }

    /*
        Recur to the right subtree
    */
    if (root->right != NULL) {
        PREORDER(root->right);
    }
}

int main(){
    AVL_Node *root = NULL;

/*
    Constructing tree 
*/
    root = AVL_insert(NULL, root, 6);
    root = AVL_insert(NULL, root, 4);
    root = AVL_insert(NULL, root, 10);
    root = AVL_insert(NULL, root, 1);
    root = AVL_insert(NULL, root, 3);
    root = AVL_insert(NULL, root, 9);

    cout << "Preorder traversal of the above AVL tree is:\n"<<endl;
    PREORDER(root);

/*
    Insert the node 7
*/
    root = AVL_insert(NULL, root, 7);
    cout << "Preorder traversal of the above AVL tree after insertion of 7 is:\n"<<endl;
    PREORDER(root);
    return 0;
}

Output

Preorder traversal of the above AVL tree is:

Node: 6, Parent Node: NULL
Node: 3, Parent Node: 6
Node: 1, Parent Node: 3
Node: 4, Parent Node: 3
Node: 10, Parent Node: 6
Node: 9, Parent Node: 10
Preorder traversal of the above AVL tree after insertion of 7 is:

Node: 6, Parent Node: NULL
Node: 3, Parent Node: 6
Node: 1, Parent Node: 3
Node: 4, Parent Node: 3
Node: 9, Parent Node: 6
Node: 7, Parent Node: 9
Node: 10, Parent Node: 9

Complexities

Time complexity

O(logn), where n is the number of nodes in the tree

Reason: Since we're traversing till the root in the worst case to insert a new node in the AVL tree, the time complexity will be equal to the height of the tree which is equal to O(logn).

Space complexity

O(1), where n is the number of nodes

Reason: All the spaces taken are constant. Thus, space complexity is O(1). 

Algorithm for deletion in AVL trees with parent pointer

Again, the deletion operation is similar to the deletion operation in normal AVL trees. The only difference is that we have to update the parent node after each deletion and rotation operation accordingly. 

The steps of the algorithm are:

  • Search the node which needs to be deleted.
  • When the node is searched, update the child of the parent and the parent of the child of the node to be deleted. 
  • Now, since the node is deleted, check if there is any imbalance in the tree. If there is, make the proper rotation. Also, update the height of the tree.

C++ implementation

#include<bits/stdc++.h>
using namespace std;

class AVL_Node{
public:
    int key;
    AVL_Node *left;
    AVL_Node *right;
    int height;
    AVL_Node *parent;
};

/*
    Function to get the height of the tree
*/
int height(AVL_Node *N){
    if (N == NULL)
        return 0;
    return N->height;
}

/*
    Function to get a maximum of two integers
*/
int max(int a, int b){
    return (a > b)? a : b;
}

/*
    Function to create a new AVL_Node .
    Adding the newly created node as leaf node
*/
AVL_Node* newAVL_Node(AVL_Node* par, int key){
    AVL_Node* node = new AVL_Node();
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    node->parent = par;
    return(node);
}

/*
    Function to update the heights
*/
void update_height(AVL_Node* root){
    if (root != NULL) {
        int val = 1;
        if (root->left != NULL)
            val = root->left->height + 1;
        if (root->right != NULL)
            val = max(val, root->right->height + 1);
        root->height = val;
    }
}

/*
    Function for right rotation
*/
AVL_Node *rightRotate(AVL_Node *y){
    AVL_Node *x = y->left;
    AVL_Node *T2 = x->right;

    if (x->right != NULL)
        x->right->parent = y;

/*
    Perform rotation
*/
    y->left = T2;
    x->right = y;

    x->parent = y->parent;
    y->parent = x;

    if (x->parent != NULL && y->key < x->parent->key) {
        x->parent->left = x;
    }
    else{
        if (x->parent != NULL)
            x->parent->right = x;
    }

    y = x;

/*
    Update the heights
*/
    update_height(y->left);
    update_height(y->right);
    update_height(y);
    update_height(y->parent);

/*
    Return new root
*/
    return y;
}

/*
    Function for left rotation
*/
AVL_Node *leftRotate(AVL_Node *x){
    AVL_Node *y = x->right;
    AVL_Node *T2 = y->left;

/*
    Perform rotation
*/
    x->right = T2;

    if (y->left != NULL)
        y->left->parent = x;
    y->left = x;

    y->parent = x->parent;
    x->parent = y;

    if (y->parent != NULL && x->key < y->parent->key) {
        y->parent->left = y;
    }
    else{
        if (y->parent != NULL)
            y->parent->right = y;
    }

/*
    Update heights
*/
    update_height(x->left);
    update_height(x->right);
    update_height(x);
    update_height(x->parent);

/*
    Return new root
*/
    return y;
}

/*
    Function to find the Balance factor of Nodes
*/
int getBalance(AVL_Node *N){
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}


/*
    Function to construct a tree.
*/
AVL_Node* AVL_insert(AVL_Node *par, AVL_Node* root, int key){

/*
    Perform the normal BST insertion
*/
    if (root == NULL)
        return(newAVL_Node(par, key));

    if (key < root->key)
        root->left = AVL_insert(root, root->left, key);

    else if (key > root->key)
        root->right = AVL_insert(root, root->right, key);

    else 
        return root;

/*
    Step 1: Find the balance factor of parent
*/
    int balance = getBalance(root);
/*
    If this Node becomes unbalanced, all four cases are:
*/

/*
    1. Left Left Case
*/
    if (balance > 1 && key < root->left->key)
        return rightRotate(root);

/*
    2. Right Right Case
*/
    if (balance < -1 && key > root->right->key)
        return leftRotate(root);

/* 
    3. Left Right Case
*/
    if (balance > 1 && key > root->left->key){
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

/*
    4. Right Left Case
*/
    if (balance < -1 && key < root->right->key){
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

/*
    Update the heights
*/
    update_height(root);

/*
    Return the (unchanged) Node pointer
*/
    return root;
}

/*
    Function to find the AVL_Node with minimum key value
*/
AVL_Node * minValueAVL_Node(AVL_Node* node){
    AVL_Node* current = node;
    /*
        Going to the left most side
    */
    while (current->left != NULL)
        current = current->left;
    return current;
}

/*
    Function to delete an AVL_Node with the given key from the subtree 
*/
AVL_Node* AVL_delete(AVL_Node* root, int key){
/*
    Perform normal BST deletion
*/
    if (root == NULL)
        return root;
/*
    Find the node to be deleted
*/

/*
    Left Side
*/
    if ( key < root->key )
        root->left = AVL_delete(root->left, key);

/*
    Right Side
*/
    else if( key > root->key )
        root->right = AVL_delete(root->right, key);

/*
    Root Node
*/
    else{
        if( (root->left != NULL) && (root->right == NULL) ){
            AVL_Node *temp = root->left;

            if (root->parent != NULL) {
                if (root->parent->key < root->key)
                    root->parent->right = root->left;
                else
                    root->parent->left = root->left;

                /*
                    Update the height of root's parent
                */
                update_height(root->parent);
            }
            root->left->parent = root->parent;
        /*
            One child case
        */
        *root = *temp; /*
            Copy the contents of the non-empty child
        */
        free(temp);
    }
    else if((root->left == NULL) && (root->right != NULL)){
        AVL_Node *temp = root->right;
        
        if (root->parent != NULL) {
            if (root->parent->key < root->key)
                root->parent->right = root->right;
            else
                root->parent->left = root->right;

                /*
                    Update the height of root's parent
                */
            update_height(root->parent);
        }
        root->right->parent = root->parent;
        /*
            One child case
        */
        *root = *temp; /*
            Copy the contents of the non-empty child
        */
        free(temp);
    }
    /*
        No child case
    */
    else if ((root->left == NULL) && (root->right == NULL)){
        if (root->parent->key < root->key) {
            root->parent->right = NULL;
        }
        else {
            root->parent->left = NULL;
        }
        if (root->parent != NULL)
            update_height(root->parent);
        AVL_Node *temp = root;
        root = NULL;
    }
    else{
        /*
            AVL_Node with two children: Get the inorder successor (smallest in the right subtree)
        */
        AVL_Node* temp = minValueAVL_Node(root->right);
        /*
            Copy the inorder successor's data to this AVL_Node
        */
        root->key = temp->key;  
        /*
            Delete the inorder successor
        */
        root->right = AVL_delete(root->right,temp->key);
    }
}

/*
    If the tree had only one AVL_Node then return
*/
if (root == NULL)
    return root;

/*
    UPDATE HEIGHT OF THE CURRENT AVL_Node
*/
update_height(root);

/*
    GET THE BALANCE FACTOR OF THIS AVL_Node (to check whether this AVL_Node became unbalanced)
*/
int balance = getBalance(root);

/*
    If this AVL_Node becomes unbalanced, then there are 4 cases
*/

/*
    Left Left Case
*/
if (balance > 1 && getBalance(root->left) >= 0)
    return rightRotate(root);

/*
    Left Right Case
*/
if (balance > 1 && getBalance(root->left) < 0){
    root->left = leftRotate(root->left);
    return rightRotate(root);
}

/*
    Right Right Case
*/
if (balance < -1 && getBalance(root->right) <= 0)
    return leftRotate(root);

/*
    Right Left Case
*/
if (balance < -1 && getBalance(root->right) > 0){
    root->right = rightRotate(root->right);
    return leftRotate(root);
}

return root;
}

/*
    AVL Tree Traversal 
*/
void PREORDER(AVL_Node *root){
    cout << "Node: " << root->key << ", Parent Node: ";

    if (root->parent != NULL)
        cout << root->parent->key << endl;
    else
        cout << "NULL" << endl;
    /*
        Recur to the left subtree
    */
    if (root->left != NULL) {
        PREORDER(root->left);
    }

    /*
        Recur to the right subtree
    */
    if (root->right != NULL) {
        PREORDER(root->right);
    }
}

int main(){
    AVL_Node *root = NULL;

/* 
    Constructing tree 
*/

    root = AVL_insert(NULL, root, 40);
    root = AVL_insert(NULL, root, 20);
    root = AVL_insert(NULL, root, 10);
    root = AVL_insert(NULL, root, 30);
    root = AVL_insert(NULL, root, 25);
    root = AVL_insert(NULL, root, 60);
    root = AVL_insert(NULL, root, 45);
    root = AVL_insert(NULL, root, 42);
    root = AVL_insert(NULL, root, 52);
    root = AVL_insert(NULL, root, 50);
    root = AVL_insert(NULL, root, 55);
    root = AVL_insert(NULL, root, 75);
    root = AVL_insert(NULL, root, 70);
    root = AVL_insert(NULL, root, 80);
    root = AVL_insert(NULL, root, 85);

    cout << "Preorder traversal of the above AVL tree is:\n"<<endl;
    PREORDER(root);

/* 
    Delete the node 25
*/
    root = AVL_delete(root, 25);

    cout <<endl<<"Preorder traversal after"<< " deletion of 25:\n"<<endl;
    PREORDER(root);
    return 0;
}

Output

Preorder traversal of the above AVL tree is:

Node: 45, Parent Node: NULL
Node: 30, Parent Node: 45
Node: 20, Parent Node: 30
Node: 10, Parent Node: 20
Node: 25, Parent Node: 20
Node: 40, Parent Node: 30
Node: 42, Parent Node: 40
Node: 60, Parent Node: 45
Node: 52, Parent Node: 60
Node: 50, Parent Node: 52
Node: 55, Parent Node: 52
Node: 75, Parent Node: 60
Node: 70, Parent Node: 75
Node: 80, Parent Node: 75
Node: 85, Parent Node: 80

Preorder traversal after deletion of 25:

Node: 45, Parent Node: NULL
Node: 30, Parent Node: 45
Node: 20, Parent Node: 30
Node: 10, Parent Node: 20
Node: 40, Parent Node: 30
Node: 42, Parent Node: 40
Node: 60, Parent Node: 45
Node: 52, Parent Node: 60
Node: 50, Parent Node: 52
Node: 55, Parent Node: 52
Node: 75, Parent Node: 60
Node: 70, Parent Node: 75
Node: 80, Parent Node: 75
Node: 85, Parent Node: 80

Complexities

Time complexity

O(logn), where n is the number of nodes

Reason: To delete the node, we need to traverse the tree and delete the node. Traversing the tree requires O(logn) time. The above code takes O(nlogn) time because the insertion is also done here, but the time taken just for deletion is O(logn) only.

Space complexity

O(1), where n is the number of nodes

Reason: All the spaces taken are constant. Thus, space complexity is O(1).

Algorithm for searching in AVL trees with parent pointer

Searching in AVL trees with a parent pointer is the same as searching in a binary search tree. No rotation is required here since the tree doesn't change as no node is inserted or deleted. 

Steps of implementation are:

  • Start the traversal of the tree from the root. 
  • If the search value is equal to the current root, return true. Else, find the value in the right and the left subtrees.

C++ implementation

#include<bits/stdc++.h>
using namespace std;

class AVL_Node{
public:
    int key;
    AVL_Node *left;
    AVL_Node *right;
    int height;
    AVL_Node *parent;
};

/*
    Function to get the height of the tree
*/
int height(AVL_Node *N){
    if (N == NULL)
        return 0;
    return N->height;
}

/*
    Function to create a new AVL_Node 
    Adding the newly created node as leaf node
*/

AVL_Node* newAVL_Node(AVL_Node* par, int key){
    AVL_Node* node = new AVL_Node();
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    node->parent = par;
    return(node);
}

/*
    Function to update the heights
*/
void update_height(AVL_Node* root){
    if (root != NULL) {
        int val = 1;
        if (root->left != NULL)
            val = root->left->height + 1;
        if (root->right != NULL)
            val = max(
                val, root->right->height + 1);
        root->height = val;
    }
}

/*
    Function for right rotation
*/
AVL_Node *rightRotate(AVL_Node *y){
    AVL_Node *x = y->left;
    AVL_Node *T2 = x->right;

    if (x->right != NULL)
        x->right->parent = y;

/*
    Perform rotation
*/
    y->left = T2;
    x->right = y;

    x->parent = y->parent;
    y->parent = x;

    if (x->parent != NULL && y->key < x->parent->key) {
        x->parent->left = x;
    }
    else{
        if (x->parent != NULL)
            x->parent->right = x;
    }

    y = x;

/*
    Update the heights
*/    
    update_height(y->left);
    update_height(y->right);
    update_height(y);
    update_height(y->parent);

/*
    Return new root
*/
    return y;
}

/*
    Function for left rotation
*/
AVL_Node *leftRotate(AVL_Node *x){
    AVL_Node *y = x->right;
    AVL_Node *T2 = y->left;

/*
    Perform rotation
*/
    x->right = T2;

    if (y->left != NULL)
        y->left->parent = x;
    y->left = x;

    y->parent = x->parent;
    x->parent = y;

    if (y->parent != NULL && x->key < y->parent->key) {
        y->parent->left = y;
    }
    else{
        if (y->parent != NULL)
            y->parent->right = y;
    }

/*
    Update heights
*/

    update_height(x->left);
    update_height(x->right);
    update_height(x);
    update_height(x->parent);

/*
    Return new root
*/
    return y;
}

/*
    Function to find the Balance factor of Nodes
*/
int getBalance(AVL_Node *N){
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}


/*
    Function to construct a tree.
*/
AVL_Node* AVL_insert(AVL_Node *par, AVL_Node* root, int key){

/*
    Perform the normal BST insertion
*/
    if (root == NULL)
        return(newAVL_Node(par, key));

    if (key < root->key)
        root->left = AVL_insert(root, root->left, key);

    else if (key > root->key)
        root->right = AVL_insert(root, root->right, key);

    else 
        return root;

/*
    Step 1: Find the balance factor of parent\
*/
    int balance = getBalance(root);
/*
    If this Node becomes unbalanced, all four cases are:
*/
/*
    1. Left Left Case
*/
    if (balance > 1 && key < root->left->key)
        return rightRotate(root);

/*
    2. Right Right Case
*/
    if (balance < -1 && key > root->right->key)
        return leftRotate(root);

/*
    3. Left Right Case
*/
    if (balance > 1 && key > root->left->key){
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

/* 
    4. Right Left Case
*/
    if (balance < -1 && key < root->right->key){
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

/*
    Update the heights
*/
    update_height(root);

/*
    Return the (unchanged) Node pointer
*/
    return root;
}

/*
    Function that searches for a value in the AVL tree
*/
bool search(AVL_Node* root, int key){
/*
    If root is NULL, return false
*/
    if (root == NULL)
        return false;

/* 
    If the value is found, return true
*/
    else if (root->key == key)
        return true;

/*
    If the value is smaller than the root's value, go and search in the left subtree of the root.
*/
    else if (root->key > key) {
        bool found = search(root->left, key);
        return found;
    }

/*
    Otherwise, seach in the right subtree
*/
    else {
        bool found = search(root->right, key);
        return found;
    }
}

int main(){
    AVL_Node *root = NULL;

/*
    Constructing tree 
*/
    root = AVL_insert(NULL, root, 6);
    root = AVL_insert(NULL, root, 4);
    root = AVL_insert(NULL, root, 10);
    root = AVL_insert(NULL, root, 1);
    root = AVL_insert(NULL, root, 3);
    root = AVL_insert(NULL, root, 9);

    /*
        Search the node 7
    */
    if(search(root, 7)){
        cout<<"7 Found in the tree!"<<endl;
    }
    else{
        cout<<"7 not found in the tree"<<endl;
    }
    return 0;
}

Output

7 not found in the tree

Complexities

Time complexity

O(logn), where n is the number of nodes

Reason: We are traversing the tree in a dfs manner and searching for the required value. This takes O(logn) time.

Space complexity

O(1), where n is the number of nodes

Reason: All the spaces taken are constant. Thus, space complexity is O(1).

Frequently asked questions

  1. What is the maximum height of an AVL tree having n nodes?
    The maximum height of an AVL tree having n nodes is log(n).
     
  2. State two properties of AVL trees.Answer: 
    The important properties of an AVL tree are:
    → It is a binary search tree,
    → and For any node A, the height of the left subtree of A and the height of the right subtree of A differ by at most 1.
     
  3. What is the balancing condition of an AVL tree?
    The balancing condition of an AVL tree is: 
    balance(n) = abs(height(n.left)−height(n.right))

Key Takeaways

This article discussed how to perform operations like insertion, searching, and deletion in an AVL tree whose nodes also contain a parent pointer node. We hope you understood it all clearly, and now it's time to implement those by yourself. Do practice questions of AVL trees here to strengthen your understanding. You can look up this website to visualize how AVL tree insertion and deletion works and how rotations are done.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on CodeStudio now!

Happy Coding!

Was this article helpful ?
0 upvotes