Woah.. First of all a merry Christmas to all my blog readers
and to the non-readers also…
Today’s post is special obviously because of the topic we
are going to discuss is super important but also because I am writing this post
because, one of my friend called me lately and told that my blog was useful for
preparing for this company, which was visiting his campus, Overwhelmed by the
response I decided to dedicate this post to my friend Anupam.
Another reason is because today is the birthday of my very
special friend shivanshu so Happy b’day to you friend, brother, bestie.. etc..
, my post is dedicated to you also.
Now let’s discuss the topic we are here for (such an irony….)
Now let’s discuss the topic we are here for (such an irony….)
Today’s post is all about AVL trees. Now why AVL trees
because AVL is a self-balancing binary tree, whose specialty is that operations
like finding max, min, delete, insert takes O(h) time, where h is the height of
tree. The upper bound for height is (Log n), that’s why this tree is special.
As we know that in case of Binary tree all these operations take O(n) time in case of worst case, which is in case
of skewed binary tree.
INSERTION
To make sure that after every insertion the tree remains
balanced or the upper bound remains (Log n) some mumbo jumbo magic is required,
since we computer scientists have our magic in codes, I will try to do the same
to get height balanced after every operation.
The two operations are
- Left Rotate
- Right Rotate
The idea is to augment the standard BST insert so that the
tree remains height balanced.
Now what is height balance??
Height of left child/subtree – Height of right child/subtree
should be between [-1,1] i.e. {1,0,-1}. (since these values can be integer only).
The above condition make sure that the height of the BST
remain balanced and whenever the above condition violates we apply right
rotation or left rotation to make the tree balanced again.
Steps to follow for insertion
Let the newly inserted node be w
1) Perform standard BST insert for w.
2) Starting from w, travel up and find the first unbalanced
node. Let z be the first unbalanced node, y be the child of z that comes on the
path from w to z and x be the grandchild of z that comes on the path from w to z.
3) Re-balance the tree by performing appropriate rotations
on the subtree rooted with z. There can be 4 possible cases that needs to be
handled as x, y and z can be arranged in 4 ways. Following are the possible 4
arrangements:
a) y is left child of z and x is left child of y (Left Left
Case)
b) y is left child of z and x is right child of y (Left
Right Case)
c) y is right child of z and x is right child of y (Right
Right Case)
d) y is right child of z and x is left child of y (Right
Left Case)
Following are the operations to be performed in above
mentioned 4 cases. In all of the cases, we only need to re-balance the subtree
rooted with z and the complete tree becomes balanced as the height of subtree
(After appropriate rotations) rooted with z becomes same as it was before
insertion.
a) Left Left Case
T1, T2, T3 and T4 are subtrees.
z y
/ \ / \
y T4
Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
b) Left Right Case
z z x
/ \ / \ / \
y T4
Left Rotate(y) x T4 Right Rotate(z) y z
/ \ - - - - - - - -> /
\ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3
T4
/ \ / \
T2 T3 T1 T2
c) Right Right Case
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - -
- - - - - -> / \ / \
T2 x T1 T2 T3
T4
/ \
T3 T4
d) Right Left Case
z z x
/ \ / \ / \
T1 y Right Rotate(y) T1
x Left Rotate(z) z y
/ \ - - - - - - - - -> /
\ - - - - - - - -> / \ / \
x T4 T2 y T1 T2
T3 T4
/ \ / \
T2 T3 T3 T4
No comments:
Post a Comment