平衡二分探索木（AVLと赤黒木）とは何か、また、なぜ重要なのか？

Question

Accepted Answer

単純なBSTは、キーがソート順で到着した場合、連結リストに退化する可能性があります（O(n)の操作）。**自己平衡二分探索木**—**AVL**および**赤黒木**—は、挿入/削除後にノードを自動的に**回転**させて、高さを~`log n`に保ち、**O(log n)**の操作を保証します。

## バランスの問題

```text
Unbalanced (insert 1,2,3,4):   Balanced after rotations:
  1                                  2
   \                                / \
    2                              1   3
     \                                  \
      3                                  4
   height ~ n (BAD)            height ~ log n (GOOD)
```

## AVL対赤黒木

| | AVL木 | 赤黒木 |
|---|---|---|
| バランスの厳格性 | 厳格（高さ平衡） | より緩い |
| 探索 | より高速（より短い） | やや遅い |
| 挿入/削除 | より多くの回転 | より少ない回転 |
| 最適な用途 | 読み取り集約的なワークロード | 書き込み集約的なワークロード |

## 保証される計算量

| 操作 | 時間 |
|---|---|
| 検索 | O(log n) |
| 挿入 | O(log n) |
| 削除 | O(log n) |

どちらも**回転**を通じてバランスを維持します—局所的なO(1)の再構成で、二分探索木の順序を保ちながら高さを削減します。

## なぜ重要なのか

平衡木は、標準ライブラリの順序付きマップとセット（例：Java `TreeMap`、C++ `std::map`は赤黒木を使用）を支え、ソート済み反復と保証された対数演算を提供します。

これは、二分探索木の順序付け*と*敵対的入力に対する厳密なパフォーマンス保証が必要な場合の答えです。

	AVL木	赤黒木
バランスの厳格性	厳格（高さ平衡）	より緩い
探索	より高速（より短い）	やや遅い
挿入/削除	より多くの回転	より少ない回転
最適な用途	読み取り集約的なワークロード	書き込み集約的なワークロード