Red-Black Tree Basics
What are they ?
Red-Black is a data structure similar to binary-search trees. And they have the following properties.
- Every node is either red/black
- The root node is always black
- Every leaf node is black
- If a node is red, then both its children will be black
- From the root, till the leaf node, the number of black nodes (excluding the root) node are always constant
- Nil nodes are black
How are they different from BST (Binary Search Trees) ?
A Red-Black tree is self-balancing, and all operation happens in logarithmic times, but BST can at times be,
unbalanced making operations take linear time.
Where do we use them ?