Red-Black Trees with Constant Update Time

Amr Elmasry, Mostafa Kahla, Fady Ahdy +1

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 struct…