Explain the concept of Red-Black Trees and their properties.

Instruction: Discuss the characteristics of Red-Black Trees and why they are important in algorithm design.

Context: This question aims to evaluate the candidate's understanding of Red-Black Trees, a self-balancing binary search tree, and its properties that ensure balanced tree height.

Updated

Official answer

A red-black tree is a BST with coloring rules that keep its height logarithmic. In the conventional formulation:

  1. Each node is red or black.
  2. The root is black.
  3. Every NIL sentinel representing a missing child is black.
  4. A red node has only black children.
  5. Every path from a node to its descendant NIL sentinels contains the same number of black nodes, using one consistent counting convention.

Equal black height and the ban on consecutive red nodes limit path-length imbalance; a tree with n stored nodes has height at most 2·log2(n+1) under the usual edge-height convention. Search, insertion and deletion are therefore O(log n) with constant-cost comparisons.

A common insertion procedure initially colors a new non-root node red, then uses recoloring and rotations to repair violations. “Every new node is red” is an algorithm step, not a permanent invariant: the root must be black after repair, and inserted nodes may be recolored. Deleting a black node can also require repair.

Rotations preserve BST in-order ordering while changing local structure. Test both ordering and coloring/black-height rules after updates. A valid BST alone is not necessarily a valid red-black tree.

Related Questions