二分探索木：削除
【アルゴリズムとデータ構造】二分探索木：削除（解説）
９．４の解説をします。
ある節点Zを削除する時を考えます。
・Zが子を持たない場合
ただ単にZを削除すれば良いので、Zの親の子供を削除つまりZを削除すれば良い
・Zが子を一つ持つ場合
Zは親と子供に挟まれているので、Zを削除するためには親の子供の設定をZの子
供に変え、（Zの子供）の親を（Zの親）に変えてあげればZを削除できます。
・Zが子を二つ持つ場合
Zの次節点とは単にZの上の接点のことを指している。Zが持っている２つの子をZの上の節点に移してあげれば良い。そこでZの次節点の値をZ地震にコピーし、Zの次節点を削除してあげればZを削除したことになる。
解説のプログラムの解説をします。
二分探索木Tと削除対象Zを受け取ります。
そこで削除対象は、Zが子を持つ場合ではZの次節点でした。そこで削除対象をYに移します。子を持たない、子を１つだけ持つ場合ではY＝Zであり、Zが子を持つ場合はZの次節点をYに代入します。
次に削除対象の子供を調べます。
左に子があれば左の子をxに代入します。
左に子供がない場合にはxに右の子の値を代入します。この場合実際に右に子供がいなくても構いません。あとで処理します。
そしてxがNILじゃないつまり削除対象の子供が存在する場合、削除対象の親を、削除対象の子供の親に設定します。
削除対象の親が存在しない時、その削除対象の子供を根とします。
削除対象がその親の左の子供の場合には、左の子供の位置に削除対象の子供を入れます。
削除対象がその親の右の子供の場合には、右の子供の位置に削除対象の子供を入れます。
最後の子供が二ついた場合において次節点が削除された場合
つまり削除対象がZと異なる場合
Zの値に、削除対象の値を代入します。
次節点を求めるアルゴリズムの解説
右の子供が存在する場合は値が一番小さい節点が次節点となるので、その節点を調べて返します。
右の子供が存在しない場合には、自身が左の子供になっているような節点の親が次節点となる。
次節点は以下のようにして探索します。まずYにXの親を代入します。
そのYが存在するつまり根ではないかつ、右の子供がXである限り以下の操作を繰り返します。
まずXとYを位置関係そのままで上に移していきます。
つまりYはXの親であるから、XにYを代入
YにYの親を代入
を繰り返すことで次節点を探索することができます。
次に二分探索木での最小値を求めるアルゴリズムの解説をします。
最小値となる候補はその値かその左の子供であるめ左の子供について一番深い場所にある節点を探索していきます。
Xの左の子が存在するまで繰り返します。
そうすることで二分探索木の最小値を求めることができます。
一般的に二分探索木では木の高さをできるだけ低く維持する必要性がある。
バランスのとれた木を平衡二分探索木という。
二分探索木：挿入
【アルゴリズムとデータ構造】二分探索木：挿入（解説）
９．２の二分探索木の解説をしていこうと思います。
２０９ページのプログラムの解説
まずルートから挿入する位置を探索するのでyにNIL(rootを表す)を代入します。
ルートであれば親は持っていないはずです。
そしてまずルートの値と比較するために比較対象にするxにルートを代入します。
以下ループで代入する位置の親となるyを探していきます。
まずどこまで探索できるかわからないためxの値を親としてまず保存しておきます。
そのあとxのkeyの値とzのkeyの値を比較し、それよりも小さいならば比較対象をxの左の値に移します。大きいならばxを右の値に移します。
そしてこの作業を続けていき比較対象を移していくと値が入っていない接点にたどり着きます。その時yにはその値が入っていない親が入っています。
それをzの親として代入します。
最後にy == NIL、親がいない、つまり xの挿入位置がルートならばTのルートにzを挿入します。そしてzの値が親の値y.keyより小さいならば親の左の子にzを挿入します。
大きいならば親の右のことしてzを代入します。
以上擬似コードの解説でした。
