二分探索木の生成

二分探索木を生成する過程では、先頭に1つのノードを持ち、そこから値の大小関係によって続くノードを右または左に割り振っていきます。この処理の仕組みを考えてみましょう。

生成の仕組み

二分探索木は、元のノードを親、そこから左右に割り振られるノードを子とし、1つの親に左右2つの子ノードがぶら下がり、さらにそれぞれの子ノードから左右に孫ノードがぶら下がって……という、モービルのような形になります。

一般に、ノードの持つ値より小さい値は左、大きい値は右へ割り振ります。二分探索木の生成過程をプログラムにする場合、次のような手順となります。

先頭の値を取り出してノードを生成
2番目の値を取り出して先頭の値と比較
先頭の値より小さければ
　　→　ノードを生成して左へ
大きければ
　　→　ノードを生成して右へ
3番目の値を取り出して先頭の値と比較
先頭の値より小さければ
　　→　ノードを生成して左へ
大きければ
　　→　ノードを生成して右へ
　　　　　割り振った先にノードがあれば
　　　　　　 →　比較元をそのノードとして3.の処理を実行
　　　　：

以下、同様に値を取り出しては先頭と比較して左右どちらかに割り振り、そこに値が存在すれば、また同じように大小関係に従ってその左右に割り振る……という動作を、比較先の値がなくなるまで繰り返す。

TOP

自分自身を呼び出す

要するに、先頭のノードを生成する処理以降は、上記3.の処理を値がなくなるまで繰り返していくことになります。これを逐一ソースコードにしていくと、キリがなくなります。

すると、上記3.の処理の中から同じ3.の処理を実行して……という形が合理的であることが分かります。処理を1つの関数とすれば、関数の中から自分自身を呼び出す形になります。このような構造を「再帰」、再帰的に関数を呼び出すことを「再帰呼び出し」と言います。

TOP

NEXT PAGE >>

【質問１】コラムをどれくらい読みましたか？

熟読した途中でやめたさっと目を通した印刷してこれから読む

【質問２】役に立つ内容でしたか？

参考になった参考にならなかった

ご自由にコメントを記入してください