Home PageTitle PageContentsJJ IIJ IPage 1 of 13Go BackFull ScreenCloseQuitIntroduction to Balanced Search Trees• Want to guarantee worst case time O(log n) for dictionary opera-tions on ordered data, irrespective of what sequence the operationscome in (Vanilla BST is embarrassing when data is in increasingorder)• Possible balanced or approximately balanced choices include– B-Trees: Great for large amounts of data. Internal nodes arenot fully “occupied,” however.– Bottom Up Red-Black Tree: Somewhat mysterious update oper-ations. Difficult to handle the several cases. Two pass algorithms– Top-Down Red-Black Trees: One pass algorithm, difficult tohandle delete– BB-trees, AA-trees: Two pass algorithms.– AVL trees: Simplest next step after BST. One functionrestructure(x) takes care of all cases. Two pass algorithm.Home PageTitle PageContentsJJ IIJ IPage 2 of 13Go BackFull ScreenCloseQuitAVL Tree Is Simple To Describe• An AVL tree T is a binary search tree (BST) such that for everyinternal node v the heights of the children of v differ at most by 1• The height of an empty tree (possible only in improper binary trees)is -1. Heights often explicitly stored in each node• v is said to be balanced, even though it is only approximately bal-anced• Main trick: Keep nodes balanced as dynamic insert() and remove()operations are called. Difficult to ensure if we insist on exact balanceHome PageTitle PageContentsJJ IIJ IPage 3 of 13Go BackFull ScreenCloseQuitAVL Tree Height is O(log n)• The balance restriction is good enough• Let n(h) be the minimum number of internal nodes of an AVL treeof height h– n(1) = 1 and n(2) = 2– For n > 2, an AVL tree of height h contains the root node, anda child of height h − 1.– The other child cannot have arbitrary height. Due to the AVLrestriction, the height can be only h − 1 or h − 2.– n(h) measures minimum and n(h − 2) < n(h − 1)– Both children are roots of AVL trees– Therefore n(h) = 1 + n(h − 1) + n(h − 2) > 2n(h − 2)• Solving n(h) ≥ 2h2−1or h < 2 log n(h) − 2Home PageTitle PageContentsJJ IIJ IPage 4 of 13Go BackFull ScreenCloseQuitInsertion• General idea: Insert a node at the leaf level which changes theheight of at most O(log n) nodes• Nodes on the path from the newly created inserted key to the rootmay have increased heights– Let x be the node (with parent y) such that its grandparent zis the first unbalanced node– The O(1) local procedure restructure(x) involving x, y, andz fixes the height of z• In fact, for insertion, this procedure will fix the height of everyunbalanced nodeHome PageTitle PageContentsJJ IIJ IPage 5 of 13Go BackFull ScreenCloseQuitrestructure(x) Is EasyFive simple steps to understand the rearrangement1. Identify x, y and z. Let abc be the order in which x, y and z showup in an inorder listing. (Thus a is one of x or y or z).2. Identify the four subtrees of the children of x, y and z. LetT 0, T 1, T 2, T 3 be the order in which these trees show up in aninorder listing.3. Replace the data at the subtree rooted at z by b.4. b.left := a; a.left := T0; a.right := T1;5. b.right := c; c.left := T2; c.right := T3;Home PageTitle PageContentsJJ IIJ IPage 6 of 13Go BackFull ScreenCloseQuitrestructure(x) Is EasyThe zig-zag caseThe zig-zig caseHome PageTitle PageContentsJJ IIJ IPage 7 of 13Go BackFull ScreenCloseQuitRemove Also Uses restructure(x)• General idea: Follow the vanilla BST procedure for removal. Finallyremove a node at the leaf level which potentially changes the heightof at most O(log n) nodes• Nodes on the path from the position of the deleted key to the rootmay have decreased heights• But in fact at most one node z can become unbalanced– Let y be the taller child of z.– Let x be the taller child of y. (If both children are equally tall,pick x so that x, y and z are in a “straight line” (zig-zig case).– restructure(x) fixes the height of z but may cause parent ofz to become unbalanced• Repeat the above procedure at most O(log n) timesHome PageTitle PageContentsJJ IIJ IPage 8 of 13Go BackFull ScreenCloseQuitZigZag and ZigZig RemovalThe zig-zag caseThe zig-zig caseHome PageTitle PageContentsJJ IIJ IPage 9 of 13Go BackFull ScreenCloseQuitExample: Cascaded RemovalHome PageTitle PageContentsJJ IIJ IPage 10 of 13Go BackFull ScreenCloseQuitPseudocode for Update Operationsvoid insertAVL ( Key k ) {node pos = insertBST ( k , ro o t ) ;r e p l a c e ( pos , new AVLItem ( k , 1 ) ;// AVL t r e e s have h ei gh t , BST don ’ tr eb a la n ce ( pos ) ;}Object removeAVL ( Key k ) {Object t = removeBST ( k , r oo t ) ;i f ( t ! = NO SUCH KEY) {r eb a la n ce ( ( node ) t ) ;}return t ;Home PageTitle PageContentsJJ IIJ IPage 11 of 13Go BackFull ScreenCloseQuitPseudocode for Update Operationsvoid reb ala n ce ( node z ) {// t r a v e r s e path from z to roo t// to s t a r t o f , z i s the p oi nt of i n s e r t or remove// and i s never unbalancedwhile ( ! isRoot ( z ) ) {z = z . parent ( ) ;set He igh t ( z ) ;// i n s e r t or remove may have caused the h ei g ht to changei f ( ! is Ba la nc ed ( z ) ) {node x = z . t a l l e r C h i l d ( ) . t a l l e r C h i l d ( ) ;z = r e s t r u c t u r e ( x ) ; // s e e e a r l i e r d e s c r i p t i o nset He igh t ( z . l e f t c h i l d ( ) ) ; s et He i gh t ( z . r i g h t c h i l d ( ) ) ;set He igh t ( z ) ;}// he ig h t o f par ent o f z may need to be changed}}Home PageTitle PageContentsJJ IIJ IPage 12 of 13Go BackFull ScreenCloseQuitPseudocode for Update Operationsnode t a l l e r C h i l d ( node p ) {i f ( p . l e f t c h i l d . h ei ght () > p . r i g h t c h i l d . h e ig ht ( ) )return p . l e f t c h i l d ;i f ( p . l e f t c h i l d . h ei ght () < p . r i g h t c h i l d . h e ig ht ( ) )return p . r i g h t c h i l d ;i f ( p …