二分探索木の探索と走査
大小関係で枝を選ぶ仕組みと、木の形が探索回数に与える影響を学びます。
説明
木は、根から親子関係をたどるデータ構造です。二分木では各ノードが左と右の子を最大一つずつ持ちます。二分探索木では、各ノードより小さい値を左の部分木、大きい値を右の部分木へ置きます。部分木は、その子を根として下に続く木全体を指します。
例として根が8の木へ6を挿入し、根からの経路を調べます。続いて左・自分・右の順で全値を列挙する中順走査を行い、一直線に偏った木との高さを比較します。この演習では同じ値を重複して格納しません。
1親と左右の子
辞書のキーをノードの値、対応するリストを[左の子, 右の子]とします。子がない場所はNoneです。
tree = {8: [3, 10], 3: [1, None], 1: [None, None], 10: [None, 14], 14: [None, None]}左右の子を定義; root = 8根; print('\n'.join(f'{value}: L={children[0]} R={children[1]}' for value, children in tree.items()))親ごとに左右を表示根8の左には3と1、右には10と14があります。8の左右だけでなく、3の左の1も8未満という条件を満たしています。子を持たない1と14は葉です。
26を置く位置
6は8より小さいので左の3へ進み、3より大きいので右へ進みます。3の右は空いています。比較結果と参照先を表示します。
target = 6挿入する値; (target < 8, tree[8][0])8より小さいので左, (target > 3, tree[3][1])3より大きいので右最初の比較は左の3、次の比較は空のNoneへ向かいます。根から全ノードを調べるのではなく、大小関係で必要な枝だけを選んでいます。
3新しい葉を接続
3の右へ6をつなぎ、6には子がないことを記録します。他のノードの配置は変えません。
tree[3][1] = 63の右へ接続; tree[6] = [None, None]新しい葉; tree[3], tree[6]変更した接続3の子は[1, 6]となりました。6は3より大きく8より小さいため、この場所で部分木全体の大小関係を保てます。
4探索経路を返す処理
探索の比較を関数にします。値が一致したら止まり、違えば小さいとき左、大きいとき右へ進みます。子がなければ探索終了です。
def search(nodes, start, target):木・根・検索値を受け取る
path = []経路の記録
while start is not None:子がある間だけ続行
path.append(start)現在地を記録
if start == target: return path, True一致したら終了
start = nodes[start][0 if target < start else 1]大小で左右を選択
return path, False空の子に到達したら未発見関数を定義した段階では探索結果は表示されません。pathに通過した値を残すので、次の実行で調べたノードと成功・失敗を確認できます。
5存在する値と存在しない値
6と5を検索します。5も8より小さく、3より大きいため6まで進みますが、その後の左の子がありません。
search(tree, root, 6)6を検索, search(tree, root, 5)5を検索どちらも経路は8・3・6ですが、6はTrue、5はFalseです。探索の失敗も、候補が存在し得る枝を最後までたどった結果です。
6左・自分・右の順に列挙
中順走査では左の部分木を全て列挙し、自分、右の部分木と続けます。子がなければ空のリストを返します。
inorder = lambda node: [] if node is None else子がなければ空 inorder(tree[node][0]) + [node] + inorder(tree[node][1])左・自分・右を連結; inorder(root)根から走査1・3・6・8・10・14の昇順になりました。各部分木で大小関係が保たれるため、同じ走査規則を繰り返すだけで昇順になります。単に辞書の登録順を表示しているわけではありません。
7木の高さ
高さは根から最も遠い葉までの辺の数とします。葉だけの木は0、空の木は計算上-1とします。
height = lambda nodes, node: -1 if node is None else空の木の高さ 1 + max(height(nodes, child) for child in nodes[node])高い方の子へ1を加える; height(tree, root)現在の高さ高さは2です。根から葉までは最大2本の辺、訪れるノードは最大3個です。高さとノード数を混同しないよう、ここでは辺の本数を基準にしています。
8同じ値でも偏った形になる
昇順に追加し、回転などで高さを調整しないと、全て右の子へつながる木を作れます。同じ6個を一直線にした木で14を探します。
values = inorder(root)同じ6個の値; chain = {value: [None, values[i+1] if i+1 < len(values) else None] for i, value in enumerate(values)}右だけに続く木; height(chain, values[0])偏った木の高さ, search(chain, values[0], 14)末端を検索高さ5、探索経路は6ノードです。二分探索木であるだけでは探索が常に速いとは限りません。高さを抑える平衡化によって、長い一本道になることを防ぎます。
まとめ
二分探索木は各部分木全体で大小関係を保ち、探索時には片方の枝へ進みます。
中順走査は左・自分・右の順で値を列挙するため、二分探索木では昇順になります。
探索に必要な比較回数は高さに依存します。偏った木では全ノードをたどることがあります。
操作履歴と解説を振り返れます。
Python 3
tree = {8: [3, 10], 3: [1, None], 1: [None, None], 10: [None, 14], 14: [None, None]}; root = 8; print('\n'.join(f'{value}: L={children[0]} R={children[1]}' for value, children in tree.items()))8: L=3 R=10 3: L=1 R=None 1: L=None R=None 10: L=None R=14 14: L=None R=None
target = 6; (target < 8, tree[8][0]), (target > 3, tree[3][1])((True, 3), (True, None))
tree[3][1] = 6; tree[6] = [None, None]; tree[3], tree[6]([1, 6], [None, None])
def search(nodes, start, target):
path = []
while start is not None:
path.append(start)
if start == target: return path, True
start = nodes[start][0 if target < start else 1]
return path, Falsesearch(tree, root, 6), search(tree, root, 5)(([8, 3, 6], True), ([8, 3, 6], False))
inorder = lambda node: [] if node is None else inorder(tree[node][0]) + [node] + inorder(tree[node][1]); inorder(root)[1, 3, 6, 8, 10, 14]
height = lambda nodes, node: -1 if node is None else 1 + max(height(nodes, child) for child in nodes[node]); height(tree, root)2
values = inorder(root); chain = {value: [None, values[i+1] if i+1 < len(values) else None] for i, value in enumerate(values)}; height(chain, values[0]), search(chain, values[0], 14)(5, ([1, 3, 6, 8, 10, 14], True))
演習完了