CSE332: Data AbstractionsLecture 7: AVL TreesTyler RobisonSummer 20101The AVL Tree Data StructureAn AVL tree is a BSTIn addition: Balance property:balance of every node isbetween -1 and 1balance(node) = height(node.left) –height(node.right)Result: Worst-case depth is O(log n)How are we going to maintain this? Worry about that later…4131062115814127 91521118461012700001123Is it an AVL tree?3BST? CheckHeight/balance property?Start at leaves, move upwardAt each node, check:Are heights of left & right within 1 of each other?311718462500 0 011234Is this an AVL tree?4Null child has height of -1; this is an imbalanceThe shallowness bound: Proving that the AVL balance property is ‘enough’Let S(h) = the minimum number of nodes in an AVL tree of height h If we can prove that S(h) grows exponentially in h, then a tree with n nodes has a logarithmic height Step 1: Define S(h) inductively using AVL property S(-1)=0, S(0)=1, S(1)=2 For h2, S(h) = 1+S(h-1)+S(h-2) Build our minimal tree from smaller minimal trees, w/ heights within 1 of each other Step 2: Show this recurrence grows really fast Similar to Fibonacci numbers Can prove for all h, S(h) > h– 1 where is the golden ratio, (1+5)/2, about 1.62 Growing faster than 1.6his “plenty” exponentialh-1h-2h5Notational note:Oval: a node in the treeTriangle: a subtreeBefore we prove it Good intuition from plots comparing: S(h) computed directly from the definition ((1+5)/2)h S(h) is always bigger Graphs aren‟t proofs, so let‟s prove it6The Golden Ratio62.1251This is a special number: If (a+b)/a = a/b, then a = b• Aside: Since the Renaissance, many artists and architects have proportioned their work (e.g., length:height) to approximate the golden ratio• We will need one special arithmetic fact about :2= ((1+51/2)/2)2= (1 + 2*51/2+ 5)/4 = (6 + 2*51/2)/4 = (3 + 51/2)/2 = 1 + (1 + 51/2)/2= 1 + 7The proofTheorem: For all h 0, S(h) > h– 1 Proof: By induction on hBase cases:S(0) = 1 > 0– 1 = 0 S(1) = 2 > 1– 1 0.62Inductive case (k > 1):Inductive hypotheses: S(k) > k– 1 and S(k-1) > k-1– 1Show S(k+1) > k+1– 1S(k+1) = 1 + S(k) + S(k-1) by definition of S> 1 + k– 1 + k-1– 1 by inductive hypotheses= k+ k-1– 1 by arithmetic (1-1=0)= k-1( + 1) – 1 by arithmetic (factor k-1)= k-12 – 1 by special property of = k+1– 1 by arithmetic (add exponents)S(-1)=0, S(0)=1, S(1)=2For h2, S(h) = 1+S(h-1)+S(h-2)8Good newsProof means that if we have an AVL tree, then find is O(log n)But as we insert and delete elements, we need to:1. Track balance2. Detect imbalance3. Restore balanceIs this AVL tree balanced?How about after insert(30)?92510715209An AVL Tree209215510301770000112 23…3valueheightchildrenTrack height at all times!10key 10AVL tree operation overview AVL find: Same as BST find AVL insert: First BST insert, then check balance and potentially “fix” the AVL tree Four different imbalance cases AVL delete: The “easy way” is lazy deletion Otherwise, like insert we do the deletion and then have several imbalance cases11Insert: detect potential imbalance1. Insert the new node as in a BST (a new leaf)2. For each node on the path from the root to the new leaf, the insertion may (or may not) have changed the node‟s height3. So when returning from insertion in a subtree:1. Update heights, if necessary2. Detect height imbalance3. Perform a rotation to restore balance at that node, if necessaryFact that makes it a bit easier: We‟ll only need to do one type of rotation in one place to fix balance That is, a single „move‟ can fix it all12Insertion Imbalance ExampleInsert(6)Insert(3)Insert(1)Third insertion violates balance property• happens to be detected at the rootWhat is the only way to fix this? 63121063106013Fix for ‘left-left’ case: Apply ‘Single Rotation’ Single rotation: The basic operation we‟ll use to rebalance Move child of unbalanced node into parent position Parent becomes the “other” child (always okay in a BST!) Other subtrees move in only way BST allows31 6001AVL Property violated hereIntuition: 3 must become rootnew-parent-height = old-parent-height-before-insert630121144 Different rotation cases15 Do the BST insertion, recurse back up the tree and check for an imbalance at each node If an imbalance is detected at node c, we‟ll perform 1 of 4 types of rotations to fix it, depending on which subtree the insertion was incXVUZab1 2 3 4Back to our example (case 1) Node imbalanced due to insertion somewhere in left-left grandchild that increased the height First we did the insertion, which would make node aimbalanced16630121aZYbXhhhh+1h+2aZYbXh+1hhh+2h+3Before insertion After insertionThe general left-left case Rotate at node a, using the fact that in a BST:X < b < Y < a < Z• A single rotation restores balance at the node– To same height as before insertion (so ancestors now balanced)aZYbXh+1hhh+2h+3bZYah+1hhh+1h+2X17Another example: insert(16)10422815361917 20241618Another case 1 example: insert(16)10422815361917 2024161048153619172016222419The general right-right case (case 4) Mirror image to left-left case, so you rotate the other way Exact same concept, but need different codeaZYXhhh+1h+3bh+2bZYaXhhh+1h+1h+220Two cases to goUnfortunately, single rotations are not enough for insertions in the left-right subtree or the right-left subtreeSimple example: insert(1), insert(6), insert(3) First wrong idea: single rotation like we did for left-left36101261310 021Two cases to goUnfortunately, single rotations are not enough for insertions in the left-right subtree or the right-left subtreeSimple example: insert(1), insert(6), insert(3) Second wrong idea: single rotation on the child of the unbalanced node36101263101222Sometimes two wrongs make a right First idea violated the BST property Second idea didn‟t fix balance But if we do both single rotations, starting with the second, it works! (And not just for this example.) Double rotation: 1. Rotate problematic child and grandchild2. Then rotate between self and new child361012631012001136Intuition: 3 must become root23The general right-left caseaXbch-1hhhVUh+1h+2h+3ZaXch-1h+1hhVUh+2h+3ZbhcXh-1h+1hh+1VUh+2Zbhah24Comments Like
View Full Document
Unlocking...