Slide 1The AVL Tree Data StructureAn AVL tree?An AVL tree?The shallowness boundBefore we prove itThe Golden RatioThe proofGood newsAn AVL TreeAVL tree operationsInsert: detect potential imbalanceCase #1: ExampleFix: Apply “Single Rotation”The example generalizedThe general left-left caseAnother example: insert(16)Another example: insert(16)The general right-right caseTwo cases to goTwo cases to goSometimes two wrongs make a right The general right-left caseCommentsThe last case: left-rightInsert, summarizedNow efficiencyCSE332: Data AbstractionsLecture 7: AVL TreesDan GrossmanSpring 20102The AVL Tree Data Structure4131062115814127 9Structural properties1. Binary tree property2. Balance property:balance of every node isbetween -1 and 1Result:Worst-case depth isO(log n) Ordering property–Same as for BST15Spring 2010 CSE332: Data Abstractions1118461012700001123An AVL tree?311718462500 0 011234An AVL tree?5The shallowness boundLet 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 h 2, S(h) = 1+S(h-1)+S(h-2)•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.6h is “plenty” exponentialh-1h-2hBefore 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 itSpring 2010 6CSE332: Data Abstractions7The Golden Ratio62.1251This is a special number•Aside: Since the Renaissance, many artists and architects have proportioned their work (e.g., length:height) to approximate the golden ratio: If (a+b)/a = a/b, then a = b•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 + The 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): Show S(k+1) > k+1 – 1 assuming S(k) > k – 1 and 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 induction = k + k-1 – 1 by arithmetic (1-1=0) = k-1 ( + 1) – 1 by arithmetic (factor k-1 ) = k-1 2 – 1 by special property of  = k+1 – 1 by arithmetic (add exponents) Spring 2010 8CSE332: Data AbstractionsS(-1)=0, S(0)=1, S(1)=2For h 2, S(h) = 1+S(h-1)+S(h-2)Good 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 balanceSpring 2010 9CSE332: Data Abstractions925107Is this AVL tree balanced?How about after insert(30)?1520An AVL Tree209215510301770000112 23…3valueheightchildrenTrack height at all times!10 keyAVL tree operations•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 casesInsert: 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 after recursive insertion in a subtree, detect height imbalance and perform a rotation to restore balance at that nodeAll the action is in defining the correct rotations to restore balanceFact that an implementation can ignore:–There must be a deepest element that is imbalanced after the insert (all descendants still balanced)–After rebalancing this deepest node, every node is balanced–So at most one node needs to be rebalancedSpring 2010 12CSE332: Data AbstractionsCase #1: ExampleSpring 2010 13CSE332: Data AbstractionsInsert(6)Insert(3)Insert(1)Third insertion violates balance property•happens to be at the rootWhat is the only way to fix this? 631210631060Fix: 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 allows (next slide)Spring 2010 14CSE332: Data Abstractions31 600163012AVL Property violated hereIntuition: 3 must become rootnew-parent-height = old-parent-height-before-insert1The example generalized•Node imbalanced due to insertion somewhere in left-left grandchild increasing height–1 of 4 possible imbalance causes (other three coming)•First we did the insertion, which would make a imbalancedSpring 2010 15CSE332: Data AbstractionsaZYbXhhhh+1h+2aZYbXh+1hhh+2h+3The general left-left case•Node imbalanced due to insertion somewhere in left-left grandchild increasing height–1 of 4 possible imbalance causes (other three coming)•So we rotate at a, using BST facts: X < b < Y < a < ZSpring 2010 16CSE332: Data Abstractions•A single rotation restores balance at the node–To same height as before insertion (so ancestors now balanced)aZYbXh+1hhh+2h+3bZYah+1hhh+1h+2XAnother example: insert(16)Spring 2010 17CSE332: Data Abstractions10 422 815 3 61917 202416Another example: insert(16)Spring 2010 18CSE332: Data Abstractions10 422 815 3 61917 20241610 4 815 3 6191720162224The general right-right case•Mirror image to left-left case, so you rotate the other way–Exact same concept, but need different codeSpring 2010 19CSE332: Data AbstractionsaZYXhhh+1h+3bh+2bZYaXhhh+1h+1h+2Two 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-leftSpring 2010 20CSE332: Data Abstractions36101 261310 0Two 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 nodeSpring 2010 21CSE332: Data Abstractions36101 26310 1 2Sometimes two