What is a red-black tree?
The red-black tree is another member of the binary search tree family. Like the AVL tree, a red-black tree has self-balancing properties.
The structure of a red-black tree follows certain rules to ensure that the tree is always balanced.
Properties of a red-black tree
-
Each tree node is colored either red or black.
-
The root node of the tree is always black.
-
Every path from the root to any of the leaf nodes must have the same number of black nodes.
-
No two red nodes can be adjacent, i.e., a red node cannot be the parent or the child of another red node.
Examples
The tree above ensures that every path from the root to a leaf node has the same amount of black nodes. In this case, there is one (excluding the root node).
There are adjacent black nodes, but no adjacent red nodes.
The tree above does not follow the red-black convention as two red nodes are adjacent to each other. Another problem is that one of the paths to a leaf node has zero black nodes, whereas the other two contain a black node.
Time Complexity
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | O(log n) | O(log n) |
| Insertion | O(log n) | O(log n) |
| Deletion | O(log n) | O(log n) |
Insertion and deletion in a red-black tree works better than the worst case, O(n) , of a BST.
