Robert Tarjan: “Binary Search Trees” 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. The opinions expressed in this video do not necessarily reflect the views of the Heidelberg Laureate Forum Foundation or any other person or associated institution involved in the making and distribution of the video.