木構造は階層関係を表現するデータ構造。二分探索木は探索を効率化する応用形で、データベースのインデックスにも使われます。
日野 こむぎ
木構造?
なんで「木」って呼ぶの?
藤森 さやか 先生
上が根(root)で、下に枝分かれして葉(leaf) になる構造を、植物の木に例えているのよ。
青木 澪
フォルダ階層やHTML/XMLのDOMが代表例ですね。
各要素をノードと呼んで、親から子へとリンクで繋がっています。
桃井 すみれ
二分探索木っていうのは何が違うんですかぁ?
藤森 さやか 先生
二分探索木は、各ノードが2つ以下の子を持ち、「左の子 < 親 < 右の子」というルールを満たす木よ。
青木 澪
このルールがあると、探したい値より小さければ左、大きければ右と進んでいくだけで O(log n) で探索できるんです。
配列の二分探索に似ていますね。
日野 こむぎ
おぉ、めっちゃ効率いいじゃん!
でも木が偏っちゃったらどうなるの?
青木 澪
いいところに気づいたわね。
最悪 O(n) になっちゃうの。
それを防ぐのが平衡二分探索木で、AVL木や赤黒木が代表的よ。
藤森 さやか 先生
他にも、データベースのインデックスで使われるB木やB+木、優先度付きキューを実装するヒープなど、木構造の応用は本当に多彩なのよ。
確認クイズ
二分探索木の探索操作の平均計算量はどれか。
- O(1)
- O(log n)
- O(n)
- O(n²)
こたえを見る
正解: 2. O(log n)
二分探索木は左右の子で大小関係が決まっているため、平均的に O(log n) で探索できます。ただし木が極端に偏った場合は最悪 O(n) になるため、平衡木 (AVL・赤黒木) で対処します。