Lecture 4 Balanced Binary Search Trees 6.006 Fall 2009Lecture 4: Balanced Binary Search TreesLecture Overview• The importance of being balanced• AVL trees– Definition– Balance– Insert• Other balanced trees• Data structures in generalReadingsCLRS Chapter 13. 1 and 13. 2 (but different approach: red-black trees)Recall: Binary Search Trees (BSTs)• rooted binary tree• each node has– key– left pointer– right pointer– parent pointerSee Fig. 1654120115029263211φφφFigure 1: Heights of nodes in a BST1Lecture 4 Balanced Binary Search Trees 6.006 Fall 2009x≤x≥xFigure 2: BST property• BST property (see Fig. 2).• height of node = length (] edges) of longest downward path to a leaf (see CLRS B.5for details).The Importance of Being Balanced:• BSTs support insert, min, delete, rank, etc. in O(h) time, where h = height of tree(= height of root).• h is between lg(n) and n: (see Fig. 3).vs.Perfectly Balanced PathFigure 3: Balancing BSTs• balanced BST maintains h = O(lg n) ⇒ all operations run in O (lg n) time.2Lecture 4 Balanced Binary Search Trees 6.006 Fall 2009AVL Trees:DefinitionAVL trees are self-balancing binary search trees. These trees are named after their twoinventors G.M. Adel’son-Vel’skii and E.M. Landis.1An AVL tree is one that requires heights of left and right children of every node to differby at most ±1. This is illustrated in Fig. 4)kk-1Figure 4: AVL Tree ConceptIn order to implement an AVL tree, follow two critical steps:• Treat nil tree as height −1.• Each node stores its height. This is inherently a DATA STRUCTURE AUGMENTATIONprocedure, similar to augmenting subtree size. Alternatively, one can just store dif-ference in heights.A good animation applet for AVL trees is available at this link. To compare Binary SearchTrees and AVL balancing of trees use code provided here.1Original Russian article: Adelson-Velskii, G.; E. M. Landis (1962). ”An algorithm for the organizationof information”. Proceedings of the USSR Academy of Sciences 146: 263266. (English translation by MyronJ. Ricci in Soviet Math. Doklady, 3:12591263, 1962.)3Lecture 4 Balanced Binary Search Trees 6.006 Fall 2009Balance:The balance is the worst when every node differs by 1.Let Nh= min (] nodes).⇒ Nh= Nh−1+ Nh−2+ 1> 2Nh−2⇒ Nh> 2h/2=⇒ h < 2 lg NhAlternatively:Nh> Fn(nthFibonacci number)In fact, Nh= Fn+2− 1 (simple induction)Fh=φh√5(rounded to nearest integer)where, φ =1 +√52≈ 1.618 (golden ratio)=⇒ max h ≈ logφ(n) ≈ 1.440 lg(n)AVL Insert:1. insert as in simple BST.2. work your way up tree, restoring AVL property (and updating heights as you go).Each Step:• suppose x is lowest node violating AVL• assume x is right-heavy (left case symmetric)• if x’s right child is right-heavy or balanced: follow steps in Fig. 5• else follow steps in Fig. 6• then continue up to x’s grandparent, greatgrandparent . . .4Lecture 4 Balanced Binary Search Trees 6.006 Fall 2009xyABCk+1kk-1k-1xzABCk+1k-1Left-Rotate(x)kkyxCABk+1kkk-1yxCABkkk-1k-1Left-Rotate(x)Figure 5: AVL Insert Balancing (FIX: Node z should be y)xzADk+1k-1Left-Rotate(x)k-1yxABkk-1yBCkk-1 ork-2Right-Rotate(z)zCDkk-1k+1k-1 ork-2Figure 6: AVL Insert Balancing5Lecture 4 Balanced Binary Search Trees 6.006 Fall 2009Example: An example implementation of the AVL Insert process is illustrated in Fig. 7.654120115029263211φφφ6541201150292621φφφ123Insert(23)x = 29: left-left case654120115026233211φφφ65412011501φφDone Insert(55)29φ322623129φφ65412011502φφ22623129φφx=65: left-right case55155412011501φφ22623129φφ65Done3φFigure 7: Illustration of AVL Tree Insert Pro c ess . Note that node x is left-heavy.Comment 1. In general, process may need several rotations before an Insert is completed.Comment 2. Delete(-min) harder but possible.6Lecture 4 Balanced Binary Search Trees 6.006 Fall 2009Balanced Search Trees:There are many balanced search trees.AVL Trees Adel’son-Velsii and Landis 1962B-Trees/2-3-4 Trees Bayer and McCreight 1972 (see CLRS 18)BB[α] Trees Nievergelt and Reingold 1973Red-black Trees CLRS Chapter 13Splay-Trees Sleator and Tarjan 1985Skip Lists Pugh 1989Scapegoat Trees Galperin and Rives t 1993Treaps Seidel and Aragon 1996Note 1. Skip Lists and Treaps use random numbers to make decisions fast with highprobability.Note 2. Splay Trees and Scapegoat Trees are “amortized”: adding up costs for severaloperations =⇒ fast on average.7Lecture 4 Balanced Binary Search Trees 6.006 Fall 2009Splay TreesUpon access (search or insert), move node to root by sequence of rotations and/or double-rotations (just like AVL trees). Height can be linear but still O(lg n) per operation “onaverage” (amortized)Note: We will see more on amortization in a couple of lectures.Optimality• For BSTs, cannot do better than O(lg n) per search in worst case.• In some cases, can do better e.g.– in-order traversal takes Θ(n) time for n elements.– put more frequent items near rootA Conjecture: Splay trees are O(best BST) for every access pattern.• With fancier tricks, can achieve O(lg lg u) performance for integers 1 ···u [Van ErndeBoas; see 6.854 or 6.851 (Advanced Data Structures)]Big Picture:Abstract Data Type(ADT): interface spec.e.g. Priority Queue:• Q = new-empty-queue()• Q.insert(x)• x = Q.deletemin()vs.Data Structure (DS): algorithm for each op.There are many possible DSs for one ADT. One example that we will discuss much later inthe course is the “heap” priority
View Full Document
Unlocking...