Self-Balancing Binary Search Tree

Red-Black Tree

The nodes in a red-black tree hold an extra “color” bit, often drawn as red and black, which help ensure that the tree is always approximately balanced.

Resources

• https://en.wikipedia.org/wiki/Red%E2%80%93black_tree