IntroductionThe Height InvariantLeft and Right RotationsSearching for a KeyInserting an ElementChecking InvariantsImplementing InsertionExperimental EvaluationLecture Notes onAVL Trees15-122: Principles of Imperative ComputationFrank PfenningLecture 18March 22, 20111 IntroductionBinary search trees are an excellent data structure to implement associa-tive arrays, maps, sets, and similar interfaces. The main difficulty, as dis-cussed in last lecture, is that they are efficient only when they are balanced.Straightforward sequences of insertions can lead to highly unbalanced treeswith poor asymptotic complexity and unacceptable practical efficiency. Forexample, if we insert n elements with keys that are in strictly increasing ordecreasing order, the complexity will be O(n2). On the other hand, if wecan keep the height to O(log (n)), as it is for a perfectly balanced tree, thenthe commplexity is bounded by O(n ∗ log(n)).The solution is to dynamically rebalance the search tree during insertor search operations. We have to be careful not to destroy the orderinginvariant of the tree while we rebalance. Because of the importance of bi-nary search trees, researchers have developed many different algorithmsfor keeping trees in balance, such as AVL trees, red/black trees, splay trees,or randomized binary search trees. They differ in the invariants they main-tain (in addition to the ordering invariant), and when and how the rebal-ancing is done.In this lecture we use AVL trees, which is a simple and efficient datastructure to maintain balance, and is also the first that has been proposed.It is named after its inventors, G.M. Adelson-Velskii and E.M. Landis, whodescribed it in 1962.LECTURE NOTES MARCH 22, 2011AVL Trees L18.22 The Height InvariantRecall the ordering invariant for binary search trees.Ordering Invariant. At any node with key k in a binary searchtree, all keys of the elements in the left subtree are strictly lessthan k, while all keys of the elements in the right subtree arestrictly greater than k.To describe AVL trees we need the concept of tree height, which we de-fine as the maximal length of a path from the root to a leaf. So the emptytree has height 0, the tree with one node has height 1, a balanced tree withthree nodes has height 2. If we add one more node to this last tree is willhave height 3. Alternatively, we can define it recursively by saying that theempty tree has height 0, and the height of any node is one greater than themaximal height of its two children. AVL trees maintain a height invariant(also sometimes called a balance invariant).Height Invariant. At any node in the tree, the heights of the leftand right subtrees differs by at most 1.As an example, consider the following binary search tree of height 3.16#10#19#1# 13#7#4#height#=#3#height#inv.#sa4sfied#LECTURE NOTES MARCH 22, 2011AVL Trees L18.3If we insert a new element with a key of 14, the insertion algorithm forbinary search trees without rebalancing will put it to the right of 13.height&=&4&height&inv.&sa.sfied&16&10&19&1& 13&7&4&14&Now the tree has height 4, and one path is longer than the others. However,it is easy to check that at each node, the height of the left and right subtreesstill differ only by one. For example, at the node with key 16, the left subtreehas height 2 and the right subtree has height 1, which still obeys our heightinvariant.Now consider another insertion, this time of an element with key 15.This is inserted to the right of the node with key 14.height&=&5&height&inv.&violated&at&13,&16,&10&16&10&19&1& 13&7&4&14&15&LECTURE NOTES MARCH 22, 2011AVL Trees L18.4All is well at the node labeled 14: the left subtree has height 0 while theright subtree has height 1. However, at the node labeled 13, the left subtreehas height 0, while the right subtree has height 2, violating our invariant.Moreover, at the node with key 16, the left subtree has height 3 while theright subtree has height 1, also a difference of 2 and therefore an invariantviolation.We therefore have to take steps to rebalance tree. We can see withouttoo much trouble, that we can restore the height invariant if we move thenode labeled 14 up and push node 13 down and to the right, resulting inthe following tree.height&=&4&height&inv.&restored&at&14,&16,&10&16&10&19&1& 14&7&4&15&13&The question is how to do this in general. In order to understand this weneed a fundamental operation called a rotation, which comes in two forms,left rotation and right rotation.3 Left and Right RotationsBelow, we show the situation before a left rotation. We have genericallydenoted the crucial key values in question with x and y. Also, we havesummarized whole subtrees with the intervals bounding their key values.Even though we wrote −∞ and +∞, when the whole tree is a subtree of alarger tree these bounds will be generic bounds α which is smaller than xLECTURE NOTES MARCH 22, 2011AVL Trees L18.5and ω which is greater than y. The tree on the right is after the left rotation.x"y"(‐∞,"+∞)"(y,"+∞)"(‐∞,"x)"(x,"y)"y"(‐∞,"+∞)"(y,"+∞)"(‐∞,"x)" (x,"y)"x"le,"rota1on"at"x"From the intervals we can see that the ordering invariants are preserved, asare the contents of the tree. We can also see that it shifts some nodes fromthe right subtree to the left subtree. We would invoke this operation if theinvariants told us that we have to rebalance from right to left.We implement this with some straightforward code. First, recall thetype of trees from last lecture. We do not repeat the function is_ordtreethat checks if a tree is ordered.struct tree {elem data;struct tree* left;struct tree* right;};typedef struct tree* tree;bool is_ordtree(tree T);The main point to keep in mind is to use (or save) a component of theinput before writing to it. We apply this idea systematically, writing to alocation immediately after using it on the previous line. We repeat the typespecification of tree from last lecture.tree rotate_left(tree T)//@requires is_ordtree(T);//@requires T != NULL && T->right != NULL;//@ensures is_ordtree(\result);//@ensures \result != NULL && \result->left != NULL;{tree root = T->right;LECTURE NOTES MARCH 22, 2011AVL Trees L18.6T->right = root->left;root->left = T;return root;}The right rotation is entirely symmetric. First in pictures:z"y"(‐∞,"+∞)"(z,"+∞)"(‐∞,"y)" (y,"z)"z"y"(‐∞,"+∞)"(z,"+∞)"(‐∞,"y)"(y,"z)"right"rota1on"at"z"Then in code:tree rotate_right(tree T)//@requires is_ordtree(T);//@requires