算法导论18.1 Exercises 答案

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

18.1-1

当\(t=1\)时，每个内部节点都将有\(t=1\)个键，这意味着它每个内部节点都有\(2\)个子节点，这说明此时\(T\)必须是一个满二叉树。令\(n\)表示这棵树的节点数，如果\(\nexists k\)使得\(n=2^k-1\)成立，这说明\(T\)的所有叶子节点都不在同一层（否则必须是一棵完美二叉树），从而违反了性质4。因此必须满足\(t>1\)。

18.1-2

可以看出，图18.1中的非根节点中的关键字数量从\(2\)到\(3\)不等。如果\(t=2\)，那么关键字数量的范围是\(\{1,2,3\}\)；如果\(t=3\)，那么关键字数量的范围是\(\{2,3,4,5\}\)；如果\(t=4\)，那么关键字数量的范围是\(\{3,4,5,6,7\}\)，此后\(t\)再大也不符合要求。因此\(t\)的值可能是\(2\)或\(3\)。

18.1-3

如下是所有满足要求的树。

1
2
3
4
5
6
7
8
9
graph TD
  A1[2];B1[1];C1["3 4 5"];
  A1---B1;A1---C1;
  A2[3];B2["1 2"];C2["4 5"];
  A2---B2;A2---C2;
  A3[4];B3["1 2 3"];C3["5"];
  A3---B3;A3---C3;
  A4["2 4"];B4["1"];C4["3"];D4["5"];
  A4---B4;A4---C4;A4---D4;

18.1-4

可见，高度为\(h\)的\(B\)树在第\(0\)层只有\(1\)个节点，在第\(1\)层最多有\(2t\)个节点，在第\(2\)层最多有\((2t)^2\)个节点……因此，高度为\(h\)的最小度数为\(t\)的\(B\)树最多可以有\(\displaystyle{\sum_{i=0}^h(2t)^i=\dfrac{(2t)^{h+1}-1}{2t-1}}\)个节点。那么这棵树可以存储\(\dfrac{(2t)^{h+1}-1}{2t-1}\times(2t-1)=(2t)^{h+1}-1\)个关键字。

18.1-5

最终会得到一个\(t=2\)的B树，并且这棵树的叶子节点都相同，为原来B树的黑高。每个黑色节点包含的关键字数为其原来在红黑树上的红色子节点数再加上\(1\)。更具体地说，对于一个黑色节点\(x\)，可以分为如下\(4\)种情况：

  1. 如果\(x\)的\(2\)个子节点都是黑色，那么吸收后所得到的\(x\)仍然和原来一样，如下图所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph TD
    A((A));
    a[α];b[β];
    Z(( ))
    classDef hide-appearance fill:transparent, stroke:transparent;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    class A black-node;
    class a,b hide-appearance;
    class Z hide-node;
    Z---A;A---a;A---b;
    
    A'[A];
    a'[α];b'[β];
    Z'(( ))
    class a',b' hide-appearance;
    class Z' hide-node;
    Z'---A';A'---a';A'---b';
  1. 如果\(x\)的左子节点是红色，右子节点是黑色，那么吸收后当前节点将会有\(2\)个键，从左到右依次为\(x.left.key,x.key\)，如下图所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
graph TD
    A((A));B((B));
    a[α];b[β];c[γ];
    Z(( ))
    classDef hide-appearance fill:transparent, stroke:transparent;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    class B black-node;
    class A,C red-node;
    class a,b,c,d hide-appearance;
    class Z hide-node;
    Z---B;B---A;B---c;A---a;A---b;

    A'["A B"]
    a'[α];b'[β];c'[γ];
    Z'(( ))
    class A,C red-node;
    class a',b',c' hide-appearance;
    class Z' hide-node;
    Z'---A';A'---a';A'---b';A'---c';
  1. 如果\(x\)的左子节点是黑色，右子节点是红色，那么吸收后当前色节点将会有\(2\)个键，从左到右依次为\(x.key,x.right.key\)，如下图所示：
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
graph TD
    B((B));C((C));
    a[α];b[β];c[γ];
    Z(( ))
    3(( ))
    6(( ))

    classDef hide-appearance fill:transparent, stroke:transparent;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    class B black-node;
    class A,C red-node;
    class a,b,c,d hide-appearance;
    class Z,3,6 hide-node;
    Z---B;B---a;a---3;a---6;
    B---C;C---b;C---c;
    linkStyle 2,3 stroke:#0ff,stroke-width:0px 


    A'["B C"]
    a'[α];b'[β];c'[γ];
    Z'(( ))
    class A,C red-node;
    class a',b',c' hide-appearance;
    class Z' hide-node;
    Z'---A';A'---a';A'---b';A'---c';
  1. 如果\(x\)的\(2\)个子节点都是红色，那么吸收后当前节点将会有\(3\)个键，从左到右依次为\(下x.left.key,x.key,x.right.key\)，如下图所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
graph TD
    A((A));B((B));C((C));
    a[α];b[β];c[γ];d[δ];
    Z(( ))
    classDef hide-appearance fill:transparent, stroke:transparent;
    classDef hide-node display:none;
    classDef red-node fill:red, color:white;
    classDef black-node fill:black, color:white;
    class B black-node;
    class A,C red-node;
    class a,b,c,d hide-appearance;
    class Z hide-node;
    Z---B;B---A;B---C;A---a;
    A---b;C---c;C---d;

    A'["A B C"]
    a'[α];b'[β];c'[γ];d'[δ];
    Z'(( ))
    class A,C red-node;
    class a',b',c',d' hide-appearance;
    class Z' hide-node;
    Z'---A';A'---a';A'---b';A'---c';
    A'---d';