AVL Trees CSE 373 Data Structures Lecture 8 Readings Reading Section 4.4, 12/26/03 AVL Trees - Lecture 2 Binary Search Tree - Best Time All BST operations are O(d), where d is tree depth minimum d is d log2N for a binary tree with N nodes What is the best case tree? What is the worst case tree? So, best case running time of BST operations is O(log N) 12/26/03

AVL Trees - Lecture 3 Binary Search Tree - Worst Time Worst case running time is O(N) What happens when you Insert elements in ascending order? Insert: 2, 4, 6, 8, 10, 12 into an empty BST Problem: Lack of balance: compare depths of left and right subtree Unbalanced degenerate tree 12/26/03 AVL Trees - Lecture 4 Balanced and unbalanced BST 1 4 2

2 5 3 1 4 4 12/26/03 6 3 Is this balanced? 5 2 1 3 5 6 7

AVL Trees - Lecture 7 5 Approaches to balancing trees Don't balance May end up with some nodes very deep Strict balance The tree must always be balanced perfectly Pretty good balance Only allow a little out of balance Adjust on access Self-adjusting 12/26/03 AVL Trees - Lecture 6 Balancing Binary Search Trees Many algorithms exist for keeping binary search trees balanced

Adelson-Velskii and Landis (AVL) trees (height-balanced trees) Splay trees and other self-adjusting trees B-trees and other multiway search trees 12/26/03 AVL Trees - Lecture 7 Perfect Balance Want a complete tree after every operation tree is full except possibly in the lower right This is expensive For example, insert 2 in the tree on the left and then rebuild as a complete tree 6 5 4 1 12/26/03 9 5

8 Insert 2 & complete tree 1 AVL Trees - Lecture 2 8 4 6 8 9 AVL - Good but not Perfect Balance AVL trees are height-balanced binary search trees Balance factor of a node height(left subtree) - height(right subtree) An AVL tree has balance factor calculated at every node

For every node, heights of left and right subtree can differ by no more than 1 Store current heights in each node 12/26/03 AVL Trees - Lecture 9 Height of an AVL Tree N(h) = minimum number of nodes in an AVL tree of height h. Basis N(0) = 1, N(1) = 2 h Induction N(h) = N(h-1) + N(h-2) + 1 Solution (recall Fibonacci analysis) N(h) > h ( 1.62) 12/26/03 AVL Trees - Lecture h-1 10

h-2 Height of an AVL Tree N(h) > h ( 1.62) Suppose we have n nodes in an AVL tree of height h. n > N(h) (because N(h) was the minimum) n > h hence log n > h (relatively well balanced tree!!) h < 1.44 log2n (i.e., Find takes O(logn)) 12/26/03 AVL Trees - Lecture 11 Node Heights Tree A (AVL) height=2 BF=1-0=1 6 1 4 Tree B (AVL)

2 0 1 9 4 6 1 9 0 0 0 0 0 1

5 1 5 8 height of node = h balance factor = hleft-hright empty height = -1 12/26/03 AVL Trees - Lecture 12 Node Heights after Insert 7 Tree A (AVL) 2 6 1 4

Tree B (not AVL) balance factor 1-(-1) = 2 3 1 1 9 4 6 2 9 0 0 0 0

0 1 1 5 7 1 5 8 0 height of node = h balance factor = hleft-hright empty height = -1 12/26/03 AVL Trees - Lecture 7 13

-1 Insert and Rotation in AVL Trees Insert operation may cause balance factor to become 2 or 2 for some node only nodes on the path from insertion point to root node have possibly changed in height So after the Insert, go back up to the root node by node, updating heights If a new balance factor (the difference hlefthright) is 2 or 2, adjust tree by rotation around the node 12/26/03 AVL Trees - Lecture 14 Single Rotation in an AVL Tree 2 6 6 1

2 4 2 1 9 4 1 8 0 0 1 0 0 0

0 1 5 8 1 5 7 9 0 7 12/26/03 AVL Trees - Lecture 15 Insertions in AVL Trees

Let the node that needs rebalancing be . There are 4 cases: Outside Cases (require single rotation) : 1. Insertion into left subtree of left child of . 2. Insertion into right subtree of right child of . Inside Cases (require double rotation) : 3. Insertion into right subtree of left child of . 4. Insertion into left subtree of right child of . The rebalancing is performed through four separate rotation algorithms. 12/26/03 AVL Trees - Lecture 16 AVL Insertion: Outside Case j Consider a valid AVL subtree k h h

h X 12/26/03 Z Y AVL Trees - Lecture 17 AVL Insertion: Outside Case j k h+1 X 12/26/03 Inserting into X destroys the AVL property at node j h h

Z Y AVL Trees - Lecture 18 AVL Insertion: Outside Case j k h+1 X 12/26/03 Do a right rotation h h Z Y AVL Trees - Lecture 19

Single right rotation j k h+1 X 12/26/03 Do a right rotation h h Z Y AVL Trees - Lecture 20 Outside Case Completed Right rotation done! (Left rotation is mirror symmetric) k j

h+1 h h X Y Z AVL property has been restored! 12/26/03 AVL Trees - Lecture 21 AVL Insertion: Inside Case j Consider a valid AVL subtree k

h h h X 12/26/03 Z Y AVL Trees - Lecture 22 AVL Insertion: Inside Case Inserting into Y destroys the AVL property at node j j k h h

X 12/26/03 Does right rotation restore balance? h+1 Z Y AVL Trees - Lecture 23 AVL Insertion: Inside Case k j h X h h+1

Y 12/26/03 Right rotation does not restore balance now k is out of balance AVL Trees - Lecture Z 24 AVL Insertion: Inside Case Consider the structure of subtree Y j k h h X 12/26/03

h+1 Z Y AVL Trees - Lecture 25 AVL Insertion: Inside Case j Y = node i and subtrees V and W k h i h X Z

h or h-1 V 12/26/03 h+1 W AVL Trees - Lecture 26 AVL Insertion: Inside Case j We will do a left-right double rotation . . . k i X V 12/26/03

Z W AVL Trees - Lecture 27 Double rotation : first rotation j i Z k X 12/26/03 left rotation complete W V AVL Trees - Lecture 28 Double rotation : second rotation

j i Z k X 12/26/03 Now do a right rotation W V AVL Trees - Lecture 29 Double rotation : second rotation right rotation complete Balance has been restored i j

k h h h or h-1 X 12/26/03 V W Z AVL Trees - Lecture 30 Implementation balance (1,0,-1) key left right No need to keep the height; just the difference in height,

i.e. the balance factor; this has to be modified on the path of insertion even if you dont perform rotations Once you have performed a rotation (single or double) you wont need to go back up the tree 12/26/03 AVL Trees - Lecture 31 Single Rotation RotateFromRight(n : reference node pointer) { p : node pointer; p := n.right; n n.right := p.left; p.left := n; n := p } You also need to modify the heights or balance factors of n and p 12/26/03 X

AVL Trees - Lecture Y Z 32 Insert Double Rotation Implement Double Rotation in two lines. DoubleRotateFromRight(n : reference node pointer) { ???? n } X Z 12/26/03 AVL Trees - Lecture V W

33 Insertion in AVL Trees Insert at the leaf (as for all BST) only nodes on the path from insertion point to root node have possibly changed in height So after the Insert, go back up to the root node by node, updating heights If a new balance factor (the difference hlefthright) is 2 or 2, adjust tree by rotation around the node 12/26/03 AVL Trees - Lecture 34 Insert in BST Insert(T : reference tree pointer, x : element) : integer { if T = null then T := new tree; T.data := x; return 1;//the links to //children case T.data = T.data > T.data < endcase }

12/26/03 are null x : return 0; //Duplicate do nothing x : return Insert(T.left, x); x : return Insert(T.right, x); AVL Trees - Lecture 35 Insert in AVL trees Insert(T : reference tree pointer, x : element) : { if T = null then {T := new tree; T.data := x; height := 0; return;} case T.data = x : return ; //Duplicate do nothing T.data > x : Insert(T.left, x); if ((height(T.left)- height(T.right)) = 2){ if (T.left.data > x ) then //outside case T = RotatefromLeft (T); else //inside case T = DoubleRotatefromLeft (T);} T.data < x : Insert(T.right, x); code similar to the left case Endcase

T.height := max(height(T.left),height(T.right)) +1; return; } 12/26/03 AVL Trees - Lecture 36 Example of Insertions in an AVL Tree 2 0 10 20 30 0 25 12/26/03 Insert 5, 40

1 0 35 AVL Trees - Lecture 37 Example of Insertions in an AVL Tree 2 1 10 20 0 0 5 25 1

1 30 10 0 35 0 20 5 3 2 30 0 1 25 35

0 40 Now Insert 45 12/26/03 AVL Trees - Lecture 38 Single rotation (outside case) 3 1 10 20 0 0 5 25

2 1 30 10 2 0 35 20 3 2 30 0 5 40 1 25 0

Imbalance 12/26/03 35 1 40 0 45 0 Now Insert 34 AVL Trees - Lecture 39 45 Double rotation (inside case) 3 1 20

10 0 5 Imbalance 0 3 1 30 10 2 40 0 25 20 3

2 35 1 5 40 1 30 0 1 Insertion of 34 0 12/26/03 35 45 0 0 25 34 AVL Trees - Lecture

40 34 45 AVL Tree Deletion Similar but more complex than insertion Rotations and double rotations needed to rebalance Imbalance may propagate upward so that many rotations may be needed. 12/26/03 AVL Trees - Lecture 41 Pros and Cons of AVL Trees Arguments for AVL trees: 1. Search is O(log N) since AVL trees are always balanced. 2. Insertion and deletions are also O(logn) 3. The height balancing adds no more than a constant factor to the speed of insertion. Arguments against using AVL trees: 1. Difficult to program & debug; more space for balance factor.

2. Asymptotically faster but rebalancing costs time. 3. Most large searches are done in database systems on disk and use other structures (e.g. B-trees). 4. May be OK to have O(N) for a single operation if total run time for many consecutive operations is fast (e.g. Splay trees). 12/26/03 AVL Trees - Lecture 42 Double Rotation Solution DoubleRotateFromRight(n : reference node pointer) { RotateFromLeft(n.right); n RotateFromRight(n); } X Z V 12/26/03 AVL Trees - Lecture W

43