平衡木（AVL木・赤黒木）とは？

平衡木（AVL木・赤黒木）の意味

挿入・削除のたびに木の形を組み替え、高さをO(log n)に保ち続ける二分探索木の総称。AVL木は左右の部分木の高さの差を1以内に、赤黒木は色の規則により最長経路が最短経路の2倍以内になるよう制約し、いずれも回転操作で平衡を回復する。

平衡木（AVL木・赤黒木）の具体例

AVL木は平衡条件が厳しいぶん高さが低く探索が速いが、更新のたびに回転が増える。赤黒木は平衡が緩く回転回数が少ないため更新が多い用途に向き、多くの言語の標準ライブラリの順序付きマップは赤黒木で実装されている。

平衡木（AVL木・赤黒木）は試験でどう引っ掛けられる？

平衡木が保証するのは「最悪でもO(log n)」であって、常に最速という意味ではない。件数が少なければ配列の線形探索のほうが速いこともある。また平衡維持のコストは挿入・削除側にかかり、探索は無料ではない。ハッシュ表との使い分けの軸は順序で、平衡木は要素の順序を保つため範囲検索ができる。

平衡木（AVL木・赤黒木）と関連する用語

• 二分探索木（BST）
• B木・B+木
• 計算量（オーダー記法）
• ハッシュ表（連想配列）

平衡木（AVL木・赤黒木）が出た過去問

• 図の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」を左にもつ形へ整い、他の部分は変わらない。

  出典：令和7年度 春期 応用情報技術者試験 午前 問6（IPA）