AVL Tree Deletion Rules

user_8893914 0
Viewed 375

For an AVL tree, when deleting a node from the tree that requires restructuring, the book i am reading states that there are certain rules to following to select which nodes to restructure. An example is as such:

       44
     /   \
    17   62
        /  \
       50  78
      /  \   \
     48  54  88

This is the AVL tree after a node(child of node 17) has been deleted and the height-balance property has been violated.

The book i read states that it will let z be the first unbalanced position encountered going up from node 17, y be the child of z with the greater height and finally x be the child of y with the greater height. However, if the children of y both have the same height, then x will be the same side as y. In this case, x is 78, y is 62, z is 44.

Now here is the question posed. Why do we select x such that it is the same side as y? Will there be any issues with the AVL tree if i select x to not be the same side as y? I have tried to give myself examples and tried selecting both types of x and, restructure the AVL tree. However, i cannot seem to find any issues that will arise from selecting x as either child. Any help is appreciated to help me solve this.

binary-search-tree avl-tree tree data-structures
1 Answers

Interestingly this topic has so many variations of answers in the various web forums. I tried creating all possible AVL tree node deletion scenario and I observed that if the node is deleted from left side of the AVL tree to make tree imbalanced, perform LL or LR (any of possible rotation) based on node availability, and the tree gets balanced. Viceversa for right node deletion.

Also, need to be sure if the moving node due to rotation has children, the children to be inserted on left or right if they were if left or right side before rotation, respectively.

user_125913590
Related