Red-black trees with constant update time

摘要

We show how a few modifications to the red-black trees allow for constant worst-case update time (once the position of the element to be inserted or deleted 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 worst-case update time, our tree is the first to provide a tailored deletion procedure without using the global rebuilding technique. In addition, our procedures are simpler and allow for an easier proof of correctness than those alternative trees.