18

Algorithms Third Edition の紹介では、赤黒木削除の疑似コード実装があります。ここにあります...

RB-DELETE(T, z)
    y = z
    y-original-color = y.color
    if z.left == T.nil
        x = z.right
        RB-TRANSPLANT(T, z, z.right)
    elseif z.right == T.nil
        x = z.left
        RB-TRANSPLANT(T, z, z.left)
    else
        y = TREE-MINIMUM(z.right)
        y-original-color = y.color
        x = y.right
        if y.p == z
                x.p = y       // <--------- why????
        else
                RB-TRANSPLANT(T, y, y.right)
                y.right = z.right
                y.right.p = y
        RB-TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y
        y.color = z.color
    if y-original-color == BLACK
        RB-DELETE-FIXUP(T, x)

TREE-MINIMUM はツリー内の最小値を見つけるだけで、RB-TRANSPLANT は 2 番目のパラメーターの親を取得して 3 番目のパラメーターを指し、3 番目のパラメーターの親を 2 番目のパラメーターの親にします。

私のコメントによると、彼らは yp が z であるかどうかをテストし、そうであれば xp を y に設定します。しかし、x はすでに y.right なので、これは y.right.p = y と言っているようなものですが、y.right.p はすでに y です! なぜ彼らはこれをしているのですか？

これが彼らの説明です...

「しかし、y の元の親が z の場合、xp が y の元の親を指すことは望ましくありません。これは、そのノードをツリーから削除しているためです。ノード y は上に移動してツリー内の z の位置を取るため、13 行目で xp を y に設定すると、x == T.nil であっても、xp は y の親の元の位置を指すようになります。」</p>

したがって、彼らは x の親を y のままにしたいと考えています...それはすでに y です...

4

1 に答える 1

13

y.right が Nil の場合、x も Nil になる可能性があるとテキストで述べています。Nil はこのコードにもノードで表されているようで、ダングリング ポインターを残したくありません。

于 2011-04-21T15:17:31.287 に答える