Can nodes in red-black trees have one nil child and one non-nil child?

I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log_2(n + 1)$, where n is the number of nodes, and I don't see how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of n.

• A node in red-black tree can have one NIL child and one non-NIL child. The fact that the height is of $O(\log n)$ is guaranteed by the red/black coloring rule. – hengxin Mar 20 '15 at 3:35
• @hengxin Expand to an answer? – Yuval Filmus Mar 20 '15 at 6:35
• "Some nodes can have X" is not the same as "all nodes can have X". – Raphael Mar 20 '15 at 7:02

Can nodes in red-black trees have one nil child and one non-nil child?

Yes. A red-black tree is a special case of binary search tree: each node is colored red or black. In red-black tree, if a child does not exist, the corresponding pointer field of that node contains the value NIL. NILs are treated as leaves.

red-black trees have a worst-case height of $2 \log 2(n+1)$

The fact that the height is of $O(\lg n)$ is guaranteed by the red/black coloring rules (copied from CLRS):

1. A node is either red or black.
2. The root is black.
3. All leaves (NIL) are black.
4. If a node is red, then both its children are black.
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.

These rules, especially rules 4 and 5, ensure that the tree is approximately balanced: no any path is more than twice as long as any other. In terms of tree height, we have

A red-black tree with $n$ internal nodes has height at most $2 \lg (n+1)$.

Finally,

how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of $n$.

By the red/black coloring rules, a non-trivial (with enough number of nodes) red-black tree cannot be a straight line/linked list.

For more details, you may want to read the book "Introduction to Algorithms" by CLRS.

• Oh, I see. When I first read the coloring rules in CLRS, I thought rule 5 meant $\forall x ( Node(x)\Rightarrow \exists c( \forall y ( Leaf(y) \Rightarrow Distance(x, y) = c) ) )$, even though it meant $\exists c (\forall x ( Node(x)\Rightarrow ( \forall y ( Leaf(y) \Rightarrow Distance(x, y) = c) ) ) )$. That was a silly mistake on my part, as the former expression is obviously true, as there is only one simple path from one node to another in a tree! – Kelmikra Mar 20 '15 at 21:34