探索木の平衡化（B木・AVL木）とは？
探索木の平衡化（B木・AVL木）とは、二分探索木は、データの追加順によっては片側に偏って一直線に近い形になり、探索効率がO(n)まで悪化することがある。この偏りを防ぎ、木の高さを常に低く保つよう自動的に調整する仕組みを平衡木といい、AVL木やB木が代表例。B木はデータベースのインデックスなど、大量データを扱う場面で広く使われる。
たんさくぎのへいこうか
探索木の平衡化（B木・AVL木）の意味
二分探索木は、データの追加順によっては片側に偏って一直線に近い形になり、探索効率がO(n)まで悪化することがある。この偏りを防ぎ、木の高さを常に低く保つよう自動的に調整する仕組みを平衡木といい、AVL木やB木が代表例。B木はデータベースのインデックスなど、大量データを扱う場面で広く使われる。
探索木の平衡化（B木・AVL木）の具体例
データベースのインデックスにB木が使われるのは、木の高さを低く保てることでディスクへのアクセス回数（読み込み回数）を抑え、大量データでも高速に検索できるため。
探索木の平衡化（B木・AVL木）は試験でどう引っ掛けられる？
平衡とは「データ件数が均等」ではなく「木の高さが均等」の意味。AVL木は左右の部分木の高さの差を1以内に保つ二分木、B木は1ノードに複数のキーを持つ多分木で、ディスクの読み書き回数を減らすのが狙い。探索量はいずれもO(log n)。
探索木の平衡化（B木・AVL木）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。