赤い黒い木の削除アルゴリズム

Question

私は赤い黒い木の削除アルゴリズムを実装しようとしている人であり、このアルゴリズムの3行目を理解するのに問題があります（本「Allyto to Algorithms」第2版から）：

1残っている場合[z] = nil [t]または右[z] = nil [t
2次にY←Z
3他のY←ツリーサクセッサー（z）
4残っている場合[y]≠nil [t
5次にx←左[y
6他のx←右[y
7 p [x]←p [y
8 p [y] = nil [t
9次に[t]←x
y =左[p [y]]の場合10 else
11次に左[p [y]]←x
12他の右[p [y]]←x
13 y 3≠zの場合
14次にキー[z]←キー[y
15 Yの衛星データをzにコピーします
16色[y] =黒
17次にrb-delete-fixup（t、x）
18 return y

まず第一に、この本には、ツリーサクセッサーがどのように見えるかを説明した場所はありません（そのためのアルゴリズムはありません）が、私は見つけました このページ: ：そして、このアルゴリズムに11,2,1,7,5,8,14,15,4,15,4,4,4,15,4を削除すると、見つかります。 前身 しかし、私が11を削除しようとすると、それは見つかります 後継. 。そして、私が理解できないこと。なぜ時々それは前身と時には後継者を必要とするのですか？この決定を行う際にどのような基準が考慮されますか？ノードの色？
ありがとうございました。

PS私はまた、それがライン番号13で書かれているものを完全に理解していません。それは、yが3色（黒でも赤でもない）または他の何かを持っている場合を意味しますか？

Answer 1

ツリーの後継者（ツリープレドマンデーの反対として[その本の中にある]）は、次に最高のキーを持つノードとしてバイナリ検索ツリーに対して一般的に定義されています。それがどのようにそれがタイプ（この場合は赤色ブラック）に依存していると判断し、あなたの本は後継者の方法を演習として残します。 （私は問題を覚えています：p）

Answer 2

CLRS第2版を読んでいると思います。

ツリーサクセッサーは、第12章セクション2-「12.2バイナリ検索ツリーのクエリ」で紹介されています。そして、ジェシー・ノーガーが言っていることとは反対に、それはバイナリ検索ツリーのタイプに依存していません。

あなたが引用した13行目はタイプミスです。 「y！= z」である必要があります。

Answer 3

次のコードを参照できます。

http://code.google.com/p/cstl/source/browse/src/c_rb.c