2 Red-Black Trees and B+ Trees¶
2. 1 Red-Black Trees¶
基本性质
温馨提示
后代节点（descendant node）是包含子节点、孙节点、曾孙节点等所有层级的下级节点。
In a red-black tree, if an internal black node is of degree 1, then it must have only 1 descendant node.
答案
\(\textnormal{T}\)
Suppose a red-black tree \(T\) contains \(N(N \geq 2)\) internal nodes, we denote the height of \(T\) as \(h(T)\) and the black-height of \(T\) as \(bh(T)\). Which of the following statements must be FALSE (assume the height of an empty tree is 0)?
\(\textnormal{A}\). \(h(T) \leq 2bh(T)\) \(\qquad\) \(\qquad\) \(\qquad\) \(\qquad\) \(\qquad\) \(\qquad\) \(\textnormal{B}\). \(h(T) = 3\lceil\log_2(N + 1)\rceil\)
\(\textnormal{C}\). The number of leaf nodes (NIL) in \(T\) is \(2N - 1\) \(\qquad\) \(\textnormal{D}\). The number of leaf nodes (NIL) in \(T\) is \(3N - 5\)
答案
红黑树任意路径中红节点数不超过黑节点数，总高度 \(h(T)\) 不超过黑高的 \(2\) 倍，故 \(\textnormal{A}\) 陈述正确。
一棵有 \(N\) 个内部节点的红黑树，它的高度至多为 \(2log(N+1)\)，NIL 叶节点的个数为 \(N+1\)，故 \(\textnormal{B}\) 陈述错误，\(\textnormal{C}\) 和 \(\textnormal{D}\) 分别在 \(N=2\) 和 \(N=3\) 时取到。
综上所述，答案为 \(\textnormal{B}\)。
In a red-black tree, the number of internal nodes in the subtree rooted at \(x\) is no more than \(2^{bh(x)}\) where \(bh(x)\) is the black-height of \(x\).
答案
对于任意节点 \(x\)，\(\text{sizeof}(x) \geq 2^{\text{bh}(x)} - 1\)，故答案为 \(\textnormal{F}\)
In a Red-Black tree, the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.
答案
\(\text{path}_{\text{farthest}} = num(R) + num(B)\)，\(\text{path}_{\text{nearest}} = num(B)\)，而 \(num(R) \leq num(B)\)，故答案为 \(\textnormal{T}\)
In a Red-Black tree, the path from the root to the nearest leaf is no more than half as long as the path from the root to the farthest leaf.
答案
\(\textnormal{F}\)
红黑树的删除
In a red-black tree, the number of rotations in the \(\text{DELETE}\) operation is \(O(1)\).
答案
\(\textnormal{T}\)
In the worst case, a red-black tree deletion requires \(O(1)\) node recolorings.
答案
红黑树删除操作在最坏情况下的节点重着色次数为 \(O(logn)\)，答案为 \(\textnormal{F}\)
After deleting 12 from the following red-black tree, 13, 14, 15 and 17 will change its color.
答案
答案为 \(\textnormal{F}\)，删除后红黑树结构如下：
红黑树势能函数
There are four basic operations on red-black trees that perform structural modifications: node insertions, node deletions, rotations, and color changes. We shall prove that any sequence of \(m\) RB-INSERT and RB-DELETE operations on an initially empty red-black tree causes \(O(m)\) structural modifications in the worst case. We count the structural modifications in each step (e.g. Case 1 in RB-DELETION) as one unit operation (cost = 1).
We define the weight of each node based on its state, and the potential of the Red-Black Tree \(T\) is represented by the following function:
where \(g(x)\) is calculated for all nodes \(x \in T\) of the Red-Black Tree.
We define the weight of a red node \(x\) as \(g(x) = 0\).
For black nodes, which of the following definitions work?
\(\textnormal{A}\). \(g(x) = \begin{cases} 1 & \text{If the black node has no red children} \\ 0 & \text{If the black node has one red child} \\ 2 & \text{If the black node has two red children} \end{cases}\)
\(\textnormal{B}\). \(g(x) = \begin{cases} 1 & \text{If the black node has no red children or one red child} \\ 2 & \text{If the black node has two red children} \end{cases}\)
\(\textnormal{C}\). \(g(x) = \begin{cases} 0 & \text{If the black node has no red children} \\ 1 & \text{If the black node has one red child} \\ 2 & \text{If the black node has two red children} \end{cases}\)
\(\textnormal{D}\). \(g(x) = \begin{cases} 1 & \text{If the black node has no red children} \\ 2 & \text{If the black node has one red child} \\ 0 & \text{If the black node has two red children} \end{cases}\)
答案
无红孩子的黑节点在删除时易引起合并，有两个红孩子的黑节点在插入时易引起分裂，两者均具有较高势能；只有一个红孩子的黑节点相对稳定，势能较低。故答案为 \(\textnormal{A}\)， 具体证明 此处省略。
2. 2 B+ 树¶
B+ 数的节点度数
A B+ tree of order 3 with 21 numbers has at most ___ nodes of degree 3.
答案
叶子节点分布为 \(2 \times 7 + 3 \times 2\) 时度为 \(3\) 的节点数最多，故答案为 \(4\)
A B+ tree of order 3 with 21 numbers has at least ___ nodes of degree 2.
答案
叶子节点分布为 \(2 \times 7 + 3 \times 2\) 时度为 \(2\) 的节点数最少，故答案为 \(0\)
A B+ tree of order 3 with 21 numbers has at most __ nodes of degree 2.
答案
叶子节点分布为 \(2 \times 9 + 3 \times 1\) 时度为 \(2\) 的节点数最多，故答案为 \(7\)
B+ 树的查找
For a B+ tree with order \(M\) and \(N\) keys, the time complexity of find operations is \(O(\log_M N)\).
答案
对于 B+ 树，查找操作的时间复杂度通常指从根节点到叶节点的路径长度（即树的高度）与节点内部查找键所需时间的乘积，其中树的高度为 \(O(\log_M N)\)，若采用二分查找，则每个节点需要 \(O(\log M)\) 时间，总时间复杂度为 \(O(\log M \cdot \log_M N) = O(\log N)\)，与 \(M\) 无关，答案为 \(\textnormal{F}\)
The time bound of the FIND operation in a B+ tree containing \(N\) numbers is \(O(\log N)\), no matter what the degree of the tree is.
答案
\(\textnormal{T}\)
B+ 树的插入
To perform Insert on a B+ tree of order M, a node with \(M+1\) keys will be split into \(2\) nodes. After inserting \(1,2,3,...,9,10\) consequentially into an initially empty B+ tree of order \(3\), how many split operations have occurred in total?
答案
注意插入 \(8\) 时发生了 \(2\) 次 split，答案为 \(5\)
When insert three keys into a non-empty 2-3 tree, and if the tree gains height when the first key is in, then it is possible that the 2-3 tree will gain more height after the insertions of the next two keys.
答案
\(\textnormal{F}\)