Results
- smallest is alway left-most
Properties
- Every node is either red or black
- The root and leaves are black
- If a node is red, then its parent is black
- All simple paths from any node to a descendant leaf have the same number of black nodes
- Simple paths means path without repetition
Theorem
A red-black tree with keys has height
- Merge red nodes into their black parents
- This process produces a tree in which each node has 2,3, or 4 children
- The 2-3-4 trees has uniform depth of leaves
Corollary
- search, min, max, successor, predecessor all run in
insertion and deletion through rotation run in
A rotation can be performed in time
- insert
- recolor
- right rotate child
- left rotate parent
- recolor
delete is
Enhancement
you can enhance in various ways
Let as max value, we can achieve performance
where , Therefore, the array consists of many duplicated small values.