  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.
