AVL tree is a self-balancing Binary Search
Tree (BST) where the difference between heights of left and right subtrees
cannot be more than one for all nodes.
-
The height of an
empty subtree is 0.
-
The
height of a leaf is 1.
-
The
height of an internal node is the maximum height of its children plus 1.
Insertion
To make sure that the given tree remains AVL after
every insertion, we must augment the standard BST insert operation to perform
some re-balancing. Following are two basic operations that can be performed to
re-balance a BST without violating the BST property (keys(left) < key(root) <
keys(right)).
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)
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. (See this video
lecture for proof)
Rebelance avl tree:
•
There
is 4 cases:
•
Case
1 : the deepest node is located at the
left sub tree of the left child of T.
•
Case
2 : the deepest node is located at the
right sub tree of the right child of T.
•
Case
3 : the deepest node is located at the
right sub tree of the left child of T.
•
Case
4 : the deepest node is located at the
left sub tree of the right child of T.
Note: In insertion, the deepest node will be the
inserted node.
•
Violation
on case 1 and 2 (left-left or right-right) are fixed by single rotation.
•
Violation
on case 3 and 4 (left-right or right-left) are fixed by double rotation.
- - 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
- - 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
- - Right
Right Case :
z y
/ \ / \
T1 y Left Rotate(z) z
x
/ \ - -
- - - - - -> / \ / \
T2 x T1 T2 T3
T4
/ \
T3 T4
- - 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