6.006 Lecture 6: AVL Trees, AVL Sort

Lecture 6 Balanced Binary Search Trees 6.006 Fall 2011 Lecture 6: Balanced Binary Search Trees Lecture Overview • The importance of being balanced • AVL trees – Definition and balance – Rotations – Insert • Other balanced trees • Data structures in general • Lower bounds Recall: Binary Search Trees (BSTs) • rooted binary tree • each node has – key – left pointer – right pointer – parent pointer See Fig. 1 3 41 65 1 2 20 0 11 1 26 29 50 0 0 Figure 1: Heights of nodes in a BST 1 Lecture 6 Balanced Binary Search Trees 6.006 Fall 2011 x ≤x ≥x Figure 2: BST property • BST property (see Fig. 2). • height of node = length (# edges) of longest downward path to a leaf (see CLRS B.5 for details). The Importance of Being Balanced: • BSTs support insert, delete, min, max, next-larger, next-smaller, etc. in O(h) time, where h = height of tree (= height of root). • h is between lg n and n: Fig. 3. vs. Perfectly Balanced Path Figure 3: Balancing BSTs • balanced BST maintains h = O(lg n) ⇒ all operations run in O(lg n) time. 2 Lecture 6 Balanced Binary Search Trees 6.006 Fall 2011 AVL Trees: Adel’son-Vel’skii & Landis 1962 For every node, require heights of left & right children to differ by at most ±1. • treat nil tree as height -1 • each node stores its height (DATA STRUCTURE AUGMENTATION) (like subtree size) (alternatively, can just store difference in heights) This is illustrated in Fig. 4 k-1 k Figure 4: AVL Tree Concept Balance: Worst when every node differs by 1 — let Nh = (min.) # nodes in height-h AVL tree =⇒ Nh = Nh−1 + Nh−2 + 1 > 2Nh−2 =⇒ Nh > 2h/2 =⇒ h < 2 lg Nh Alternatively: Nh > Fh (nth Fibonacci number) • In fact Nh = Fn+1 − 1 (simple induction) √ ϕh 1+ 5 ≈ 1.618 (golden ratio) • Fh = √ rounded to nearest integer where ϕ = 2 5 • =⇒ max. h ≈ logϕ n ≈ 1.440 lg n 3 Lecture 6 Balanced Binary Search Trees 6.006 Fall 2011 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 x k-1 y y k-1 Left-Rotate(x) k+1 A C B k k k-1 x k k-1 B A x k-1 y z A k C C B k-1 k x k+1 Left-Rotate(x) k+1 k k A C B Figure 5: AVL Insert Balancing • else: follow steps in Fig. 6 x k-1 y z A k Right-Rotate(z) Left-Rotate(x) k+1 k k+1 z x k-1 y D k-1 k-1 A B or k-2 C k D k-1 k-1 B or k-2 C Figure 6: AVL Insert Balancing • then continue up to x’s grandparent, greatgrandparent . . . 4 Lecture 6 Balanced Binary Search Trees 6.006 Fall 2011 Example: An example implementation of the AVL Insert process is illustrated in Fig. 7 x = 29: left-left case Insert(23) 3 41 65 1 2 20 0 11 41 50 0 1 29 0 11 0 23 Done Insert(55) 3 41 3 41 2 20 65 1 2 20 50 0 1 26 0 11 29 0 0 23 0 23 Done 3 41 0 23 2 20 2 65 1 26 50 0 29 0 41 2 20 65 1 1 26 x=65: left-right case 11 0 50 0 2 29 1 26 26 0 0 11 65 1 20 50 1 29 0 11 0 55 0 1 26 0 23 1 55 0 50 0φ65 29 0 Figure 7: Illustration of AVL Tree Insert Process Comment 1. In general, process may need several rotations before done with an Insert. Comment 2. Delete(-min) is similar — harder but possible. 5 Lecture 6 Balanced Binary Search Trees 6.006 Fall 2011 AVL sort: • insert each item into AVL tree Θ(n lg n) Θ(n) Θ(n lg n) • in-order traversal Balanced Search Trees: There are many balanced search trees. AVL Trees B-Trees/2-3-4 Trees BB[α] Trees Red-black Trees (A) — Splay-Trees (R) — Skip Lists (A) — Scapegoat Trees (R) — Treaps Adel’son-Velsii and Landis 1962 Bayer and McCreight 1972 (see CLRS 18) Nievergelt and Reingold 1973 CLRS Chapter 13 Sleator and Tarjan 1985 Pugh 1989 Galperin and Rivest 1993 Seidel and Aragon 1996 (R) = use random numbers to make decisions fast with high probability (A) = “amortized”: adding up costs for several operations =⇒ fast on average For example, Splay Trees are a current research topic — see 6.854 (Advanced Algorithms) and 6.851 (Advanced Data Structures) Big Picture: Abstract Data Type(ADT): interface spec. vs. Data Structure (DS): algorithm for each op. There are many possible DSs for one ADT. One example that we will discuss much later in the course is the “heap” priority queue. Priority Queue ADT Q = new-empty-queue() Q.insert(x) x = Q.deletemin() x = Q.findmin() heap Θ(1) Θ(lg n) Θ(lg n) Θ(1) 6 AVL tree Θ(1) Θ(lg n) Θ(lg n) Θ(lg n) → Θ(1) Lecture 6 Balanced Binary Search Trees Predecessor/Successor ADT S = new-empty() S.insert(x) S.delete(x) y = S.predecessor(x) → nextsmaller y = S.successor(x) → next-larger heap Θ(1) Θ(lg n) Θ(lg n) Θ(n) AVL tree Θ(1) Θ(lg n) Θ(lg n) Θ(lg n) Θ(n) Θ(lg n) 7 6.006 Fall 2011