Efficient Top-Down Updating of Red-Black Trees

Abstract:

The red-black tree is an especially flexible and efficient form of binary search tree. In this note we show that an insertion or deletion in a red-black tree can be performed in one top-down pass, requiring O(1) rotations and color changes in the amortized case.