information:classification, structural:expansion, stylistic:tone
Operations

The read-only operations, such as search or tree traversal, on a red–black tree require no modification from those used for binary search trees, because every red–black tree is a special case of a simple binary search tree. However, the immediate result of an insertion or removal may violate the properties of a red–black tree, the restoration of which is called rebalancing so that red–black trees become self-balancing. It requires in the worst case a small number, O (log n) {\displaystyle O(\log n)} in Big O notation, where n {\displaystyle n} is the number of objects in the tree, on average or amortized O (1) {\displaystyle O(1)}, a constant number, of color changes (which are very quick in practice); and no more than three tree rotations (two for insertion).

If the example implementation below is not suitable, other implementations with explanations may be found in Ben Pfaff’s annotated C library GNU libavl (v2.0.3 as of June 2019).

The details of the insert and removal operations will be demonstrated with example C++ code, which uses the type definitions, macros below, and the helper function for rotations: