The structure of a red-black tree follows certain rules to ensure that the tree is always balanced.
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.
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.
|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.