Consider the rotations in the insertion and the removal of AVL trees. Let w be t
ID: 3774274 • Letter: C
Question
Consider the rotations in the insertion and the removal of AVL trees. Let w be the position to insert or to remove one node. Let z be the first unbalanced node along the path from w to the root. Let y be z's child with larger height and x be y's child with larger height. Consider the case where the inorder order of x, y, z is y, x, z (the double-rotation case). Let h_0, h_1 be the height function of nodes before and after the update respectively. Prove the following: prove that x, y, z are balanced after the update. Moreover, prove that h_1(x) = h_0(z). prove that x, y, z are balanced after the update. Note the difference between insertion and removal and carefully argue about the properties of h_0, h_1 for each case.Explanation / Answer
AVL Tree:
Here the question requires to prove that AVL tree is an self balancing tree, which remains balanced after removing and updating the nodes.
1.) To Prove AVL Tree remains balance after insertsion:
The Main property of AVL tree is that the difference between the left subtree and right subtree must be less than or equal to 1.
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)). 1) Left Rotation 2) Right Rotation
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. (See this video lecture for proof)
a) Left Left Case
b) Left Right Case
c) Right Right Case
d) Right Left Case
2.) To prove AVL tree remains balanced after deletion
To make sure that the given tree remains AVL after every deletion, we must augment the standard BST delete 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)). 1) Left Rotation 2) Right Rotation
Let w be the node to be deleted
1) Perform standard BST delete for w.
2) Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the larger height child of z, and x be the larger height child of y. Note that the definitions of x and y are different from insertion here.
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)
Like insertion, following are the operations to be performed in above mentioned 4 cases. Note that, unlike insertion, fixing the node z won’t fix the complete AVL tree. After fixing z, we may have to fix ancestors of z as well (See this video lecture for proof)
a) Left Left Case
b) Left Right Case
c) Right Right Case
d) Right Left Case
Unlike insertion, in deletion, after we perform a rotation at z, we may have to perform a rotation at ancestors of z. Thus, we must continue to trace the path until we reach the root.