Red-black trees
A Red-black tree, also referred to as an RBT, is the next variant of the self-balancing binary search trees. As a variant of BSTs, this data structure requires that the standard BST rules be maintained. Moreover, the following rules must be taken into account:
- Each node must be colored either red or black. Thus, you need to add additional data for a node that stores a color.
- All nodes with values cannot be leaf nodes. For this reason, the NIL pseudo-nodes should be used as leaves in the tree, while all other nodes are internal ones. Moreover, all NIL pseudo-nodes must be black.
- If a node is red, both its children must be black.
- For any node, the number of black nodes on the route to a descendant leaf (that is, the NIL pseudo-node) must be the same.
The proper RBT is presented in the following diagram:
The tree consists of nine nodes, each colored red or black. It is worth mentioning the NIL pseudo-nodes, which are added as leaf nodes. If you again take a look at the set of rules...
