Red-Black Trees
Red-black trees are one of many search-tree schemes that are balanced in order to guarantee that basic dynamic-set operations take $Θ(log_2 \;n)$ time in the worst case. [1] A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK. Every red-black tree should satisfy the following red-black properties: [1] Every node is either red or black. The root is black. Every leaf ( NIL ) is black. If a node is red, then both its children are black. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. As a matter of convenience in dealing with boundary conditions in red-black tree code, we use a single sentinel to represent NIL. Its color attribute is BLACK , and its other attributes - p, left, right, and key—can take on arbitrary values. Although we instead could add a distinct sentinel node for each NIL in the tree, so that the parent of each NIL is well defined, t