Efficient Top-Down Updating of Red-Black Trees
Report ID: TR-006-85Author: Tarjan, Robert E.
Date: 1985-06-00
Pages: 18
Download Formats: |PDF|
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.