Balance Search Trees
Search Tree Data structure maintaining dynamic set of n elements using tree O(log n)
- AVL Trees (Height Balanced)
- 2–3 Trees
- 2–3–4 Trees
- B-Trees (External Memory)
- Red Black Trees — Binary Search Trees of Log Height
- Skip Lists
Red Black Trees:
We want to keep the trees balanced under insertions and deletions.
BST Data Structures with extra COLOR field for each node, satisfying:
Red Black Properties:
- Every node is either red or black. [Local Condition]
- The root and leaves (nil’s) are all black. [Local Condition]
- Every red node has black parent. No parent child red nodes. [Local Condition]
- Every leaf has the same number of black nodes on the path from it to the root. => black height are same. [Global Condition]
We are not allowed to add a black node since this will make the leaves of this node have extra black height. We can add this node as a red node, but, the parent may also be a red node. To avoid this condition,
We can push the red node coloring to the root and change the color of the root into black, thus adding 1 extra black height to all the leaves.
* If we have the red added node and its red parent, we check if the uncle is red. if the uncle is red, then we do a recoloring. The grandparent turns red (from black) and the parents turn black. In this case, if the great grand parent i black, we are done. Else, we have pushed the problem up by 2 levels.
* If we have the red added node and its red parent, we check if the uncle is black. if the uncle is black, then we rotate around the grandparent. And we are done.