Lecture Notes on AVL Trees 15 122 Principles of Imperative Computation Frank Pfenning Lecture 18 March 22 2011 1 Introduction Binary search trees are an excellent data structure to implement associative arrays maps sets and similar interfaces The main difficulty as discussed in last lecture is that they are efficient only when they are balanced Straightforward sequences of insertions can lead to highly unbalanced trees with poor asymptotic complexity and unacceptable practical efficiency For example if we insert n elements with keys that are in strictly increasing or decreasing order the complexity will be O n2 On the other hand if we can keep the height to O log n as it is for a perfectly balanced tree then the commplexity is bounded by O n log n The solution is to dynamically rebalance the search tree during insert or search operations We have to be careful not to destroy the ordering invariant of the tree while we rebalance Because of the importance of binary search trees researchers have developed many different algorithms for keeping trees in balance such as AVL trees red black trees splay trees or randomized binary search trees They differ in the invariants they maintain in addition to the ordering invariant and when and how the rebalancing is done In this lecture we use AVL trees which is a simple and efficient data structure 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 who described it in 1962 L ECTURE N OTES M ARCH 22 2011 AVL Trees 2 L18 2 The Height Invariant Recall the ordering invariant for binary search trees Ordering Invariant At any node with key k in a binary search tree all keys of the elements in the left subtree are strictly less than k while all keys of the elements in the right subtree are strictly greater than k To describe AVL trees we need the concept of tree height which we define as the maximal length of a path from the root to a leaf So the empty tree has height 0 the tree with one node has height 1 a balanced tree with three nodes has height 2 If we add one more node to this last tree is will have height 3 Alternatively we can define it recursively by saying that the empty tree has height 0 and the height of any node is one greater than the maximal 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 left and right subtrees differs by at most 1 As an example consider the following binary search tree of height 3 10 4 1 L ECTURE N OTES 16 7 13 height 3 height inv sa4s ed 19 M ARCH 22 2011 AVL Trees L18 3 If we insert a new element with a key of 14 the insertion algorithm for binary search trees without rebalancing will put it to the right of 13 10 4 1 16 7 13 height 4 height inv sa s ed 19 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 subtrees still differ only by one For example at the node with key 16 the left subtree has height 2 and the right subtree has height 1 which still obeys our height invariant Now consider another insertion this time of an element with key 15 This is inserted to the right of the node with key 14 10 4 1 16 7 13 height 5 height inv violated at 13 16 10 19 14 15 L ECTURE N OTES M ARCH 22 2011 AVL Trees L18 4 All is well at the node labeled 14 the left subtree has height 0 while the right subtree has height 1 However at the node labeled 13 the left subtree has 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 the right subtree has height 1 also a difference of 2 and therefore an invariant violation We therefore have to take steps to rebalance tree We can see without too much trouble that we can restore the height invariant if we move the node labeled 14 up and push node 13 down and to the right resulting in the following tree 10 4 1 16 7 14 13 height 4 height inv restored at 14 16 10 19 15 The question is how to do this in general In order to understand this we need a fundamental operation called a rotation which comes in two forms left rotation and right rotation 3 Left and Right Rotations Below we show the situation before a left rotation We have generically denoted the crucial key values in question with x and y Also we have summarized whole subtrees with the intervals bounding their key values Even though we wrote and when the whole tree is a subtree of a larger tree these bounds will be generic bounds which is smaller than x L ECTURE N OTES M ARCH 22 2011 AVL Trees L18 5 and which is greater than y The tree on the right is after the left rotation y x x y le rota1on at x x y y x x y x y From the intervals we can see that the ordering invariants are preserved as are the contents of the tree We can also see that it shifts some nodes from the right subtree to the left subtree We would invoke this operation if the invariants told us that we have to rebalance from right to left We implement this with some straightforward code First recall the type of trees from last lecture We do not repeat the function is ordtree that 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 the input before writing to it We apply this idea systematically writing to a location immediately after using it on the previous line We repeat the type specification 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 L ECTURE N OTES M ARCH 22 2011 AVL Trees L18 6 T right root left root left T return root The right rotation is entirely symmetric First in pictures y z right rota1on at z y y z y z y z y z z Then in code tree rotate right tree T requires is ordtree T requires T NULL T left NULL ensures is ordtree result ensures result NULL result right NULL tree root T left T left root right root right …