平衡二分探索木とは？データ構造の仕組みと平衡化手法をわかりやすく解説

平衡二分探索木とは

本記事では、平衡二分探索木（Balanced Binary Search Tree）について詳しく解説します。二分探索木（BST：Binary Search Tree）は、各ノードに対して「左の子にはより小さい要素、右の子にはより大きい要素」が配置されるという性質を持つ二分木です。

二分探索木の課題：木が偏る問題

二分探索木での要素検索は、平均的にO(log n)の時間計算量で実行できます。ただしこれは、二分探索木の高さに依存します。BSTの性質を保ちながら要素を挿入していくと、挿入順序によっては木が片側に偏ってしまう（スキューした状態になる）ことがあります。

木が極端に偏ると、以下のような形になります。

上記は確かに木構造ではあるものの、見た目としては連結リストとほぼ変わりません。このような偏った木の場合、検索の時間計算量はO(n)まで悪化し、二分探索木本来の高速な検索性能をまったく活かせなくなります。

平衡化による解決策

こうした問題を防ぐために有効なのが、「高さのバランスが取れた（height-balanced）」木を構築することです。意識的にバランスを保つことで、木が偏るのを防ぎます。具体的には、各ノードの左右の部分木の高さがほぼ同じになるように木を構成します。

代表的な平衡化手法

木を平衡状態に保つための手法はいくつか存在しますが、特に有名なものとして次の2つが挙げられます。

• AVL木（AVL tree）
• 赤黒木（Red-Black Tree）

平衡化後の木の形

先ほどの偏った木を、高さのバランスが取れた形に再構成すると、次のようになります。

このように平衡二分探索木を用いることで、最悪の場合でもO(log n)の検索性能を安定して維持でき、効率的なデータ管理が可能になります。