7.1. Chapter Introduction: 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.