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

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

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

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

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

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

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

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

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

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

• B+木インデックスが定義されている候補キーを利用して、1件のデータを検索するとき、データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオー…

  正解：logX

  要点：B+木の検索は木の高さ、すなわちO(log X)

  B+木は全ての葉が同じ深さになる平衡木で、1ノードに多数のキーを収めて木の高さを抑える構造である。1件の検索は根から葉までを1回ずつたどるのでアクセス回数は木の高さに等しく、データ総件数Xに対してO(log X)のオーダとなる。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問9（IPA）