ドイツ大学院生日記

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

二分探索木:挿入

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

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

 

209ページのプログラムの解説

 

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

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

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

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

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

 

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

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

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

 

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

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

 

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