C# Data Structures and Algorithms

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) ...