二分探索木：挿入 - ドイツ大学院生日記

９．２の二分探索木の解説をしていこうと思います。

２０９ページのプログラムの解説

まずルートから挿入する位置を探索するのでyにNIL(rootを表す)を代入します。

ルートであれば親は持っていないはずです。

そしてまずルートの値と比較するために比較対象にするxにルートを代入します。

以下ループで代入する位置の親となるyを探していきます。

まずどこまで探索できるかわからないためxの値を親としてまず保存しておきます。

そのあとxのkeyの値とzのkeyの値を比較し、それよりも小さいならば比較対象をxの左の値に移します。大きいならばxを右の値に移します。

そしてこの作業を続けていき比較対象を移していくと値が入っていない接点にたどり着きます。その時yにはその値が入っていない親が入っています。

それをzの親として代入します。

最後にy == NIL、親がいない、つまり　xの挿入位置がルートならばTのルートにzを挿入します。そしてzの値が親の値y.keyより小さいならば親の左の子にzを挿入します。

大きいならば親の右のことしてzを代入します。

以上擬似コードの解説でした。