2分探索木
出典: フリー百科事典『ウィキペディア（Wikipedia）』
2分探索木（にぶんたんさくぎ、Binary search tree）は、コンピュータプログラムにおける抽象データ型の一つ。2つの枝を持つ木構造であり各葉（leaf）は値をもつ。探索木のうちで最も基本的な木構造である。
目次 |
[編集] 構造
構造は二分木と同じだが、「左の子 ≤ 親 ≤ 右の子」という制約を持つ。左の子と右の子の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。
平衡（左右のバランスがとれている状態）している状態では木の高さは O(log2 N) となる。ただし最悪の場合は、事実上の 線形リスト になり、木の高さは O(N) となる。木の形は挿入時のデータ出現順序に依存し、特にソート済みのデータを与えると線形リストになる点は注意を要する。データの出現順序によって大きく性能が劣化しないように、挿入・削除の際に木の平衡を取り直す処理を追加した2分探索木は平衡2分探索木と呼ばれる。
[編集] 操作
[編集] 探索
- ルートから手順を開始する。
- 着目しているノードと目的の値を比較する。等しいか、着目ノードが存在しなければ終了。
- 「目的の値 < 着目しているノード」なら左の子、「着目しているノード < 目的の値」なら右の子へ移って繰り返し。
探索の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。
[編集] 挿入
同値のデータが出現した場合は右の子として登録するという前提で手順を記す。
- ルートから手順を開始する。
- 着目しているノードと目的の値を比較する。「目的の値 < 着目しているノード」なら左の子、「着目しているノード ≤ 目的の値」なら右の子が、次の着目ノードとなる。
- 次の着目ノードが存在しなければ（現在の着目ノードが葉であれば）、次の着目ノードの位置にデータを挿入。存在すれば、次の着目ノードに移って繰り返し。
挿入の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。
[編集] 全データの列挙
以下のように 再帰呼び出し を使うことで、2分探索木に登録された全データをソートされた順序で列挙できる。
- 左の子をルートとする部分木に対して、この処理を再帰的に適用する。
- 親を表示する。
- 右の子をルートとする部分木に対して、この処理を再帰的に適用する。
挿入時に、同値の値を右の子に登録しておけば、安定ソート となる。
[編集] 関連項目
 |
この「2分探索木」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる人を求めています（Portal:コンピュータ）。 |
