Successor and predecessor Which is the node 15 15s successor 6 18 3 7 17 20 2 13
S dd uccessor an d pre decessor Which is the node 15 Which is the node 15's successor 6 18 3 7 17 20 2 4 13 9
Successor and predecessor 15 6 18 3 7 17 20 2 13 Which is the node 13’ s successor
S dd uccessor an d pre decessor 15 6 18 3 7 17 20 2 4 13 Whi h i th d 9 Whi c h is the no de 13's successor 9
Successor and predecessor TREE-SUCCESSOR(x) 1. if rightIe]≠NIL 2. then return TREE-MINIMUN(righteD 3. y←P 4. while yf nil and x= rightly 5.dox←y y←p[ 7. return Running time O(h)
S dd uccessor an d pre decessor TREE-SUCCESSOR (x ) 1. if rig h t [ x ] ≠ NIL 2. then return TREE-MINIMUN (right [ x]) 3. y ← p [ x ] 4. while y ≠ NIL and x = right [y ] 5. do x ← y 6. y ← p [ x ] 7. return y Running time O ( h )
Constructing Bst TREE-INSERT(T, 2) Running time (9 1.y←NIL OCh 2.x←root们 3. while x≠NIL 5 12 456 doy←x if key{-]≤key{x 6 then x←lef[x 7 else x←righ{x 2 7 9. ify=NiL l0. then root[门← I1. else if key=< keyly 8 then lef[x]←z TREE-INSERT(T, 2) else right{x]←z
C ST onstructing BST TREE INSERT ( T ) R i ti 9 TREE -INSERT ( T, z ) 1. y ← NIL 2 x ← root [ T] Runn ing time O ( h ) 5 12 2. x ← root [ T] 3. while x ≠ NIL 4. do y ← x 1 6 5. if key [ z] < key [ x ] 6. then x ← left [ x ] 7 l i ht [ ] 2 7 7. e lse x ← r ight [ x ] 8. p [ z] ← y 9. if y = NIL 8 9. if y NIL 10. then root [ T] ← z 11. else if key [ z] < key [y ] TREE-INSERT ( T, 2) 12. then left [ x ] ← z 13. else right [ x ] ← z
A nalvSiS After we insert n elements, (1 what is the worst possible BST height? ° Pretty bad:n-1 3 Average: O(nlgn 4 5
A l na ysis y After we insert n elements, what is the worst possible 1 BST height? P bd 1 2 y Pretty bad: n − 1 3 y Average: O(nlgn) 4 y Average: O(nlgn) 5