Red-black tree
An AVL tree guarantees logarithmic insertion, deletion, and search. But it makes a lot of rotations. In most applications, insertions are randomly ordered and so are deletions. So, the trees would sort of balance out eventually. However, since the AVL tree is too quick to rotate, it may make very frequent rotations in opposite directions even when it would be unnecessary, had it been waiting for the future values to be inserted. This can be avoided using a different approach: knowing when to rotate a subtree. This approach is called a red-black tree.
In a red-black tree, the nodes have a color, either black or red. The colors can be switched during the operations on the node, but they have to follow these conditions:
The root has to be black
A red node cannot have a black child
The black height of any subtree rooted by any node is equal to the black height of the subtree rooted by the sibling node
Now what is the black height of a subtree? It is the number of black nodes found...
