Topics

Last lecture

• Running times of operations supported by a BST: Min, Max, Search, Pre-decessor, Successor, Delete
• Worst case running time of search on a BST
• Running time of BST operations in terms of the height of the tree

This lecture

• Balanced BSTs
• Running time complexity for some balanced BSTs
• Using the STL set ADT