算法导论13.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

13.1-1

这棵高度为\(3\)的完全二叉搜索树如下：

1
2
3
4
5
6
7
8
9
10
graph TD
  1((1));2((2));3((3));4((4));
  5((5));6((6));7((7));8((8));
  9((9));10((10));11((11));12((12));
  13((13));14((14));15((15))
  8---4;8---12;4---2;4---6;
  12---10;12---14;2---1;2---3;
  6---5;6---7;10---9;10---11;
  14---13;14---15

如下是一棵黑高为\(2\)的红黑树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
graph TD
  1((1));2((2));3((3));4((4));
  5((5));6((6));7((7));8((8));
  9((9));10((10));11((11));12((12));
  13((13));14((14));15((15))
  A[NIL];B[NIL];C[NIL];D[NIL];
  E[NIL];F[NIL];G[NIL];H[NIL];
  I[NIL];J[NIL];K[NIL];L[NIL];
  M[NIL];N[NIL];O[NIL];P[NIL];
  8---4;8---12;4---2;4---6;
  12---10;12---14;2---1;2---3;
  6---5;6---7;10---9;10---11;
  14---13;14---15;
  1---A;1---B;3---C;3---D;
  5---E;5---F;7---G;7---H;
  9---I;9---J;11---K;11---L;
  13---M;13---N;15---O;15---P;
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 1,3,5,7,9,11,13,15,4,12 red-node;
  class 2,6,10,14,8,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P black-node;

如下是一棵黑高为\(3\)的红黑树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
graph TD
  1((1));2((2));3((3));4((4));
  5((5));6((6));7((7));8((8));
  9((9));10((10));11((11));12((12));
  13((13));14((14));15((15))
  A[NIL];B[NIL];C[NIL];D[NIL];
  E[NIL];F[NIL];G[NIL];H[NIL];
  I[NIL];J[NIL];K[NIL];L[NIL];
  M[NIL];N[NIL];O[NIL];P[NIL];
  8---4;8---12;4---2;4---6;
  12---10;12---14;2---1;2---3;
  6---5;6---7;10---9;10---11;
  14---13;14---15;
  1---A;1---B;3---C;3---D;
  5---E;5---F;7---G;7---H;
  9---I;9---J;11---K;11---L;
  13---M;13---N;15---O;15---P;
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  class 4,12 red-node;
  class 1,3,5,7,9,11,13,15,2,6,10,14,8,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P black-node;

如下是一棵黑高为\(4\)的红黑树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph TD
  1((1));2((2));3((3));4((4));
  5((5));6((6));7((7));8((8));
  9((9));10((10));11((11));12((12));
  13((13));14((14));15((15))
  A[NIL];B[NIL];C[NIL];D[NIL];
  E[NIL];F[NIL];G[NIL];H[NIL];
  I[NIL];J[NIL];K[NIL];L[NIL];
  M[NIL];N[NIL];O[NIL];P[NIL];
  8---4;8---12;4---2;4---6;
  12---10;12---14;2---1;2---3;
  6---5;6---7;10---9;10---11;
  14---13;14---15;
  1---A;1---B;3---C;3---D;
  5---E;5---F;7---G;7---H;
  9---I;9---J;11---K;11---L;
  13---M;13---N;15---O;15---P;
  classDef black-node fill:black, color:white;
  class 4,12,1,3,5,7,9,11,13,15,2,6,10,14,8,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P black-node;

13.1-2

使用TREE-INSERT插入节点36后的整棵树如图所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
graph TD
  26((26));17((17));41((41));14((14));
  21((21));30((30));47((47));10((10));
  16((16));19((19));23((23));28((28));
  38((38));7((7));12((12));15((15));
  20((20));35((35));39((39));3((3));
  36((36));
  A[NIL];B[NIL];C[NIL];D[NIL];
  E[NIL];F[NIL];G[NIL];H[NIL];
  I[NIL];J[NIL];K[NIL];L[NIL];
  M[NIL];N[NIL];O[NIL];P[NIL];
  Q[NIL];R[NIL];S[NIL];T[NIL];
  U[NIL];V[NIL];
  26---17;26---41;17---14;17---21;
  41---30;41---47;14---10;14---16;
  21---19;21---23;30---28;30---38;
  10---7;10---12;16---15;19---I;19---20;
  38---35;38---39;7---3;
  3---A;3---B;7---C;12---D;12---E;
  15---F;15---G;16---H;20---J;
  20---K;23---L;23---M;28---N;
  28---O;35---P;35---36;36---Q;36---V;39---R;
  39---S;47---T;47---U;
  classDef red-node fill:red, color:white;
  classDef black-node fill:black, color:white;
  classDef grey-node fill:grey, color:white;
  class 3,17,30,10,15,20,35,39 red-node;
  class 26,41,14,21,47,16,19,23,28,38,7,12,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V black-node;
  class 36 grey-node;

节点36不可以染成红色，因为节点35是红色节点，不满足性质4。同时，节点36也不可以染成黑色，因为节点35的左子树黑高为\(0\)，右子树黑高为\(1\)，两棵子树黑高不相同，不满足性质5。

因此，无论将节点36染成什么颜色，它都不是一棵红黑树。

13.1-3

仍然是一棵红黑树。以下是说明对应5个性质仍然保持的原因：

  1. 因为它只是将根节点从红色染成黑色，而不是染成其它颜色。
  2. 因为根节点按照这个操作染成黑色了。
  3. 因为这个过程没有对NIL节点进行任何操作，它们仍然是黑色的。
  4. 一开始这棵树的根节点是红色，那么它的两个子节点必定是黑色，现在根节点染成黑色后，就不需要对子节点的颜色做出限制了。
  5. 因为变化前到变化后，从根节点到每个叶节点的黑色节点数都恰好多了\(1\)，因为包括上了叶节点。

13.1-4

当吸收操作完成后，一个黑色子节点的度数可能会变成\(1,2,3,4,5\)。对应如下情况：

  1. 当前节点是一个NIL节点，它不会有任何变化。
  2. 收缩前根节点具有\(2\)个黑色子节点，那么收缩后仍然有\(2\)个子节点。
  3. 收缩前根节点具有\(1\)个红色子节点，\(1\)个黑色子节点，那么收缩后有\(3\)个子节点；非根节点具有\(2\)个黑色子节点，收缩后将会有\(2\)个子节点和\(1\)个父节点。
  4. 收缩前根节点具有\(2\)个红色子节点，那么收缩后有\(4\)个子节点；非根节点具有\(1\)个红色子节点，\(1\)个黑色子节点，收缩后将会有\(3\)个子节点和\(1\)个父节点。
  5. 非根节点具有\(2\)个红色子节点，收缩后将会有\(4\)个子节点和\(1\)个父节点。

此外，收缩后，一棵树的高度至少为原来的一半，因为最好的情况下是一棵完全二叉树中，奇数层是红色节点，偶数层是黑色节点。如此吸收所有红色节点后，树高只剩下一半。

13.1-5

令\(bh(x)\)为以\(x\)为根节点的子树的黑高，\(h(x)\)为以\(x\)为根节点的子树的高。那么按照定义，必有\(h(x)\ge bh(x)\)。根据性质\(4\)，从\(x\)到任意叶节点的路径如果包含了一个红色节点，那么这个节点下一个必定是黑色节点，这说明了来自根\(x\)的任意路径上，红色节点的数量一定不超过黑色节点，因此有\(h(x)\le 2bh(x)\)。因此从根到叶子节点的路径中，最长的路径长度至多为最短的\(2\)倍。

13.1-6

当这棵树的节点每一层是红黑交间时，内部节点数最大。这时这棵树是一棵\(2k\)层的完全二叉树，其中偶数层是黑色节点，奇数层是红色节点，一共有\(2^{2k}-1\)个节点。

当这棵树都是黑色节点时，内部节点数最小。这时这棵树是一棵\(k\)层的完全二叉树，一共有\(2^{k}-1\)个节点。

13.1-7

当一棵树所有节点都是黑色时，这个比值最小，为\(0\)。

如果存在正整数\(k\)，使得\(n=2^{2k}-1\)成立，那么这棵高度为\(2k\)的二叉完全树为所求，其中偶数层是黑色节点，奇数层是红色节点。此时将达到最大比值\(2\)。因为每个黑色节点都有\(2\)个红色子节点。

13.1-8

考虑使用反证法证明。不失一般性，假设某个红色子节点的左子节点为NIL，那么左子树黑高为\(0\)。如果右子树不为空，那么根据性质4，右子树的根节点是一个黑色节点，向下遍历，最终这棵子树也会有空子节点NIL，因此右子树黑高一定大于\(0\)。由于左子树和右子树黑高不一致，因此不满足性质5，这棵树必定不是一棵红黑树，最终原结论成立。