Lecture: Binary Search Tree

Robert Endre Tarjan

Abstract:

The binary search tree is one of the most fundamental data structures in computer science, with many applications. Binary search trees support binary search in a set of totally ordered items, and ideally reduce search time from linear to logarithmic. A central question is how to keep such a tree balanced in the presence of updates. The first solution was offered by Adelson-Velskii and Landis in 1962. In spite of a huge volume of work during the intervening 64 years, the design space is rich, and basic questions remain open, notably how best to make a search tree adapt to its usage pattern. In this talk I’ll explore relatively recent new work and interesting open problems.

---