6 Binary Search Trees

This chapter covers balanced binary search trees (BSTs), a data structure that uses a binary tree to implement a set or a map. Balanced BSTs are the first data structure we see that implements the set and map operations efficiently. In a balanced BST, insertion, deletion and lookup all take $O(\log n)$ time.