みんな私はレッドブラックツリーの削除アルゴリズムを実装しようとしていますが、このアルゴリズムの3行目を理解するのに問題があります(本「アルゴリズムの紹介」第2版から):
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 そうでなければ x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p [y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y 3≠z
14 then key[z] ← key[y]
15 yの衛星データをzにコピー
16 color[y] = BLACK の場合
17 then RB-DELETE-FIXUP(T, x)
18 return y
まず第一に、この本のどこにも TREE-SUCCESSOR がどのように見えるかを説明していません (そのためのアルゴリズムはありません) 。 ,14,15,4 を削除してから 7 を削除しようとすると、先行者が見つかりますが、11 を削除しようとすると後続者が見つかります。そして、それは私が理解できないものです。なぜ時には前任者が必要なのか、時には後継者が必要なのか? この決定を下す際に考慮される基準は何ですか? ノードの色？
ありがとうございました。
PS 13 行目に書かれていることもよくわかりません。y に 3 つの色 (黒でも赤でもない) があるかどうかということですか?