・最も基本的な
・ …データを格納する が決められている木構造
・例えば、
・同一レベルのノードは左から右へ、
・レベルの上から下へ、
・値が大きくなるように格納
・二分探索木のデータ格納順序
・全てのノードについて、次の関係が成り立つように格納
・ノードの持つ値(キー)は、その
左部分木のどのノードの値よりも か、または等しい
右部分木のどのノードの値よりも か、または等しい
・つまり、
左部分木の子孫の値 親の値 右部分木の子孫の値 [一般的にはこちら]
が成り立っている
※もちろん、この順序関係は真逆でもよい
左部分木の子孫の値≧親の値≧右部分木の子孫の値
二分探索木の有用性
・目的の値を持つノードを効率よく探索できる
・目的の値と現在注目しているノードの値を比較
・目的の値の方が大きい
→目的の値は を再帰的に探す
・目的の値の方が小さい
→目的の値は を再帰的に探す
・たったこれだけ！
二分探索木の探索効率
・ノード数nの二分探索木を考える
・目的の値を検索する際の計算量は？→ によって変わる
・最も探索効率が良い形は？ ・最も探索効率が悪い形は？
・目的の値を探索する際の最大計算量を見積もりたい
・最大計算量=探索時の最大比較回数← に等しい(これは、ほぼ自明ですね)
・ノード数がnであるとき、探索に必要な計算量を考察しよう
・まずは、最良の場合
→左右の部分木がバランスしている二分探索木( )
・では、ノード数nの平衡二分木の高さHはどうなるでしょう？
・Hをnの関数で表したい
H = f(n)
・高さHの平衡二分木に収容できる最大ノード数nmaxは？
・木のレベルが深くなるごとに、子ノードは に増やせる
ノードの総数は、初項1公比2の等比数列の第H項までの和 一般に
・高さHの平衡二分木に収容できる最大ノード数nmaxは
nmax = 2^H - 1
なので、高さHは
H = log2(nmax + 1)
ノード数nの平衡二分木の高さH(n)はn≦nmaxだから
H(n)=log2(n + 1) log2(nmax + 1)
二分探索木が平衡に分岐のとき、探索計算量は
O( ) … これが最良の場合
・では、最悪の場合は
・左右どちらかの部分木にリスト状に値が格納されている
ノード数nのとき、木の高さHは
H = n
なので
O(n)
探索効率の良い二分探索木にするには
・左右の部分木をバランスさせ、 に近づける
・but... バランスした二分探索木を作るのは難しい
・ノードの でバランスが崩れるので、その都度再バランス化が必要
→複雑なアルゴリズムを採用する必要がある
・バランスした二分探索木を作るアルゴリズム
(例) 、
・あるいは、多分木を採用する
・これも実装はかなり複雑
(例) …データベースのインデックスの実装などによく用いられる
実は、無理に平衡二分探索木を作らなくても...
・格納対象が大量のランダムデータであれば...
・ノード数nの二分探索木の高さは、高々 であることが知られている
※eはネイピア数(自然対数の底)
・この様なデータから作られる二分探索木
・木の高さは、完全な平衡二分探索木の高々 程度しか増えない(1.386倍)
[このぐらいの効率低下は気にしなくていいよね] → 十分実用になる
二分探索木を作ろう！
作り方(もちろん再帰で作る)
ノードを追加する二分探索木が・
・根となるノードを1つ作る
・空木でないとき
・追加する値が根の値より
大きい→ へこの方法で追加
小さい→ へこの方法で追加
[再帰]
・データがなければ終了
指定した値を持つノードの削除
・注意…単純な削除はダメ！
・ノードの削除後も、二分探索木を保たなければならない
・順序木でない二分木のノード削除と同様に、3つ場合を考える
・リーフの場合
…これは簡単、単純に削除しても二分探索木は保持される
・子を1つ持つノードの場合
…これも簡単、単純に削除しても二分探索木は保持される
・子を2つ持つノードの場合
…単純にリーフと置き換えてはダメ
・単純にリーフと置き換えると、二分探索木が
・置き換えの対象となる適切なノードを選ぶ
・適切なノードは、左部分木の または右部分木の
・これは必ず決まった場所にある
・左部分木の最大値→左部分木の のノード
・右部分木の最小値→右部分木の のノード
[どちらを採用してもよいが通常は、前者を採用することが多い]
二分探索木内の値を全て取り出す(表示する)
・昇順(小さい順)に取り出す
手順
見ているノードが
・空木のとき
・何もしない
・空木でないとき
・ 部分木の値を、全てこの方法で取り出す
・根の値を取り出す
・ 部分木の値を、全てこの方法で取り出す
[再帰]
探索方法…「 」
二分探索木内の値を全て取り出す(表示する)
・降順(大きい順)に取り出す
手順
見ているノードが
・空木のとき
・何もしない
・空木でないとき
・ 部分木の値を、全てこの方法で取り出す
・根の値を取り出す
・ 部分木の値を、全てこの方法で取り出す
[再帰]