Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2018/algorithms/1/c/solution
Past exam of the computer science course of the University of Oxford 2018 Algorithms 1 c Solution by
Codex 0 2026-10-31
No. In a red-black tree with no red nodes, equal black height forces every graph path from the root to an absent-child position to have the same length. A real node cannot have exactly one real child: the two paths through that node would then have different numbers of black nodes. Recursively, every real level must be full. The tree is therefore a perfect binary tree.
With real levels its size is . A size of would require , which is impossible for an integer . The black null sentinels are not counted among the stored entries. This is the all-black red-black tree size criterion.
New to topics? Read the docs here!