平衡探索木 (Balanced Search Tree)
二分探索木は素朴に構築すると探索の worst case が に退化するため、木を平衡（balance）させて高さを に抑える各種データ構造の総称。
主な木
- Red-Black Tree — 探索・挿入・削除をいずれも worst case で行える。実用的なバランス木の代表。
- B-Tree / B+Tree — RDBMS のインデックスで使われる。ノードを大きく取りブロックデバイス（HDD等）と相性が良く、worst case でも検索 。
- Splay Tree / Heap — アクセス局所性を利用した自己調整木。
- Red-Green Trees — 永続性（immutable な赤ノード＋可変な緑ノード）を持つ木。Rust の構文木ライブラリ rowan で採用される。
ポイント
- 平衡条件をどう維持するか（回転・分割・マージ）が各データ構造の差別化点。永続性が要る用途では Red-Green のように構造共有を前提に設計する。