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 : O(___) ?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.2Balanc ed 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 restore balance to the treeCompSci 100E41.4AVL TreesSingle RotationAn insertion into the left subtree of the left child of tree Adapted from Weiss, pp 567-568/** Used if insert has caused loss of balance at k2 * (Also used as part of double rotation operations) * @return root of adjusted tree */TNode rotateWithLeftChild(TNode k2){ 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 case/** Used if insert has caused loss of balance at k2 * (Also used as part of double rotation operations) * @return root of adjusted tree */TNode rotateWithRightChild(TNode k2){ 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) * @return root of adjusted tree */TNode doubleRotateWithLeftChild(TNode k3) { 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/** Used after insertion into right subtree, k2, * of right child, k1, of k3 (if it has caused * loss of balance) * @return root of adjusted tree */TNode doubleRotateWithRightChild(TNode k3) { k3.right = rotateWithLeftChild(k3.right); return rotateWithRightChild(k3); }CompSci 100E41.12AVL TreesDeletions can also cause imbalanceUse similar rotations to restore balanceBig Oh?That was the “big picture”How can we insure performance?Think about some of the implementation
View Full Document