AVL Tree and Balancing

The AVL Tree is a binary search tree that has an additional balance condition. This balance condition must be easy to maintain and ensures that the depth of the tree is O(logN). The simplest idea is to require that the left and right sub-trees have the same height. Recursion dictates that this idea applies to all nodes in the tree, since each node is itself a root of some sub-tree.

AVL is a height balanced tree. A height balanced tree is one in which the difference in the height of the two sub-trees for any node is less than or equal to some specified amount.

Balance Factor

Balance is defined by height of left sub-tree - height of right sub-tree. For an AVL tree the value of the balance factor of any node is -1, 0, or 1. If it is other than these three values then the tree is not balanced.

Insertion In AVL Tree

We can insert a new node in an AVL tree by finding its appropriate position similar to that of the binary search tree.

If the data item with key 'k' is inserted into an empty AVL tree, then the node with key 'k' is set to be the root node.
If tree contains only single node i.e. root node then the insertion of the node with key 'k' depends upon its value. If the value of 'k' is less than the key value of the root then it is inserted to the left of the root otherwise right of the root.
If on inserting the node with key 'k' the height of the right sub-tree of the root has increased. Similarly if on inserting a node with key 'k' the height of the left sub-tree of the root is increased.

LL Rotation: The new node 'x' is inserted in the left sub-tree of root node whose(root) balance factor becomes +2 after insertion. Below in the Fig 2 we will see the LL rotation.

RR Rotation: Unbalance occurs due to insertion in the right sub-tree of the right child of the root node and balance factor of root node becomes -2.We will see the RR rotation in the following Fig 3.

LR Rotation: Unbalance occurred due to the insertion in the right sub-tree of the left child of the root node. We will clear this rotation in the following Fig 4.

RL Rotation: Unbalance occurred due to the insertion in the left subtree of the right child of the root node. We will clear this rotation in the following Fig 5.

Insertion In AVL Tree Using C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
};
 
int max(int a, int b);
 
int height(struct Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
struct Node* newNode(int key)
{
    struct Node* node = (struct Node*)
                        malloc(sizeof(struct Node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}
 
struct Node *rightRotate(struct Node *y)
{
    struct Node *x = y->left;
    struct Node *T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
 
    // Return new root
    return x;
}
 
struct Node *leftRotate(struct Node *x)
{
    struct Node *y = x->right;
    struct Node *T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
 
    // Return new root
    return y;
}
 
int getBalance(struct Node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
struct Node* insert(struct Node* node, int key)
{
    /* 1.  Perform the normal BST insertion */
    if (node == NULL)
        return(newNode(key));
 
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else // Equal keys are not allowed in BST
        return node;
 
    /* 2. Update height of this ancestor node */
    node->height = 1 + max(height(node->left),
                           height(node->right));
 
    /* 3. Get the balance factor of this ancestor
          node to check whether this node became
          unbalanced */
    int balance = getBalance(node);
 
    // If this node becomes unbalanced, then
    // there are 4 cases
 
    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    /* return the (unchanged) node pointer */
    return node;
}
 
void preOrder(struct Node *root)
{
    if(root != NULL)
    {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}
 
int main()
{
  struct Node *root = NULL;
   int ch,value;
    while(1)
    {
        printf("\n1.insert");
        printf("\n2.preorder");
        printf("\n3.exit");
        printf("\nenter your choice:");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1:printf("\nenter the value:");
                   scanf("%d",&value);
                   root=insert(root,value);
                   break;
            case 2:preOrder(root);
                   break;
            case 3:return 0;
        }
    }
    return 0;
 }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Deletion In AVL Tree

The deletion of a node from an AVL tree is exactly the same as the deletion of a node from the BST. The sequence of steps to be followed in deleting a node from an AVL tree is as follows:

Initially, the AVL tree is searched to find the node to be deleted.
The procedure used to delete a node in an AVL tree is the same as deleting the node in the binary search tree.
After deletion of the node, check the balance factor of each node.
Rebalance the AVL tree if the tree is unbalanced. In this situation we need some rotations.

R0 And L0 Rotation: When we delete a node and that node is present at the right sub-tree. In this situation th parent node of left sub-tree whose balance factor is 0 is rotated in right direction. Similarly for L0 rotation, the deleted node is present at left sub-tree of root node. We will see the rotation in following Fig 1.

R1 And L1 Rotation: It is same as R0 or L0 rotation. Only the difference is that balance factor of parent node of left sub-tree or right sub-tree is +1 here.We will see the rotation in following Fig 2.

R(-1) And L(-1) Rotation: In this case balance factor of parent node is -1. we will see the rotation in following Fig 3.

Deletion In AVL Tree Using C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
};
 
int max(int a, int b);
 
int height(struct Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}
 
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
struct Node* newNode(int key)
{
    struct Node* node = (struct Node*)
                        malloc(sizeof(struct Node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}
 
struct Node *rightRotate(struct Node *y)
{
    struct Node *x = y->left;
    struct Node *T2 = x->right;
 
    // Perform rotation
    x->right = y;
    y->left = T2;
 
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
 
    // Return new root
    return x;
}
 
struct Node *leftRotate(struct Node *x)
{
    struct Node *y = x->right;
    struct Node *T2 = y->left;
 
    // Perform rotation
    y->left = x;
    x->right = T2;
 
    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
 
    // Return new root
    return y;
}
 
int getBalance(struct Node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
 
struct Node* insert(struct Node* node, int key)
{
    /* 1.  Perform the normal BST rotation */
    if (node == NULL)
        return(newNode(key));
 
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else // Equal keys not allowed
        return node;
 
    /* 2. Update height of this ancestor node */
    node->height = 1 + max(height(node->left),
                           height(node->right));
 
    /* 3. Get the balance factor of this ancestor
          node to check whether this node became
          unbalanced */
    int balance = getBalance(node);
 
    // If this node becomes unbalanced, then there are 4 cases
 
    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
 
    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
 
    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
 
    /* return the (unchanged) node pointer */
    return node;
}
 
struct Node * minValueNode(struct Node* node)
{
    struct Node* current = node;
 
    /* loop down to find the leftmost leaf */
    while (current->left != NULL)
        current = current->left;
 
    return current;
}
 
struct Node* deleteNode(struct Node* root, int key)
{
    // STEP 1: PERFORM STANDARD BST DELETE
 
    if (root == NULL)
        return root;
 
    // If the key to be deleted is smaller than the
    // root's key, then it lies in left subtree
    if ( key < root->key )
        root->left = deleteNode(root->left, key);
 
    // If the key to be deleted is greater than the
    // root's key, then it lies in right subtree
    else if( key > root->key )
        root->right = deleteNode(root->right, key);
 
    // if key is same as root's key, then This is
    // the node to be deleted
    else
    {
        // node with only one child or no child
        if( (root->left == NULL) || (root->right == NULL) )
        {
            struct Node *temp = root->left ? root->left :
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Community

Join WhatsApp Grpup using https://chat.whatsapp.com/EAcqRurEOXb52Ax7Tlmj9I

AVL Tree and Balancing

Balance Factor

Insertion In AVL Tree

Deletion In AVL Tree

Deletion In AVL Tree Using C

Happy Exploring!

No comments:

Post a Comment

About BunksAllowed

Coding Challenges

Socialize

Categories

Followers

BunksAllowed

Comments

Subscribe To

Total Pageviews

Blog Archive

Categories

Recent Posts

Popular Posts

Subscribe Us

Quick Contact

Translate

Archive

Follow Us

We Acknowledge

PEXELS

Recent Tutorials

Contact Form

Categories