# Learning Augmented Binary Search Trees

arXiv: https://arxiv.org/abs/2206.12110 · HTML: https://mlsanity.com/paper/2206.12110/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2022.

## Built on by (most cited first, 30 of 31)

- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Learning-Augmented Algorithms for the Bahncard Problem](https://mlsanity.com/paper/2410.15257/) (2024)
- [On Tradeoffs in Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.12770/) (2025)
- [Algorithms with Calibrated Machine Learning Predictions](https://mlsanity.com/paper/2502.02861/) (2025)
- [Robust Learning-Augmented Dictionaries](https://mlsanity.com/paper/2402.09687/) (2024)
- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [Learning-Based Algorithms for Graph Searching Problems](https://mlsanity.com/paper/2402.17736/) (2024)
- [Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search](https://mlsanity.com/paper/2502.05720/) (2025)
- [On the Power of Learning-Augmented Search Trees](https://mlsanity.com/paper/2211.09251/) (2022)
- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)
- [Robustifying Learning-Augmented Caching Efficiently without Compromising 1-Consistency](https://mlsanity.com/paper/2507.16242/) (2025)
- [Learning-Augmented Online Bidding in Stochastic Settings](https://mlsanity.com/paper/2510.25582/) (2025)
- [Warm-starting Push-Relabel](https://mlsanity.com/paper/2405.18568/) (2024)
- [Learning-Augmented Moment Estimation on Time-Decay Models](https://mlsanity.com/paper/2603.02488/) (2026)
- [Connectivity Oracles for Predictable Vertex Failures](https://mlsanity.com/paper/2312.08489/) (2023)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Discovering Data Structures: Nearest Neighbor Search and Beyond](https://mlsanity.com/paper/2411.03253/) (2024)
- [On multiagent online problems with predictions](https://mlsanity.com/paper/2507.12486/) (2025)
- [Privacy-Preserving Learning-Augmented Data Structures](https://mlsanity.com/paper/2510.00165/) (2025)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [Robust and Consistent Ski Rental with Distributional Advice](https://mlsanity.com/paper/2603.29233/) (2026)
- [Incremental Strongly Connected Components with Predictions](https://mlsanity.com/paper/2604.26062/) (2026)

## Abstract (arXiv)

A treap is a classic randomized binary search tree data structure that is easy to implement and supports O(log n) expected time access. However, classic treaps do not take advantage of the input distribution or patterns in the input. Given recent advances in algorithms with predictions, we propose pairing treaps with machine advice to form a learning-augmented treap. We are the first to propose a learning-augmented data structure that supports binary search tree operations such as range-query and successor functionalities. With the assumption that we have access to advice from a frequency estimation oracle, we assign learned priorities to the nodes to better improve the treap's structure. We theoretically analyze the learning-augmented treap's performance under various input distributions and show that under those circumstances, our learning-augmented treap has stronger guarantees than classic treaps and other classic tree-based data structures. Further, we experimentally evaluate our learned treap on synthetic datasets and demonstrate a performance advantage over other search tree data structures. We also present experiments on real world datasets with known frequency estimation oracles and show improvements as well.