# Red-Black Trees with Constant Update Time

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2018.

## Built on by (most cited first, 1 of 1)

- [Integrating Human Feedback into a Reinforcement Learning-Based Framework for Adaptive User Interfaces](https://mlsanity.com/paper/2504.20782/) (2025)

## Abstract (arXiv)

We show how a few modifications to the red-black trees allow for O(1) worst-case update time (once the position of the inserted or deleted element is known). The resulting structure is based on relaxing some of the properties of the red-black trees while guaranteeing that the height remains logarithmic with respect to the number of nodes. Compared to the other search trees with constant update time, our tree is the first to provide a tailored deletion procedure without using the global rebuilding technique. In addition, our structure is very simple to implement and allows for a simpler proof of correctness than those alternative trees.