IntroductionIn the previous set of notes you were introduced to binary search trees (BSTs).Recall that one of the problems with general BSTs is that the tree may beunbalanced and thus skewed to the right or left. The more heavily skewed thetree, the further in general, you will get from the logarithmic time bound onsearching in the tree. Therefore, it becomes a potentially important task to beable to balance the search tree. We will briefly examine a global balancingalgorithm known as the DSW algorithm (named for its developer’s Day and laterimproved by Stout and Warren). Algorithm’s such as the DSW algorithmperform balancing (or rebalancing actually) on the entire tree, thus algorithm’s ofthis type are known as global balancing algorithms. Global balancingalgorithms are fairly costly, particularly when the search tree is already fairly wellbalanced. As an alternative, algorithms which adjust the balance of the searchtree on a local basis; that is, they do not consider the entire tree but restrict theirrebalancing to a subtree, have been developed as more efficient techniques forsuch well balanced search trees. This set of notes will introduce the AVL treewhich is a search tree variant that self-balances at the local level.Most advanced tree structures, each with particular properties regardingbalance, restricting the height growth, specifying insertion points, etc. aregeared toward searching operations in one form or another, rather than simpledata representation. We’ll start our foray into advanced tree structures with aquick look at the DSW algorithm, and AVL trees. Binary Search TreesThe property that turns a binary tree into a binary search tree is that for everynode x, in the tree, the values of all the items in the left subtree of x are smallerthan the item in x and the values of all the items in the right subtree of x arelarger than the item in x. Notice that this implies that every item in the tree ispart of a total ordering. Using this definition and considering the two treesshown in Figure 1, the tree on the left is a BST while the tree on the right is nota BST.AVL Trees - 1Advanced Tree Structures – AVL Trees (Day 25)(a) (b)Figure 1 – (a) A BST, (b) Not a BST (nodes 2 and 6 are in error)Recall that inserting a new node into a BST essentially involves a search forthat node which will direct you to the correct location at which it is to be insertedas a new leaf node. Note that it is not possible to insert a new internal node in aBST. Deletion of a node in a BST is trivial if the node to be deleted is a leafnode. Deletion of an internal node is also trivial if the node to be deleted hasonly a single child. However, if the internal node has two children, then nosingle step operation will be able to complete the deletion of the node. The twobasic techniques for deleting a node with two children are: deletion by copyingand deletion by merging. Deletion by MergingThis technique makes one tree out of the two subtrees of the node which will bedeleted and then attaches it to that node’s parent. The main question is howcan these two subtrees be merged? The nature of the BST is that every valuein the right subtree is greater than every value in the left subtree, so the bestthing to do is find, within the left subtree, the node with the greatest value andmake this the parent of the right subtree. Symmetrically, the node with thelowest value can be found in the right subtree and made a parent of the leftsubtree.The desired node is the rightmost node of the left subtree. This node can belocated by traversing this subtree always taking right references until a nullreference is encountered (indicating that we have reached a leaf node). Thismeans that the node which has been located has no right child, and there is nodanger of violating the property of BSTs in the original tree by setting thatrightmost node’s right reference to the right subtree. [Symmetry would allow usto accomplish exactly the same effect by setting the left reference of theAVL Trees - 2ccabced fgih735 62 9222521(a) (b)leftmost node of the right subtree to the left subtree.] This operation is depictedgraphically in Figure 2. Figure 2 – Illustration of Deletion by Merging in a BSTDeletion by CopyingDeletion by copying was proposed by Thomas Hibbard and Donald Knuth. Thejustification for this technique is the deletion by merging technique may increasethe height of the tree! In some cases the resulting tree may be highlyunbalanced. Some cases may decrease the overall height of the tree. For ourpurposes here, this will not be a concern because we will rebalance the tree inany case. I’ll illustrate the technique of deletion by copying so that you will haveit, but deletion by merging is easier to understand.If the node has two children, it can be reduced to one of two simple cases: Thenode is a leaf or the node has only one nonempty child. This can be done byreplacing the key being deleted with its immediate predecessor (or successor).As we mentioned in the previous technique of deleting by merging, a key’spredecessor is the key in the rightmost node in the left subtree (via symmetry,its immediate successor is the key in the leftmost node in the right subtree).First, the predecessor has to be located. This is again done by moving one stepto the left by first reaching the root of the node’s left subtree and then moving asfar to the right as possible. Next, the key of the located node replaces the keyto be deleted. At this point is where one of the two simple cases comes intoplay. If the rightmost node is a leaf, the first case applies; however, if it has onechild the second case will apply. In this way, deletion via copying removes a keyk1 by overwriting it with another key k2 and then removing the node that holds k2,whereas deletion by merging consisted of removing a key k1 along with theAVL Trees - 3node that holds it. Deletion by copying is shown graphically in the diagramsillustrated in Figure 3.Figure 3 – Illustration of Deletion by Copying in a BSTDSW AlgorithmRecall that a binary tree is height-balanced or simply balanced if the differencein height of both subtrees of any node is either zero or one. A perfectlybalanced