13.1 紅黑樹的性質(zhì)

13.1-1

解：
完全二叉搜索樹：

黑高為2的紅黑樹：

黑高為3的紅黑樹：

黑高為4的紅黑樹：

13.1-2

解：如果標(biāo)紅，不滿足性質(zhì)4，因為35是36的父結(jié)點，也是紅色；如果標(biāo)黑，不滿足性質(zhì)5，該條路徑黑高超過其他路徑。

13.1-3

解：可以驗證所得到的樹仍然滿足5個條件，所以是紅黑樹。

13.1-4

解：
（1）如果“吸收”前兩個子結(jié)點都已經(jīng)是黑色了，度為2；
（2）如果“吸收”前兩個子結(jié)點一個是紅一個是黑，度為3；
（3）如果“吸收”前兩個子結(jié)點都是紅色，度為4。
所得到的樹，所有葉結(jié)點的深度相同。

13.1-5

證明：在最長的路徑中，至少每個其他結(jié)點都是黑色的（一紅一黑一紅一黑）。在最短路徑中，最多每個結(jié)點都是黑色的。由于兩條路徑包含相同數(shù)量的黑色結(jié)點，因此最長路徑的長度最多為最短路徑長度的兩倍。

13.1-6

解：最多一層紅一層黑，葉結(jié)點紅，$2^{2k}?1$個；最少全黑，$2^k?1$個。

13.1-7

解：最大比值是2，每個黑色父結(jié)點有兩個紅色子結(jié)點；最小比值是0，全黑。

13.2 旋轉(zhuǎn)

13.2-1

解：

RIGHT-ROTATE(T, x) y = x.left x.left = y.right if y.right != T.nily.right.p = x y.p = x.p if x.p == T.nilT.root = y elseif x == x.p.rightx.p.right = y else x.p.left = y y.right = x x.p = y

13.2-2

證明：每個子結(jié)點都可以旋轉(zhuǎn)到它的父結(jié)點上，只有根結(jié)點沒法轉(zhuǎn)。

13.2-3

解：a深度-1，b深度不變，c深度+1。

13.2-4

證明（機(jī)翻自參考答案）：Since the exercise asks about binary search trees rather than the more specific redblack trees, we assume here that leaves are full-fledged nodes, and we ignore the sentinels.
（由于練習(xí)要求二叉搜索樹而不是更特殊的紅黑樹，我們假設(shè)葉子是完全成熟的節(jié)點而忽略了哨兵。）
Taking the book’s hint, we start by showing that with at most $n?1$ right rotations, we can convert any binary search tree into one that is just a right-going chain. The idea is simple. Let us define the right spine as the root and all descendants of the root that are reachable by following only right pointers from the root. A binary search tree that is just a right-going chain has all n nodes in the right spine.
（根據(jù)本書的提示，我們首先展示最多$n?1$次右旋，可以將任何二叉搜索樹轉(zhuǎn)換為一個單鏈。這個想法很簡單。讓我們將右脊定義為根，并且后繼只能通過右指針到達(dá)。右向單鏈的二叉搜索樹在右脊中具有所有n個結(jié)點。）
As long as the tree is not just a right spine, repeatedly find some node $y$ on the right spine that has a non-leaf left child $x$ and then perform a right rotation on $y$:
（只要樹不僅僅是一個右脊，在右脊上重復(fù)找到一個節(jié)點$y$，其中有一個非葉左子結(jié)點$x$，然后在$y$上執(zhí)行右旋：）

(In the above figure, note that any of $\alpha$, $\beta$, and $\gamma$ can be an empty subtree.) Observe that this right rotation adds $x$ to the right spine, and no other nodes leave the right spine. Thus, this right rotation increases the number of nodes in the right spine by $1$. Any binary search tree starts out with at least one node—the root—in the right spine. Moreover, if there are any nodes not on the right spine, then at least one such node has a parent on the right spine. Thus, at most $n?1$ right rotations are needed to put all nodes in the right spine, so that the tree consists of a single right-going chain.
（（在上圖中，請注意$\alpha$，$\beta$和$\gamma$中的任何一個都可以是一個空子樹。）觀察到這個右旋將$x$添加到右脊，而沒有其他節(jié)點離開右脊。因此，這種右旋使右脊中的節(jié)點數(shù)量增加$1$。任何二叉搜索樹都從右脊以至少一個結(jié)點（根結(jié)點）開始。此外，如果有任何結(jié)點不在右脊上，則至少一個這樣的結(jié)點在右脊上具有父節(jié)點。因此，將所有節(jié)點放在右脊柱中需要最多$n?1$次右旋，以使樹由右向單鏈組成。）
If we knew the sequence of right rotations that transforms an arbitrary binary search tree $T$ to a single right-going chain $T^{\prime }$, then we could perform this sequence in reverse—turning each right rotation into its inverse left rotation—to transform $T^{\prime }$ back into $T$.
（如果我們知道將任意二叉搜索樹$T$轉(zhuǎn)換為單個右向鏈$T^{\prime }$的右旋序列，那么我們可以反向執(zhí)行此序列，將每個右旋反向旋轉(zhuǎn)到其反向左旋直到將$T^{\prime }$轉(zhuǎn)換回$T$。）
Therefore, here is how we can transform any binary search tree $T_1$ into any other binary search tree $T_2$. Let $T^{\prime }$ be the unique right-going chain consisting of the nodes of $T_1$ (which is the same as the nodes of $T_2$). Let $r=?r_1,r_2,\dots ,r_k?$ be a sequence of right rotations that transforms $T_1$ to $T^{\prime }$, and let $r^{\prime }=?r_1^{\prime },r_2^{\prime },\dots ,r_{k^{\prime }}^{\prime }?$ be a sequence of right rotations that transforms $T_2$ to $T^{\prime }$. We know that there exist sequences $r$ and $r^{\prime }$ with $k$, $k^{\prime }\le n?1$. For each right rotation $r_i^{\prime }$, let $l_i^{\prime }$ be the corresponding inverse left rotation. Then the sequence $?r_1,r_2,\dots ,r_k,l_{k^{\prime }}^{\prime },l_{k^{\prime }?1}^{\prime },\dots ,l_2^{\prime },l_1^{\prime }?$ transforms $T_1$ to $T_2$ in at most $2n?2$ rotations.
（因此，以下是我們?nèi)绾螌⑷魏味嫠阉鳂?span id="ze8trgl8bvbq" class="katex--inline">$T_1$轉(zhuǎn)換為任何其他二叉搜索樹$T_2$。 讓$T^{\prime }$成為由$T_1$結(jié)點組成的唯一右鏈（與$T_2$的結(jié)點相同）。 設(shè)$r=?r_1，r_2，\dots ，r_k?$是一系列右旋，將$T_1$轉(zhuǎn)換為$T^{\prime }$，讓$r^{\prime }=?r_1^{\prime }，r_2^{\prime }，\dots ，r_{k^{\prime }}^{\prime }?$是一系列右旋，將$T_2$轉(zhuǎn)換為$T^{\prime }$。 我們知道存在序列$r$和$r^{\prime }$和$k$，$k^{\prime }\le n?1$。 對于每個右旋$r_i^{\prime }$，讓$l_i^{\prime }$為相應(yīng)的反向左旋。 然后序列$?r_1，r_2，\dots ，r_k，l_{k^{\prime }}^{\prime }，l_{k^{\prime }?1}^{\prime }，\dots ，l_2^{\prime }，l_1^{\prime }?$將$T_1$轉(zhuǎn)換為$T_2$ 最多$2n?2$次旋轉(zhuǎn)。）

13.2-5

我們可以使用$O(n)$調(diào)用將$T_2$中的根節(jié)點旋轉(zhuǎn)到$T_1$的根，然后分別在兩個子樹中使用相同的操作。共有$n$個結(jié)點，因此上限是$O(n^2)$。

13.3 插入

13.3-1

解：性質(zhì)5會被破壞。

13.3-2

解：

13.3-3

解（來自參考答案）：
In Figure 13-5, nodes $A$, $B$, and $D$ have black-height $k+1$ in all cases, because each of their subtrees has black-height $k$ and a black root. Node $C$ has black-height $k+1$ on the left (because its red children have black-height $k+1$) and black-height $k+2$ on the right (because its black children have black-height $k+1$).

In Figure 13-6, nodes $A$, $B$, and $C$ have black-height $k+1$ in all cases. At left and in the middle, each of $A$'s and $B$'s subtrees has black-height $k$ and a black root, while $C$ has one such subtree and a red child with black-height $k+1$. At the right, each of $A$'s and $C$'s subtrees has black-height $k$ and a black root, while $B$'s red children each have black-height $k+1$.

Property 5 is preserved by the transformations. We have shown above that the black-height is well-defined within the subtrees pictured, so property 5 is preserved within those subtrees. Property 5 is preserved for the tree containing the subtrees pictured, because every path through these subtrees to a leaf contributes $k+2$ black nodes.

13.3-4

證明：只有在情況1或3會將某結(jié)點設(shè)為RED，在這兩種情況下也只有z.p.p被標(biāo)紅。如果z.p.p是哨兵，z.p就是根結(jié)點。通過循環(huán)不變式的（b）和RB-INSERT-FIXUP的第1行，如果z.p是根，我們已經(jīng)退出循環(huán)。唯一的細(xì)微之處在于情況2，我們在把 z.p.p標(biāo)紅之前設(shè)置z = z.p。因為我們在重新著色之前旋轉(zhuǎn)，所以z.p.p的標(biāo)識在情況2之前和之后是相同的，所以沒有問題。

13.3-5

證明：
情況1：z和z.p.p是RED，如果循環(huán)終止，則z不能是root，因此修復(fù)后z是RED。
情況2：z和z.p是RED，旋轉(zhuǎn)后z.p不能是root，因此修復(fù)后z.p是RED。
情況3：z是RED且z不能是root，因此修復(fù)后z是RED。
無論哪種情況都會有至少一個紅結(jié)點。

13.3-6

解（翻譯自參考答案）：
使用堆棧記錄插入結(jié)點的路徑，然后parent是堆棧中的頂部元素。
情況1：出棧$z.p$和$z.p.p$。
情況2：出棧$z.p$和$z.p.p$，然后入棧$z.p.p$和$z$。
情況3：出棧$z.p$，$z.p.p$和$z.p.p.p$，然后入棧$z.p$。

13.4 刪除

13.4-1

情況1：轉(zhuǎn)換為情況2，3，4
情況2：如果終止，子樹的根結(jié)點（新的x）被設(shè)置為黑色。
情況3：轉(zhuǎn)換為情況4。
情況4：根結(jié)點被設(shè)為黑色。

13.4-2

假設(shè)在$\text{RB-DELETE}$中$x$和$x.p$都是紅色。這只可能在第9行的else情況下發(fā)生。由于是從紅黑樹中刪除，因此在$\text{RB-TRANSPLANT}$第14行的調(diào)用中成為$x$兄弟的y.p的另一個孩子必須是黑色的，所以$x$是$x.p$唯一的孩子。 $\text{RB-DELETE-FIXUP}(T，x)$的while循環(huán)條件會立即被違反，所以只需設(shè)置$x.color=black$，恢復(fù)屬性4。

13.4-3

13.4-4

由于$w$可能是$T.nil$，因此必須包含$\text{RB-DELETE-FIXUP}(T，x)$中檢查或修改w的任何行。但是，如第185頁所述，$w$永遠(yuǎn)不會是$T.nil$，因此不需要包含這些行。

13.4-5

（來自參考答案）
Our count will include the root (if it is black).
Case 1:
For each subtree, it is $2$ both before and after.
Case 2:
For $\alpha$ and $\beta$, it is $1+\text{count}(c)$ in both cases.
For the rest of the subtrees, it is from $2+\text{count}(c)$ to $1+\text{count}(c)$.
This decrease in the count for the other subtreese is handled by then having $x$ represent an additional black.
Case 3:
For $?$ and $\zeta$, it is $2+\text{count}(c)$ both before and after.
For all the other subtrees, it is $1+\text{count}(c)$ both before and after.
Case 4:
For $\alpha$ and $\beta$, it is from $1+\text{count}(c)$ to $2+\text{count}(c)$.
For $\gamma$ and $\delta$, it is $1+\text{count}(c)+\text{count}(c^{\prime })$ both before and after.
For $?$ and $\zeta$, it is $1+\text{count}(c)$ both before and after.
This increase in the count for $\alpha$ and $\beta$ is because $x$ before indicated an extra black.

13.4-6

僅當(dāng)$x$的兄弟$w$為紅色時才會出現(xiàn)情況1。如果$x.p$是紅色的，那么連續(xù)會有兩個紅色，即$x.p$（也是$w.p$）和$w$，即使在調(diào)用$\text{RB-DELETE}$之前也會連續(xù)出現(xiàn)這兩個紅色。

13.4-7

不，紅黑樹不一定是一樣的。 以下是兩個示例：一個是樹的形狀發(fā)生變化，另一個是形狀保持不變但節(jié)點顏色發(fā)生變化。

思考題

13-1（持久動態(tài)集合）

a.

b.

c.

d.

e.

13-2（紅黑樹上的連接操作）

a.

b.

c.

d.

e.

f.

13-3（AVL樹）

a.

b.

c.

d.

13-4（treap樹）

a.

b.

c.

d.

e.

f.

g.

h.

i.

j.

總結(jié)

以上是生活随笔為你收集整理的《算法导论》第三版第13章 红黑树 练习思考题 个人答案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。