平衡木（AVL木・赤黒木）とは？へいこうぎ
平衡木（AVL木・赤黒木）とは、どんな順序でデータを入れても木の高さがO(log n)を超えないよう、挿入・削除のたびに回転で形を整え直す二分探索木の総称。整え方の厳しさで種類が分かれ、赤黒木は色の規則により最長経路を最短経路の2倍以内に抑えるにとどめ、AVL木は左右の部分木の高さの差を1以内まで厳しくそろえる。
最終更新：2026-10-06
この語が出る過去問を解く →背景
単純な二分探索木は、あらかじめ整列されたデータを順に挿入すると片側だけに伸び、実質的に線形リストへ退化して探索がO(n)まで落ちる。平均では速いが最悪が保証できないという性質は、入力の順序を選べない実システムでは致命的になる。形を自動的に整え直す仕組みを組み込むことで、どんな挿入順でも性能の上限を約束できるようにしたのがこれらの木である。
具体例
C++のstd::mapやJavaのTreeMapといった順序付きの連想配列は赤黒木で実装されており、平衡条件が緩く回転回数が少ないため更新の多い用途に向く。対してAVL木は高さがより低く抑えられるので、更新が少なく探索が支配的な用途で有利になる。Linuxカーネルも内部の管理構造に赤黒木を使っている。
試験での引っ掛け
平衡木が約束するのは「最悪でもO(log n)」であって、常に最速という意味ではない。件数が少なければ配列の線形探索のほうが速いこともあり、平衡を保つコストは挿入・削除の側に乗る。ハッシュ表との使い分けの軸は順序で、平衡木は要素の順序を保つため範囲検索や順次取り出しができるのに対し、ハッシュ表は等値検索しかできない。
関連用語
出た過去問
出典：令和7年度 春期 応用情報技術者試験 午前 問6（IPA）
図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。
正解：根5、左の子3（左の子1（左の子0、右の子2）、右の子4）、右の子7（左の子6）
要点：AVL木は高さの差が2になった節点で回転し、平衡を回復する
AVL木は各節点で左右部分木の高さの差を1以内に保つ平衡2分探索木である。まず1を追加しても各節点の高さの差は1以内に収まるため回転は起きないが、続けて0を追加すると2を根とする部分木で左に偏り高さの差が2になる。左の左に偏った形なので1を軸に右回転し、1が親、0と2がその左右の子になる。結果として根5の左部分木が「1を親に0と2」を左にもつ形へ整い、他の部分は変わらない。
出典・参考
公式シラバスの1 基礎理論 ＞ 1. データ構造 ＞ (2) データ構造の種類に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。