Fundamental data structures are critical components of the modern computing infrastructure, including databases, file systems, web servers; efficient storage and retrieval is crucial in all data-intensive applications. Besides the immediate practical impact, the design and analysis of data structures has revealed a rich mathematical theory, with connections to combinatorics, information theory, algebra, and analysis.

Adaptive data structures take advantage of regularities in the input, and can be more efficient than what their worst-case analysis would suggest. Binary search trees and heaps are two well-studied and fundamental classes of data structures, with many applications. Self-adjusting trees and heaps are particularly attractive, due to their simplicity. The most prominent data structure in this family is the splay tree, invented by Sleator and Tarjan in 1985. Splay trees have many known adaptive properties, furthermore, they are conjectured to be instance-optimal (i.e. as good on any input as any dynamic tree, up to a constant factor). This is the famous dynamic optimality conjecture. For heaps, several ingenious designs were proposed throughout the years, and Fibonacci heaps and their variants achieve theoretically optimal amortized running times. Compared to search trees, far less is known about the adaptive properties of heaps. In general, self-adjusting data structures are not fully understood, due to the lack of tools for describing their behavior.

The main objective of the project is to deepen the understanding of adaptive data structures, with focus on self-adjusting binary search trees and heaps.