平衡二分木 vs 非平衡二分木

平衡木 vs 非平衡木

二分木が平衡であるとは、すべてのノードについて、左右の部分木の高さの差が最大 1 であることです。非平衡（偏った）木はノードが一方に集中し、パフォーマンスが O(log n) から O(n) に低下します。

視覚的比較

平衡（高さ 3）:           非平衡（高さ 5）:
        4                    1
       / \                    \
      2   6                    2
     / \ / \                    \
    1  3 5  7                    3
                                  \
                                   4
                                    \
                                     5

パフォーマンスへの影響

操作	平衡 O(log n)	非平衡 O(n)
探索	100万ノードで ~20 ステップ	最大 100万ステップ
挿入	100万ノードで ~20 ステップ	最大 100万ステップ
削除	100万ノードで ~20 ステップ	最大 100万ステップ

不均衡の原因

ソート済みまたはほぼソート済みのデータを通常の BST に挿入すると退化木が作成されます。[1, 2, 3, 4, 5] を挿入すると右に偏った連結リストになります。

自己平衡木

いくつかの木の変形は自動的にバランスを維持します：

• AVL 木: 厳密なバランス — すべてのノードで高さの差が最大 1。挿入/削除のたびに回転を使用。
• Red-Black 木: 緩やかなバランス — 高さが最大 2 * log(n+1) であることを保証。Java TreeMap、C++ std::map で使用。
• B-Tree: データベースやファイルシステムのディスクベースストレージに使用される多分岐平衡木。