Red-Black Trees Definition¶
The definition of a Red-Black Trees¶
- In the red-black tree, we consider every NULL pointer, every NIL, as a leaf node, and thier colr is black.
- real tree node -> "internal node"
- NIL node -> External node(leaf node)
Ex
A
The black-height of Red-Black Trees(bh)¶
Definition¶
- Notice that x is not included.
Lemma¶
A red-black tree with \(N\) internal nodes has height at most \(2\ln (N+1)\)
Proof¶
- sizeof(x): the Number of internal nodes in the subtree rooted at x
- 根据红黑树定义的第四条，我们知道树中的某一路径的黑色节点数肯定比红色节点数多
Problem¶
1¶
A
构造最短路经，路径上只有黑节点；构造最长路径，路径上是一红一黑
2¶
A
根据定义即可