Balanced Binary Search TreesSlide 2AVL TreesSlide 4Slide 5Slide 6Slide 7AVL TreeSlide 9Slide 10Slide 11Slide 12CompSci 100E41.1Balanced Binary Search TreesPathological BSTInsert nodes from ordered list Search: O(___) ?The Balanced TreeBinary Tree is balanced if height of left and right subtree differ by no more than one, recursively for all nodes. (Height of empty tree is -1) ExamplesCompSci 100E41.2Balanced Binary Search TreesKeeping BSTrees Balanced Keeps find, insert, delete O(log(N)) worst case. Pay small extra amount at each insertion to keep it balanced Several Well-known Systems Exist for ThisAVL TreesRed-Black Trees. . .Will look at AVL TreesCompSci 100E41.3AVL TreesAVL TreesAdelson-Velskii and Landis Discovered ways to keep BSTrees BalancedInsertionsInsert into BST in normal wayIf tree no longer balanced, perform “rotation(s)”Rotations leave the tree balanced againCompSci 100E41.4AVL TreesSingle RotationAn insertion into the left subtree of the left child of tree Adapted from Weiss, pp 567-568// Used if it has caused loss of balance) // (Also used as part of double rotation operations) Tnode rotateWithLeftChild(TNode k2)//post: returns root of adjusted tree { TNode k1 = k2.left; k2.left = k1.right; k1.right = k2; return k1; }CompSci 100E41.5AVL TreesSingle RotationCompSci 100E41.6AVL Treesk2k1k1k2CAABB CSingle RotationAlso: mirror imagebeforeafterCompSci 100E41.7AVL TreesSingle RotationMirror image caseTNode rotateWithRightChild(TNode k2)//post: returns root of adjusted tree { TNode k1 = k2.right; k2.right = k1.left; k1.left = k2; return k1; }CompSci 100E41.8AVL TreeDouble RotationAn insertion into the right subtree of the left child of tree Adapted from Weiss, p 57// Used after insertion into right subtree, k2,// of left child, k1, of k3 (if it has caused// loss of balance) TNode doubleRotateWithLeftChild(TNode k3) //post: returns root of adjusted tree { k3.left = rotateWithRightChild(k3.left); return rotateWithLeftChild(k3); }CompSci 100E41.9AVL TreeDouble RotationCompSci 100E41.10AVL Treesk3k1k1k3DAABBCDouble RotationAlso: mirror imagebeforeafterk2k2CDCompSci 100E41.11AVL TreeDouble RotationAn insertion into the right subtree of the left child of tree Adapted from Weiss, p 571// Mirror ImageTNode doubleRotateWithRightChild(TNode k3) //post: returns root of adjusted tree { k3.right = rotateWithLeftChild(k3.right); return rotateWithRightChild(k3); }CompSci 100E41.12AVL TreesDeletions can also cause imbalanceUse similar rotations to restore balanceBig
View Full Document