无解的博客

Appearance

wxvirus2026-10-05
4475
20.2m

替罪羊树（Scapegoat Tree） ​

你有没有被红黑树的 5 条规则折磨过？左旋右旋、色变判断、插入修复的 8 种情况……代码写着写着，人已经麻了 😵。

我当年学红黑树的时候，边学边忘，前后折腾了两周才勉强能写出来。后来学 Treap，花了半天就上手了——随机优先级嘛，简单。但 Treap 的问题是，它的平衡是"概率保证"，最坏情况依然可能退化（虽然概率极低）。

今天要介绍的替罪羊树（Scapegoat Tree），则是一个完全不同的思路：不需要旋转，也不需要随机权重，发现不平衡就直接把整棵子树拍平重构成平衡的。整个实现比红黑树简单几个数量级，理论上最坏情况也是 O(log n)，非常适合面试和工程实战。

原理拆解 ​

1. BST 的退化问题 ​

先回顾一下 BST 为什么会退化——当插入顺序接近有序时，树就变成一条链：

按升序插入 [1, 2, 3, 4, 5, 6, 7]：

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

高度 = 7，退化成链表，O(log n) → O(n)

平衡树的核心目标：无论插入顺序如何，树的高度始终控制在 O(log n)。

2. 替罪羊树的核心思想 ​

替罪羊树借鉴了一个很有意思的想法——找"替罪羊"来承担责任。

插入一个新节点后，从根节点往下走，找到插入位置。如果新节点插入后导致某个节点的子树高度失衡，这个节点就是"替罪羊"。然后，把这棵以替罪羊为根的子树整棵拍平（flatten）成有序数组，再用 O(n) 时间重建为一棵完全平衡的二叉树。

失衡的替罪羊节点：

          8
        /   \
       4    [12]      ← 替罪羊（假设左右子树高度差超限）
      / \     \
     2   6    15

拍平重构成完全平衡的树：

          8
        /   \
       4    12
      / \   /
     2   6 15

高度从 3 降到 2，重新平衡 ✓

关键问题：什么时候算"失衡"？替罪羊是谁？

3. 重量平衡树（Weight-Balanced Tree） ​

替罪羊树是一种重量平衡树（Weight-Balanced Tree），它用子树的大小（节点数）来判断是否平衡，而不是用高度。

定义一个平衡因子 α（alpha），通常取 0.5 ≤ α ≤ 0.75，常见值是 0.75。一个节点的左右子树如果满足以下条件，就是平衡的：

size(left)  ≤ α * size(node)
size(right) ≤ α * size(node)

也就是说，每个子树的大小不超过整棵树的 α 倍。如果不满足，节点就失衡，这个节点就是我们要找的替罪羊。

α = 0.75

         8 (size=7)
       /   \
  (size=5)  (size=1)   ← size(right)=1, 1 > 7*0.75? No.
                              但 left=5 > 7*0.75? Yes → 失衡！

替罪羊 = 节点 8

为什么 α 通常取 0.75 而不是 0.5？

  • α = 0.5 是 AVL 树的平衡标准，非常严格，重构频率很高
  • α = 0.75 比较折中，允许更大的子树，重构次数少很多
  • α 越小越平衡，但重构越频繁；α 越大重构越少，但树越高

4. 插入操作与替罪羊寻找 ​

插入新节点 v 的过程：

  1. 按普通 BST 插入 v（O(log n)）
  2. 从 v 的父节点往上回溯，检查每个祖先是否平衡
  3. 第一个发现失衡的节点就是替罪羊 scapegoat
  4. 以 scapegoat 为根，将子树拍平成有序数组，再重构为平衡树
  5. 重构后树高恢复 O(log n)
插入节点 1.5 后的回溯路径：

          8           size=8
        /   \
       4    12        sizes: 4, 2
      / \
     2   6            sizes: 1, 1
      \
       3               (这里插入了 1.5)
        \
         1.5          ← 新节点

从 3 回溯 → 2 → 4 → 8，逐层检查平衡性

假设 8 失衡 → 8 是替罪羊 → 重构以 8 为根的子树

替罪羊一定存在吗？ 存在。根节点保证是替罪羊（因为如果整棵树都失衡，根就是第一个检测到的失衡点）。所以回溯的上界是树的高度 O(log n)。

5. 重构（Rebuild）操作 ​

这是替罪羊树最核心的操作，也是它区别于 AVL/红黑树的关键——不需要旋转。

重构分两步：

第一步：拍平（Flatten） 用中序遍历把子树所有节点收集到一个数组 nodes[]，得到有序序列。

第二步：重建（Build） 递归地从中间取节点作为根，左右递归构建左右子树。这和构建平衡 BST 的经典方法完全一致。

typescript
/**
 * 将有序数组重建成完全平衡的二叉搜索树
 * 核心思想：每次选中间元素做根，左右均分
 *
 *        nodes: [1, 2, 3, 4, 5, 6, 7]
 *                  ↑ mid = 4
 *                  4
 *               /     \
 *           [1,2,3]  [5,6,7]
 *              2        6
 *            /  \      /  \
 *           1    3    5    7
 *
 * 完全平衡，高度 = floor(log2(7)) + 1 = 3
 */
function buildBalanced(nodes: TreeNode[], lo: number, hi: number): TreeNode | null {
  if (lo >= hi) return null;

  const mid = Math.floor((lo + hi) / 2);
  const root = nodes[mid];
  root.left = buildBalanced(nodes, lo, mid);
  root.right = buildBalanced(nodes, mid + 1, hi);
  return root;
}

这个 buildBalanced 的时间复杂度是 O(n)，其中 n 是子树节点数。为什么能 O(n)？因为每个节点只被访问常数次（一次拍平 + 一次建树）。

6. 删除操作 ​

替罪羊树支持两种删除策略：

策略一：惰性删除（Lazy Delete） 标记节点为"已删除"，查询时跳过。简单，但可能导致树变"胖"（虚假节点太多影响平衡判断）。定期或按需整体重构。

策略二：真实删除 和普通 BST 删除一样，删除后从父节点回溯检查替罪羊，失衡则重构。实现稍复杂但更精确。

大多数替罪羊树实现用惰性删除，因为实现简单，而且当"假节点"太多时（超过子树大小的一定比例），一次性重构整棵树即可。

代码实现 ​

TypeScript ​

typescript
/**
 * 替罪羊树（Scapegoat Tree）
 *
 * 核心特点：
 * - 不旋转，纯重构平衡
 * - 重量平衡（weight-balanced），用子树大小判断平衡性
 * - α（alpha）平衡因子，通常取 0.75
 * - 插入后最多重构 O(log n) 个节点（摊销 O(1)）
 */

class ScapegoatNode<T> {
  val: T;
  size: number; // 子树节点数（含自身）
  deleted: boolean; // 惰性删除标记
  left: ScapegoatNode<T> | null;
  right: ScapegoatNode<T> | null;

  constructor(val: T) {
    this.val = val;
    this.size = 1;
    this.deleted = false;
    this.left = null;
    this.right = null;
  }
}

export class ScapegoatTree<T = number> {
  private root: ScapegoatNode<T> | null = null;
  private readonly alpha: number;
  private readonly maxSize: () => number; // 历史最大 size，用于判断是否需要全局重构
  private _size: number = 0; // 实时 size（非删除节点数）
  private _maxSize: number = 0;

  constructor(alpha: number = 0.75) {
    if (alpha < 0.5 || alpha >= 1) {
      throw new Error('alpha must be in [0.5, 1)');
    }
    this.alpha = alpha;
    this.maxSize = () => this._maxSize;
  }

  // --- 辅助方法 ---

  /** 获取节点大小（计入惰性删除标记） */
  private getSize(node: ScapegoatNode<T> | null): number {
    return node ? node.size : 0;
  }

  /** 更新节点的 size（向上回溯更新） */
  private updateSize(node: ScapegoatNode<T>): void {
    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);
  }

  /** 判断节点是否平衡（α-平衡） */
  private isBalanced(node: ScapegoatNode<T>): boolean {
    const leftSize = this.getSize(node.left);
    const rightSize = this.getSize(node.right);
    return (
      leftSize <= this.alpha * node.size &&
      rightSize <= this.alpha * node.size
    );
  }

  /** 中序遍历收集节点到数组（拍平） */
  private flatten(node: ScapegoatNode<T> | null, nodes: ScapegoatNode<T>[]): void {
    if (!node) return;
    this.flatten(node.left, nodes);
    nodes.push(node);
    this.flatten(node.right, nodes);
  }

  /**
   * 从有序数组重建平衡二叉树
   * 类似二分查找构建平衡 BST，O(n)
   */
  private buildBalanced(
    nodes: ScapegoatNode<T>[],
    lo: number,
    hi: number,
  ): ScapegoatNode<T> | null {
    if (lo >= hi) return null;
    const mid = Math.floor((lo + hi) / 2);
    const root = nodes[mid];
    root.left = this.buildBalanced(nodes, lo, mid);
    root.right = this.buildBalanced(nodes, mid + 1, hi);
    this.updateSize(root);
    return root;
  }

  /** 重建以 node 为根的子树（通过父节点的引用替换） */
  private rebuild(nodeRef: { current: ScapegoatNode<T> | null }): void {
    const nodes: ScapegoatNode<T>[] = [];
    this.flatten(nodeRef.current, nodes);
    nodeRef.current = this.buildBalanced(nodes, 0, nodes.length);
  }

  // --- 核心操作 ---

  /** 插入值 */
  insert(val: T): void {
    if (!this.root) {
      this.root = new ScapegoatNode<T>(val);
      this._size++;
      this._maxSize = Math.max(this._maxSize, this._size);
      return;
    }

    // 用一个引用对象来追踪要插入位置的父节点引用
    const insertedRef: { node: ScapegoatNode<T> | null; side: 'left' | 'right' } = {
      node: null,
      side: 'left',
    };

    const cmp = (a: T, b: T) => {
      if (a < b) return -1;
      if (a > b) return 1;
      return 0;
    };

    // 找插入位置，同时记录路径
    let cur = this.root;
    const path: { node: ScapegoatNode<T>; side: 'left' | 'right' }[] = [];

    while (true) {
      const c = cmp(val, cur.val);
      if (c <= 0) {
        if (!cur.left) {
          cur.left = new ScapegoatNode<T>(val);
          insertedRef.node = cur;
          insertedRef.side = 'left';
          break;
        }
        path.push({ node: cur, side: 'left' });
        cur = cur.left;
      } else {
        if (!cur.right) {
          cur.right = new ScapegoatNode<T>(val);
          insertedRef.node = cur;
          insertedRef.side = 'right';
          break;
        }
        path.push({ node: cur, side: 'right' });
        cur = cur.right;
      }
    }

    this._size++;
    this._maxSize = Math.max(this._maxSize, this._size);

    // 从新节点的父节点开始向上回溯，找替罪羊
    let scapegoat: ScapegoatNode<T> | null = insertedRef.node;
    for (const p of path) {
      this.updateSize(p.node);
      if (!this.isBalanced(p.node)) {
        scapegoat = p.node;
        break;
      }
    }

    // 找到了替罪羊，重构以其为根的子树
    if (scapegoat) {
      // 找到 scapegoat 在其父节点中的引用
      const scapegoatRef: { current: ScapegoatNode<T> | null } = { current: null };

      if (!this.root || scapegoat === this.root) {
        scapegoatRef.current = this.root;
        this.rebuild(scapegoatRef);
        this.root = scapegoatRef.current;
      } else {
        // 在 path 中找到 scapegoat 的父节点引用
        for (const p of path) {
          if (p.node.left === scapegoat) {
            scapegoatRef.current = p.node.left;
            this.rebuild(scapegoatRef);
            p.node.left = scapegoatRef.current;
            break;
          } else if (p.node.right === scapegoat) {
            scapegoatRef.current = p.node.right;
            this.rebuild(scapegoatRef);
            p.node.right = scapegoatRef.current;
            break;
          }
        }
      }
    } else {
      // 没有人失衡，更新到根的路径上所有节点的 size
      // （已经在上面的回溯中更新了）
    }
  }

  /** 查询值是否存在 */
  contains(val: T): boolean {
    let cur = this.root;
    const cmp = (a: T, b: T) => {
      if (a < b) return -1;
      if (a > b) return 1;
      return 0;
    };

    while (cur) {
      const c = cmp(val, cur.val);
      if (c === 0) return !cur.deleted;
      cur = c < 0 ? cur.left : cur.right;
    }
    return false;
  }

  /** 删除值（惰性删除） */
  delete(val: T): boolean {
    let cur = this.root;
    const cmp = (a: T, b: T) => {
      if (a < b) return -1;
      if (a > b) return 1;
      return 0;
    };

    while (cur) {
      const c = cmp(val, cur.val);
      if (c === 0) {
        if (!cur.deleted) {
          cur.deleted = true;
          this._size--;
          // 惰性删除后，如果真实节点数太少（小于 maxSize * alpha），整体重构
          if (this._size < this.alpha * this._maxSize) {
            this.rebuildTree();
          }
        }
        return true;
      }
      cur = c < 0 ? cur.left : cur.right;
    }
    return false;
  }

  /** 整体重构树（清除惰性删除标记） */
  private rebuildTree(): void {
    const nodes: ScapegoatNode<T>[] = [];
    this.flatten(this.root, nodes);
    // 过滤掉 deleted 的节点
    const alive: ScapegoatNode<T>[] = [];
    for (const n of nodes) {
      if (!n.deleted) {
        n.left = null;
        n.right = null;
        alive.push(n);
      }
    }
    this.root = this.buildBalanced(alive, 0, alive.length);
    this._maxSize = this._size;
  }

  /** 中序遍历（验证树结构） */
  inOrderTraversal(node: ScapegoatNode<T> | null, result: T[] = []): T[] {
    if (!node) return result;
    this.inOrderTraversal(node.left, result);
    if (!node.deleted) result.push(node.val);
    this.inOrderTraversal(node.right, result);
    return result;
  }
}

// ==================== 使用示例 ====================

const tree = new ScapegoatTree<number>();

// 模拟有序插入（会导致普通 BST 退化）
const sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
for (const v of sorted) {
  tree.insert(v);
}

console.log('contains(5):', tree.contains(5)); // true
console.log('contains(99):', tree.contains(99)); // false
console.log('in-order:', tree.inOrderTraversal(tree['root'])); // [1, 2, 3, ..., 10]

tree.delete(5);
console.log('after delete(5), contains(5):', tree.contains(5)); // false

Python ​

python
from typing import Generic, TypeVar, Optional, List

T = TypeVar('T')


class ScapegoatNode(Generic[T]):
    """替罪羊树节点"""
    __slots__ = ('val', 'size', 'deleted', 'left', 'right')

    def __init__(self, val: T):
        self.val: T = val
        self.size: int = 1        # 子树节点数（含自身）
        self.deleted: bool = False  # 惰性删除标记
        self.left: Optional['ScapegoatNode[T]'] = None
        self.right: Optional['ScapegoatNode[T]'] = None


class ScapegoatTree(Generic[T]):
    """替罪羊树 —— 不旋转的自平衡 BST

    核心思路：
    1. 用 α（alpha）平衡因子判断子树是否失衡
    2. 插入时找到"替罪羊"节点，以其为根重构子树
    3. 删除采用惰性删除，过多假节点时整体重构

    α 常用值 0.75，越小越平衡但重构越频繁
    """

    def __init__(self, alpha: float = 0.75):
        if not (0.5 <= alpha < 1):
            raise ValueError('alpha must be in [0.5, 1)')
        self.alpha = alpha
        self.root: Optional[ScapegoatNode[T]] = None
        self._size: int = 0         # 有效节点数
        self._max_size: int = 0     # 历史最大有效节点数

    # ---- 辅助函数 ----

    def _size_of(self, node: Optional[ScapegoatNode[T]]) -> int:
        return node.size if node else 0

    def _update(self, node: ScapegoatNode[T]) -> None:
        node.size = 1 + self._size_of(node.left) + self._size_of(node.right)

    def _is_balanced(self, node: ScapegoatNode[T]) -> bool:
        """判断节点是否满足 α-平衡"""
        left_sz = self._size_of(node.left)
        right_sz = self._size_of(node.right)
        return (left_sz <= self.alpha * node.size and
                right_sz <= self.alpha * node.size)

    def _flatten(self, node: Optional[ScapegoatNode[T]],
                 nodes: List[ScapegoatNode[T]]) -> None:
        """中序遍历拍平子树"""
        if not node:
            return
        self._flatten(node.left, nodes)
        nodes.append(node)
        self._flatten(node.right, nodes)

    def _build(self, nodes: List[ScapegoatNode[T]],
               lo: int, hi: int) -> Optional[ScapegoatNode[T]]:
        """从有序数组重建完全平衡的 BST，O(n)"""
        if lo >= hi:
            return None
        mid = (lo + hi) // 2
        root = nodes[mid]
        root.left = self._build(nodes, lo, mid)
        root.right = self._build(nodes, mid + 1, hi)
        self._update(root)
        return root

    def _rebuild_at(self, parent, side: str) -> None:
        """重定向 parent[side] 指向重构后的子树"""
        nodes: List[ScapegoatNode[T]] = []
        subtree = getattr(parent, side)
        self._flatten(subtree, nodes)
        # 过滤已删除节点
        alive = [n for n in nodes if not n.deleted]
        for n in alive:
            n.left = None
            n.right = None
        new_root = self._build(alive, 0, len(alive))
        setattr(parent, side, new_root)

    # ---- 核心操作 ----

    def insert(self, val: T) -> None:
        """插入值"""
        cmp = (lambda a, b: -1 if a < b else (1 if a > b else 0))

        if not self.root:
            self.root = ScapegoatNode(val)
            self._size = 1
            self._max_size = 1
            return

        cur = self.root
        path: List[tuple] = []  # 记录路径：(parent, side)

        while True:
            c = cmp(val, cur.val)
            if c <= 0:
                if not cur.left:
                    cur.left = ScapegoatNode(val)
                    path.append((cur, 'left'))
                    break
                path.append((cur, 'left'))
                cur = cur.left
            else:
                if not cur.right:
                    cur.right = ScapegoatNode(val)
                    path.append((cur, 'right'))
                    break
                path.append((cur, 'right'))
                cur = cur.right

        self._size += 1
        self._max_size = max(self._max_size, self._size)

        # 向上回溯找替罪羊
        scapegoat = None
        for parent, side in reversed(path):
            self._update(parent)
            if not self._is_balanced(parent):
                scapegoat = (parent, side)
                break

        # 重构替罪羊子树
        if scapegoat:
            parent, side = scapegoat
            self._rebuild_at(parent, side)
        else:
            # 没有失衡，更新路径上所有节点
            for parent, _ in path:
                self._update(parent)

    def contains(self, val: T) -> bool:
        """查询值是否存在"""
        cur = self.root
        cmp = (lambda a, b: -1 if a < b else (1 if a > b else 0))

        while cur:
            c = cmp(val, cur.val)
            if c == 0:
                return not cur.deleted
            cur = cur.left if c < 0 else cur.right
        return False

    def delete(self, val: T) -> bool:
        """删除值（惰性删除）"""
        cur = self.root
        cmp = (lambda a, b: -1 if a < b else (1 if a > b else 0))

        while cur:
            c = cmp(val, cur.val)
            if c == 0:
                if not cur.deleted:
                    cur.deleted = True
                    self._size -= 1
                    # 节点太少，整体重构
                    if self._size < self.alpha * self._max_size:
                        self._rebuild_tree()
                return True
            cur = cur.left if c < 0 else cur.right
        return False

    def _rebuild_tree(self) -> None:
        """整体重构树，清除惰性删除标记"""
        nodes: List[ScapegoatNode[T]] = []
        self._flatten(self.root, nodes)
        alive = [n for n in nodes if not n.deleted]
        for n in alive:
            n.left = None
            n.right = None
        self.root = self._build(alive, 0, len(alive))
        self._max_size = self._size

    def inorder(self) -> List[T]:
        """中序遍历（验证）"""
        result: List[T] = []
        nodes: List[ScapegoatNode[T]] = []
        self._flatten(self.root, nodes)
        for n in nodes:
            if not n.deleted:
                result.append(n.val)
        return result


# ==================== 使用示例 ====================

if __name__ == '__main__':
    tree = ScapegoatTree[int]()

    # 有序插入 —— 普通 BST 会退化，但替罪羊树会自动重构保持平衡
    for v in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]:
        tree.insert(v)

    print('contains(5):', tree.contains(5))    # True
    print('contains(99):', tree.contains(99))  # False
    print('in-order:', tree.inorder())         # [1, 2, 3, ..., 10]

    tree.delete(5)
    print('after delete(5):', tree.contains(5))  # False

    # 乱序插入也保持平衡
    tree2 = ScapegoatTree[int]()
    import random
    for v in random.sample(range(100), 30):
        tree2.insert(v)
    print('after random inserts, size:', tree2.inorder().__len__())  # 30

复杂度分析 ​

操作平均 / 摊销最坏
查找O(log n)O(n)
插入O(log n)（摊销 O(1)）O(n)
删除（惰性）O(log n)O(n)
重构单子树O(k)（k=子树节点数）O(n)
空间O(n)O(n)

为什么插入是摊销 O(1)？

每次插入最多只会触发一次重构，重构一个大小为 k 的子树需要 O(k) 时间。虽然单次重构可能较慢（如果替罪羊子树很大），但由于一次重构后，这个子树的高度大幅降低（从可能 O(k) 降到 O(log k)），后续的插入要经过很多次才能再次触发同一位置的重构。

摊销下来，每次插入的重构代价是 O(1)，总插入成本是 O(log n)（找插入位置 + 可能的重构）。

关键参数 α 的影响：

α 越小（如 0.5）→ 平衡越严格 → 树越矮（查询更快）→ 重构越频繁（插入更慢）
α 越大（如 0.75）→ 平衡越宽松 → 树稍高（查询略慢）→ 重构更少（插入更快）

实际工程中 0.75 是最常用的折中值。

替罪羊树 vs 其他平衡树 ​

特性替罪羊树AVL 树红黑树Treap
平衡方式整体重构旋转旋转 + 色变随机优先级
实现难度⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐
最坏查询O(log n)O(log n)O(log n)O(n)（概率极低）
最坏插入O(log n)O(log n)O(log n)O(log n)（概率）
需要额外存储size 字段高度颜色优先级
重构粒度整棵失衡子树单/双旋单/双旋可能整树
工业应用较少数据库索引C++ map/set, Java TreeMap教学/简单场景

替罪羊树的独特优势：

  1. 代码最简单——不需要写任何旋转逻辑，只有拍平+重建
  2. 重构整棵树不影响其他分支——不像旋转会影响周围节点的父亲/孩子指针
  3. 易于持久化（Persistent）——重构返回新节点引用，原树不变，非常适合函数式编程和版本控制场景

实际应用场景 ​

1. 函数式编程 / 不可变数据结构 ​

重构操作天然产生新节点引用（不修改原节点），非常适合**持久化（Immutable）**场景。每次重构后，原来的树不受影响，可以保留历史版本。

2. 数据库索引（类 LSM-Tree 场景） ​

某些数据库在合并 SSTable 时会用到替罪羊树类似的"整体重构"思路：数据积累到一定程度后，把乱序数据整体排序重写，而不是逐个插入维护有序性。

3. 教学与面试 ​

替罪羊树是解释"摊销分析"和"重量平衡"概念的绝佳例子，比红黑树的 5 条规则好懂得多，也比 Treap 的概率平衡更符合算法直觉。

小结 ​

替罪羊树的核心哲学就一句话：发现问题不修，直接推倒重来。

这种思路在工程上其实很常见——与其在失衡的树上小心翼翼地旋转，不如直接拍平重构成完全平衡的树。代码简单、理论扎实、实现友好，除了工业界用得不多（主要还是红黑树/AVL），简直是面试和学习的完美素材 🎉。

如果你下次被问到"除了 AVL 和红黑树，还有什么平衡 BST 的方案？"——替罪羊树就是那个让人眼前一亮的答案。

最近更新