平衡木（AVL木・赤黒木）とは？へいこうぎ
平衡木（AVL木・赤黒木）とは、挿入・削除のたびに木の形を組み替え、高さをO(log n)に保ち続ける二分探索木の総称。AVL木は左右の部分木の高さの差を1以内に、赤黒木は色の規則により最長経路が最短経路の2倍以内になるよう制約し、いずれも回転操作で平衡を回復する。
最終更新：2026-10-07
高度試験の午前Iを最短で暗記する →具体例
AVL木は平衡条件が厳しいぶん高さが低く探索が速いが、更新のたびに回転が増える。赤黒木は平衡が緩く回転回数が少ないため更新が多い用途に向き、多くの言語の標準ライブラリの順序付きマップは赤黒木で実装されている。
試験での引っ掛け
平衡木が保証するのは「最悪でもO(log n)」であって、常に最速という意味ではない。件数が少なければ配列の線形探索のほうが速いこともある。また平衡維持のコストは挿入・削除側にかかり、探索は無料ではない。ハッシュ表との使い分けの軸は順序で、平衡木は要素の順序を保つため範囲検索ができる。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。