木構造 ── BST・AVL・Red-Black Tree

扱う概念：二分探索木（BST）、平衡条件、回転操作、AVL木、Red-Black Tree、木の走査（in-order / pre-order / post-order / level-order）

---

この章で何ができるようになるか：「なぜソート済み配列ではなく BST を使うのか」を説明でき、平衡木がどうやって O(log n) を保証しているかを理解できる。

---

二分探索木（BST：Binary Search Tree）

BST の不変条件：全てのノードについて、左の子孫 < 自分 < 右の子孫。

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if node is None:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val) -> bool:
        return self._search(self.root, val)

    def _search(self, node, val) -> bool:
        if node is None:
            return False
        if val == node.val:
            return True
        elif val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if node is None:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # 削除対象ノードが見つかった
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            # 子が2つ → 右部分木の最小値で置き換え
            successor = self._find_min(node.right)
            node.val = successor.val
            node.right = self._delete(node.right, successor.val)
        return node

    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

BST の問題：偏り

[1, 2, 3, 4, 5] を順に挿入すると：

  1
   \
    2
     \
      3
       \
        4
         \
          5

→ 実質的にリンクリスト → 全操作が O(n)

平衡木はこの偏りを自動的に修正する。

---

木の走査（Traversal）

      4
     / \
    2   6
   / \ / \
  1  3 5  7

def inorder(node):
    """中順（in-order）: 左 → 自分 → 右 → ソート済み出力"""
    if node:
        inorder(node.left)
        print(node.val, end=" ")  # 1 2 3 4 5 6 7
        inorder(node.right)

def preorder(node):
    """前順（pre-order）: 自分 → 左 → 右 → 木のシリアライズに使う"""
    if node:
        print(node.val, end=" ")  # 4 2 1 3 6 5 7
        preorder(node.left)
        preorder(node.right)

def postorder(node):
    """後順（post-order）: 左 → 右 → 自分 → 削除・解放に使う"""
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.val, end=" ")  # 1 3 2 5 7 6 4

def levelorder(root):
    """レベル順（BFS）: 段ごとに左から右"""
    from collections import deque
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")  # 4 2 6 1 3 5 7
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

---

AVL 木：最初の自己平衡BST（1962年）

平衡条件：全てのノードで「左右の部分木の高さの差が1以下」。

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def _height(self, node) -> int:
        return node.height if node else 0

    def _balance_factor(self, node) -> int:
        return self._height(node.left) - self._height(node.right)

    def _update_height(self, node):
        node.height = 1 + max(self._height(node.left), self._height(node.right))

    def _rotate_right(self, y):
        """右回転"""
        x = y.left
        t = x.right
        x.right = y
        y.left = t
        self._update_height(y)
        self._update_height(x)
        return x

    def _rotate_left(self, x):
        """左回転"""
        y = x.right
        t = y.left
        y.left = x
        x.right = t
        self._update_height(x)
        self._update_height(y)
        return y

    def _rebalance(self, node):
        self._update_height(node)
        bf = self._balance_factor(node)

        if bf > 1:  # 左が重い
            if self._balance_factor(node.left) < 0:
                node.left = self._rotate_left(node.left)  # LR ケース
            return self._rotate_right(node)                # LL ケース

        if bf < -1:  # 右が重い
            if self._balance_factor(node.right) > 0:
                node.right = self._rotate_right(node.right)  # RL ケース
            return self._rotate_left(node)                    # RR ケース

        return node

    def insert(self, root, val):
        if not root:
            return AVLNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        elif val > root.val:
            root.right = self.insert(root.right, val)
        return self._rebalance(root)

4つの回転ケース

LL（左の左に挿入）：右回転で解決
      z                y
     / \             /   \
    y   T4  →       x     z
   / \             / \   / \
  x   T3          T1 T2 T3 T4
 / \
T1  T2

RR（右の右に挿入）：左回転で解決
LR（左の右に挿入）：左回転 → 右回転
RL（右の左に挿入）：右回転 → 左回転

---

Red-Black Tree

AVL は厳密に平衡を保つため、挿入・削除のたびに回転が多く発生しうる。Red-Black Tree はより緩い平衡条件で回転を減らしつつ O(log n) を保証する。

5つの性質：

1. 全ノードは赤か黒
2. ルートは黒
3. 葉（NIL）は黒
4. 赤ノードの子は必ず黒（赤が連続しない）
5. 任意のノードから葉までの黒ノード数は全経路で同じ

これらの性質により、最長パス ≤ 最短パス × 2
→ 高さが O(log n) に収まることが保証される

AVL vs Red-Black Tree

	AVL	Red-Black Tree
平衡条件	厳密（高さ差 ≤ 1）	緩い（赤黒ルール）
木の高さ	≤ 1.44 × log(n)	≤ 2 × log(n)
検索速度	やや速い（より低い木）	やや遅い
挿入・削除	回転が多い（最大2回）	回転が少ない（最大3回）
使用例	データベースのインデックス	Java TreeMap, C++ std::map, Linux CFS

実務での選択：検索が多いなら AVL、挿入・削除が多いなら Red-Black Tree。

---

面接頻出問題

木の最大深さ

def max_depth(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

BST の検証

def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')) -> bool:
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

最近共通祖先（LCA）

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root  # p と q が左右に分かれている → root が LCA
    return left or right

---

まとめ

木構造	検索	挿入	削除	順序	使用例
BST（非平衡）	O(h)※	O(h)	O(h)	✅	教育用
AVL	O(log n)	O(log n)	O(log n)	✅	DB インデックス
Red-Black	O(log n)	O(log n)	O(log n)	✅	Java TreeMap, C++ map

※ h = 木の高さ。最悪 O(n)（偏った場合）

＋ － ⟳ ✕