AVL Trees PDF

AVL Search Trees What is an AVL Tree? AVL Tree Implementation. Why AVL Trees? Rotations.  What is an AVL Tree? An AVL tree is a binary search tree with a height balance property: For each node v, the heights of the subtrees of v differ by at most 1....

AVL Search Trees What is an AVL Tree? AVL Tree Implementation. Why AVL Trees? Rotations.  What is an AVL Tree? An AVL tree is a binary search tree with a height balance property: For each node v, the heights of the subtrees of v differ by at most 1. A subtree of an AVL tree is also an AVL tree. For each node of an AVL tree: Balance factor = height(right subtree) - height(left subtree) An AVL node can have a balance factor of -1, 0, or +1. 7 -1 7 -1 -1 3 10 1 -2 3 10 1 1 1 4 0 13 0 1 1 13 0 AVL Tree Not an AVL Tree 2 0 2 0  AVL Trees Implementation public class AVLTree extends BinarySearchTree{ protected int height; public AVLTree(){ height = -1;} public int getHeight(){ return height } ; protected void adjustHeight(){ if(isEmpty()) height = -1; else height = 1 + Math.max(left.getHeight() , right.getHeight()); } protected int getBalanceFactor(){ if( isEmpty()) return 0; else return right.getHeight() - left.getHeight(); } //... }  Why AVL Trees? Insertion or deletion in an ordinary Binary Search Tree can cause large imbalances. In the worst case searching an imbalanced Binary Search Tree is O(n). An AVL tree is rebalanced after each insertion or deletion. The height-balance property ensures that the height of an AVL tree with n nodes is O(log n). Searching, insertion, and deletion are all O(log n).  What is a Rotation? A rotation is a process of switching children and parents among two or three adjacent nodes to restore balance to a tree. An insertion or deletion may cause an imbalance in an AVL tree. The deepest node, which is an ancestor of a deleted or an inserted node, and whose balance factor has changed to -2 or +2 requires rotation to rebalance the tree. 50 -1 -2 50 Insert 35 -1 45 78 0 -2 45 78 0 0 40 -1 40 0 35 Deepest unbalanced node  What is a Rotation? (contd.) -2 -1 50 50 rotation -2 45 78 0 0 40 78 0 -1 40 0 35 45 0 0 35 There are two kinds of single rotation: Right Rotation. Left Rotation. A double right-left rotation is a right rotation followed by a left rotation. A double left-right rotation is a left rotation followed by a right rotation.  Single Right Rotation Single right rotation: The left child x of a node y becomes y's parent. y becomes the right child of x. The right child T2 of x, if any, becomes the left child of y. deepest unbalanced node a right rotation of x about y y x x y T3 T1 T1 T2 T2 T3 Note: The pivot of the rotation is the deepest unbalanced node  Single Left Rotation Single left rotation: The right child y of a node x becomes x's parent. x becomes the left child of y. The left child T2 of y, if any, becomes the right child of x. deepest unbalanced node a left rotation of y about x x y y x T1 T3 T2 T3 T1 T2 Note: The pivot of the rotation is the deepest unbalanced node  Single Right Rotation Implementation protected void rightRotate(){ if( isEmpty()) throw new InvalidOperationException(); BinaryTree temp = right; right = left; left = right.left; right.left = right.right; right.right = temp; Object tmpObj = key; key = right.key; right.key = tempObj; getRightAVL().adjustHeight(); adjustHeight(); } Single Right Rotation Implementation (example) Single Right Rotation Implementation (example) contd Single Right Rotation Implementation (example) contd Single Right Rotation Implementation (example) contd Single Right Rotation Implementation (example) contd Single Right Rotation Implementation (example) contd Single Right Rotation Implementation (example) contd Single Right Rotation Implementation (example) contd Single Right Rotation Implementation (example) contd Single Right Rotation Implementation (example) contd  Double Right-Left Rotation x deepest unbalanced node x z right rotation of y about z y y T1 z T1 T4 T2 T2 T3 T3 T4 y left rotation of Y about X Note: First pivot is the right child of the deepest x z unbalanced node; second pivot is the deepest unbalanced node T1 T2 T3 T4  Double Left-Right Rotation x deepest unbalanced node x v left rotation of w about v w w v T4 T4 T1 T3 T2 T3 T1 T2 w left rotation of W about X Note: First pivot is the left child of the deepest v x unbalanced node; second pivot is the deepest unbalanced node T1 T2 T3 T4  Double Rotation implementation 1 protected void rotateRightLeft() 2 { 3 if( isEmpty()) 4 throw new InvalidOperationException(); 5 getRightAVL().rotateRight(); 6 rotateLeft(); 7 } 1 protected void rotateLeftRight() 2 { 3 if( isEmpty()) 4 throw new InvalidOperationException(); 5 getLeftAVL().rotateLeft(); 6 rotateRight(); 7 }  BST ordering property after a rotation A rotation does not affect the ordering property of a BST (Binary Search Tree). y x a right rotation of x about y x y T3 T1 T1 T2 T2 T3 BST ordering property requirement: BST ordering property requirement: T1 < x < y T1 < x < y x < T2 < y Similar x < T2 < y x < y < T3 x < y < T3 Similarly for a left rotation.  AVL Search Trees Inserting in an AVL tree Insertion implementation Deleting from an AVL tree  Insertion Insert using a BST insertion algorithm. Rebalance the tree if an imbalance occurs. An imbalance occurs if a node's balance factor changes from -1 to -2 or from+1 to +2. Rebalancing is done at the deepest or lowest unbalanced ancestor of the inserted node. There are three insertion cases: 1. Insertion that does not cause an imbalance. 2. Same side (left-left or right-right) insertion that causes an imbalance. Requires a single rotation to rebalance. 3. Opposite side (left-right or right-left) insertion that causes an imbalance. Requires a double rotation to rebalance.  Insertion: case 1 Example: An insertion that does not cause an imbalance. Insert 14  Insertion: case 2 Case 2a: The lowest node (with a balance factor of -2) had a taller left-subtree and the insertion was on the left-subtree of its left child. Requires single right rotation to rebalance. -2 -1 right rotation, with node 10 as pivot Insert 3  Insertion: case 2 (contd) Case 2b: The lowest node (with a balance factor of +2) had a taller right-subtree and the insertion was on the right-subtree of its right child. Requires single left rotation to rebalance. +2 +1 left rotation, with node 30 Insert 45 as the pivot  Insertion: case 3 Case 3a: The lowest node (with a balance factor of -2) had a taller left-subtree and the insertion was on the right-subtree of its left child. Requires a double left-right rotation to rebalance. -2 +1 Insert 7 left rotation, with node 5 as the pivot right rotation, with node 10 as the pivot  Insertion: case 3 (contd) Case 3b: The lowest node (with a balance factor of +2) had a taller right-subtree and the insertion was on the left-subtree of its right child. Requires a double right-left rotation to rebalance. +2 -1 Insert 15 right rotation, with node 16 as the pivot left rotation, with node 9 as the pivot  AVL Rotation Summary -2 -2 +2 +2 -1 +1 +1 -1 Single Double Single Double right left-right left right-left rotation rotation rotation rotation  Insertion Implementation The insert method of the AVLTree class is: public void insert(Comparable comparable){ super.insert(comparable); balance(); } Recall that the insert method of the BinarySearchTree class is: public void insert(Comparable comparable){ if(isEmpty()) attachKey(comparable); else { Comparable key = (Comparable) getKey(); if(comparable.compareTo(key)==0) throw new IllegalArgumentException("duplicate key"); else if (comparable.compareTo(key) 0) rotateLeft(); else rotateRightLeft(); } }  Deletion Delete by a BST deletion by copying algorithm. Rebalance the tree if an imbalance occurs. There are three deletion cases: 1. Deletion that does not cause an imbalance. 2. Deletion that requires a single rotation to rebalance. 3. Deletion that requires two or more rotations to rebalance. Deletion case 1 example: Delete 14  Deletion: case 2 examples Delete 40 right rotation, with node 35 as the pivot Deletion: case 2 examples (contd) Delete 32 left rotation, with node 44 as the pivot Deletion: case 3 examples Delete 40 right rotation, with node 35 as the pivot right rotation, with node 30 as the pivot 0