Understanding Red-Black Trees
Red-Black tree is a binary search tree in which every node is colored with either red or black.
It is a type of self-balancing binary search tree. It has a good efficient worst case running time complexity.
- Complexity guarantees
- Coloring and rotation rules
Rules That Every Red-Black Tree Follows:
- Every node has a color either red or black.
- The root of the tree is always black.
- There are no two adjacent red nodes (A red node cannot have a red parent or red child).
- Every path from a node (including root) to any of its descendants NULL nodes has the same number of black nodes.
- Every leaf (e.i. NULL node) must be colored BLACK.
Learn more about Red-Black Trees