Balanced Binary Search TreesSlide 2AVL TreesSlide 4Slide 5Slide 6AVL TreeSlide 8Slide 9Slide 10CompSci 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 a “rotation”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 Treesk2k1k1k2CAABB CSingle RotationAlso: mirror imagebeforeafterCompSci 100E41.6AVL 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.7AVL 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.8AVL Treesk3k1k1k3DAABBCDouble RotationAlso: mirror imagebeforeafterk2k2CDCompSci 100E41.9AVL 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.10AVL TreesDeletions can also cause imbalanceUse similar rotations to restore balanceBig
View Full Document