読者です 読者をやめる 読者になる 読者になる

競プロ記録

問題を解いた際に自分の復習用として使ってます

二分探索木:削除

アルゴリズムとデータ構造】二分探索木:削除(解説)

9.4の解説をします。

ある節点Zを削除する時を考えます。

・Zが子を持たない場合

 ただ単にZを削除すれば良いので、Zの親の子供を削除つまりZを削除すれば良い

 

・Zが子を一つ持つ場合

 Zは親と子供に挟まれているので、Zを削除するためには親の子供の設定をZの子

 供に変え、(Zの子供)の親を(Zの親)に変えてあげればZを削除できます。

 

・Zが子を二つ持つ場合

 Zの次節点とは単にZの上の接点のことを指している。Zが持っている2つの子をZの上の節点に移してあげれば良い。そこでZの次節点の値をZ地震にコピーし、Zの次節点を削除してあげればZを削除したことになる。

 

解説のプログラムの解説をします。

 

二分探索木Tと削除対象Zを受け取ります。

そこで削除対象は、Zが子を持つ場合ではZの次節点でした。そこで削除対象をYに移します。子を持たない、子を1つだけ持つ場合ではY=Zであり、Zが子を持つ場合はZの次節点をYに代入します。

 

次に削除対象の子供を調べます。

左に子があれば左の子をxに代入します。

左に子供がない場合にはxに右の子の値を代入します。この場合実際に右に子供がいなくても構いません。あとで処理します。

 

そしてxがNILじゃないつまり削除対象の子供が存在する場合、削除対象の親を、削除対象の子供の親に設定します。

 

削除対象の親が存在しない時、その削除対象の子供を根とします。

削除対象がその親の左の子供の場合には、左の子供の位置に削除対象の子供を入れます。

削除対象がその親の右の子供の場合には、右の子供の位置に削除対象の子供を入れます。

最後の子供が二ついた場合において次節点が削除された場合

つまり削除対象がZと異なる場合

Zの値に、削除対象の値を代入します。

 

次節点を求めるアルゴリズムの解説

右の子供が存在する場合は値が一番小さい節点が次節点となるので、その節点を調べて返します。

右の子供が存在しない場合には、自身が左の子供になっているような節点の親が次節点となる。

次節点は以下のようにして探索します。まずYにXの親を代入します。

そのYが存在するつまり根ではないかつ、右の子供がXである限り以下の操作を繰り返します。

 

まずXとYを位置関係そのままで上に移していきます。

つまりYはXの親であるから、XにYを代入

YにYの親を代入

を繰り返すことで次節点を探索することができます。

 

次に二分探索木での最小値を求めるアルゴリズムの解説をします。

最小値となる候補はその値かその左の子供であるめ左の子供について一番深い場所にある節点を探索していきます。

Xの左の子が存在するまで繰り返します。

そうすることで二分探索木の最小値を求めることができます。

 

一般的に二分探索木では木の高さをできるだけ低く維持する必要性がある。

バランスのとれた木を平衡二分探索木という。