AVL Tree/Discussion: Difference between revisions

Deleting entries from a Binary Search Tree turns out to be quite tricky. When a node has only one child it is easy, just go to the parent and link the child of the node to be deleted in place of the node itself. The main problem arises when the node to be deleted has two children. For example, the following tree will be built, and node 6 will be deleted.

 

 

Node 6 has two children. To delete it, node 6 will be swapped with node 4, then deleted. The tree that remains is shown below.

 

 

Node 4 was chosen for the swap because it is the immediate predecessor of node 6. Note that a valid Binary Search Tree results. In general, when a node to be deleted has two children, its inorder predecessor is located and swapped with the node to be deleted. The node at its new position has at most one child and may easily be deleted.

The Russian mathematicians G.M.Adel'son-Vel'skii and E.M.Landis were the first to notice that certain operations can be performed on binary trees without affecting their validity. For example, please consider the following diagram.

 

 

The second tree is obtained from the first by rotating the node 7 left and upwards. It is called a left rotation. The things to notice about this transformation are:

The first case (in BalanceRight) is illustrated in the diagram below.

 

 

The required action is a left rotation. In the diagram, the node x is rotated upward and r is made the left subtree of x. The left subtree T2 of x becomes the right subtree of r. A left rotation is described in the appropriate C# function (see RotateLeft). Note that when done in the appropriate order, the steps constitute a rotation of three reference values. After the rotation, the height of the rotated set has decreased by 1 whereas it had previously increased because of the insertion, thus the height finishes where it began.

The second case is when the balance factor of x is left high. This case is more complicated. It is required to move two levels to the node w that is the root of the left subtree of x to find the new root. This process is called a double rotation because the transformation can be obtained in two steps (see diagram below). First, x is rotated to the right (so that w becomes its root) and then the set with root r is rotated to the left (moving w up to become the new root).

 

 

The code for BalanceRight (and BalanceLeft) should now be carefully considered with the above diagrams in mind.