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.
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):
- A node is either red or black.
- The root is black.
- All leaves (NIL) are black.
- If a node is red, then both its children are black.
- 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)$.
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.