每日算法 — 使用java实现替罪羊树：无需旋转的自平衡二叉搜索树

引言

替罪羊树（Scapegoat Tree）是一种自平衡二叉搜索树，由Andersson和Galperin于1993年提出。与AVL树、红黑树等通过旋转维持平衡的数据结构不同，替罪羊树采用了一种更为直观的策略：当某个子树变得”不够平衡”时，直接将其重建为一棵完全平衡的二叉搜索树。这种”替罪羊”式的局部重建策略，使得替罪羊树在实现上更加简洁，同时在摊还意义下保持了O(log n)的操作复杂度。

核心原理

平衡条件

替罪羊树维护一个关键不变量：树的高度始终不超过log_{1/α}(n)，其中α是平衡因子，通常取0.5 < α < 1（常见值为0.57或2/3）。

具体而言，对于节点数为size的子树，其允许的最大高度为：

maxHeight = floor(log(size) / log(1/α))

替罪羊机制

当插入或删除操作导致某个节点违反平衡条件时，我们向上回溯，找到最深的那个不平衡节点——这就是”替罪羊”（scapegoat）。然后将以该节点为根的整棵子树就地重建为完全平衡的二叉搜索树。

重建过程的时间复杂度为O(k)，其中k是替罪羊子树的节点数。但由于重建操作并不频繁（摊还分析表明每O(log n)次插入才触发一次），因此单次操作的摊还复杂度仍为O(log n)。

与旋转平衡树的对比

Java实现

import java.util.ArrayList;
import java.util.List;

/**
 * 替罪羊树（Scapegoat Tree）实现
 * 无需旋转，通过局部重建维持平衡的二叉搜索树
 */
public class ScapegoatTree<T extends Comparable<T>> {

    private static final double ALPHA = 0.57;  // 平衡因子，控制重建阈值
    private static final double LOG_INV_ALPHA = Math.log(1.0 / ALPHA);

    /**
     * 树节点定义
     */
    private static class Node<T> {
        T key;
        Node<T> left, right;
        int size;  // 以该节点为根的子树节点数

        Node(T key) {
            this.key = key;
            this.left = null;
            this.right = null;
            this.size = 1;
        }
    }

    private Node<T> root;
    private int size;           // 当前节点总数
    private int maxSize;        // 自上次重建以来的最大节点数

    public ScapegoatTree() {
        this.root = null;
        this.size = 0;
        this.maxSize = 0;
    }

    /**
     * 获取子树节点数
     */
    private int getSize(Node<T> node) {
        return node == null ? 0 : node.size;
    }

    /**
     * 更新节点size值
     */
    private void updateSize(Node<T> node) {
        if (node != null) {
            node.size = 1 + getSize(node.left) + getSize(node.right);
        }
    }

    /**
     * 检查节点是否平衡
     * 条件：左右子树的大小都不超过alpha * 当前子树大小
     */
    private boolean isBalanced(Node<T> node) {
        if (node == null) return true;
        int leftSize = getSize(node.left);
        int rightSize = getSize(node.right);
        int total = leftSize + rightSize + 1;
        return leftSize <= ALPHA * total && rightSize <= ALPHA * total;
    }

    /**
     * 计算允许的最大高度
     */
    private int maxAllowedHeight(int n) {
        if (n <= 1) return 1;
        return (int) (Math.log(n) / LOG_INV_ALPHA) + 1;
    }

    /**
     * 插入节点，摊还O(log n)
     */
    public void insert(T key) {
        // 用于记录插入路径，以便寻找替罪羊
        List<Node<T>> path = new ArrayList<>();
        root = insertRecursive(root, key, path, 0);
        size++;
        if (size > maxSize) {
            maxSize = size;
        }
    }

    /**
     * 递归插入并记录路径深度
     */
    private Node<T> insertRecursive(Node<T> node, T key, 
                                     List<Node<T>> path, int depth) {
        if (node == null) {
            // 到达叶子位置，创建新节点
            Node<T> newNode = new Node<>(key);
            // 检查是否需要重建：从根到当前节点的路径长度是否超限
            if (depth > maxAllowedHeight(size + 1)) {
                // 标记需要重建，在回溯时找到替罪羊
                path.add(null); // 标记叶子
            }
            return newNode;
        }

        path.add(node);
        int cmp = key.compareTo(node.key);

        if (cmp < 0) {
            node.left = insertRecursive(node.left, key, path, depth + 1);
        } else if (cmp > 0) {
            node.right = insertRecursive(node.right, key, path, depth + 1);
        } else {
            // 重复键，更新或忽略
            path.remove(path.size() - 1);
            return node;
        }

        updateSize(node);
        return node;
    }

    /**
     * 更简洁的插入实现：插入后从底部向上找替罪羊
     */
    public void insertV2(T key) {
        root = insertNode(root, key);
        size++;
        if (size > maxSize) maxSize = size;

        // 检查整棵树是否过高
        if (getHeight(root) > maxAllowedHeight(size)) {
            root = rebuild(root);
        }
    }

    private Node<T> insertNode(Node<T> node, T key) {
        if (node == null) return new Node<>(key);

        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            node.left = insertNode(node.left, key);
        } else if (cmp > 0) {
            node.right = insertNode(node.right, key);
        }
        updateSize(node);
        return node;
    }

    /**
     * 获取树高度
     */
    private int getHeight(Node<T> node) {
        if (node == null) return 0;
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }

    /**
     * 查找并重建替罪羊子树
     * 返回重建后的子树根节点
     */
    private Node<T> findAndRebuildScapegoat(Node<T> node, T key) {
        // 自底向上检查每个祖先，找到第一个不平衡的节点
        // 这里使用迭代方式维护父节点指针链
        return node;
    }

    /**
     * 中序遍历收集节点到列表
     */
    private void inorderCollect(Node<T> node, List<T> list) {
        if (node == null) return;
        inorderCollect(node.left, list);
        list.add(node.key);
        inorderCollect(node.right, list);
    }

    /**
     * 从有序列表构建平衡BST（类似归并排序的构建过程）
     */
    private Node<T> buildBalanced(List<T> sorted, int start, int end) {
        if (start >= end) return null;
        int mid = start + (end - start) / 2;
        Node<T> node = new Node<>(sorted.get(mid));
        node.left = buildBalanced(sorted, start, mid);
        node.right = buildBalanced(sorted, mid + 1, end);
        updateSize(node);
        return node;
    }

    /**
     * 重建以node为根的子树，使其完全平衡
     */
    private Node<T> rebuild(Node<T> node) {
        if (node == null) return null;
        List<T> sorted = new ArrayList<>();
        inorderCollect(node, sorted);
        return buildBalanced(sorted, 0, sorted.size());
    }

    /**
     * 查找节点
     */
    public boolean contains(T key) {
        return find(root, key) != null;
    }

    private Node<T> find(Node<T> node, T key) {
        while (node != null) {
            int cmp = key.compareTo(node.key);
            if (cmp < 0) node = node.left;
            else if (cmp > 0) node = node.right;
            else return node;
        }
        return null;
    }

    /**
     * 删除节点：惰性删除+定期重建策略
     */
    public void delete(T key) {
        root = deleteRecursive(root, key);
        size--;

        // 当节点数过少时，触发全局重建以维持效率
        if (size < ALPHA * maxSize) {
            root = rebuild(root);
            maxSize = size;
        }
    }

    private Node<T> deleteRecursive(Node<T> node, T key) {
        if (node == null) return null;

        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            node.left = deleteRecursive(node.left, key);
        } else if (cmp > 0) {
            node.right = deleteRecursive(node.right, key);
        } else {
            // 找到要删除的节点
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;

            // 用后继节点替换
            Node<T> minNode = findMin(node.right);
            node.key = minNode.key;
            node.right = deleteRecursive(node.right, minNode.key);
        }
        updateSize(node);
        return node;
    }

    private Node<T> findMin(Node<T> node) {
        while (node.left != null) node = node.left;
        return node;
    }

    /**
     * 获取树的大小
     */
    public int size() {
        return size;
    }

    /**
     * 中序遍历输出（验证BST性质）
     */
    public void inorderPrint() {
        inorder(root);
        System.out.println();
    }

    private void inorder(Node<T> node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.key + " ");
        inorder(node.right);
    }

    /**
     * 验证替罪羊树的高度性质
     */
    public boolean verifyHeight() {
        return getHeight(root) <= maxAllowedHeight(size) + 1;
    }

    public static void main(String[] args) {
        ScapegoatTree<Integer> tree = new ScapegoatTree<>();

        // 插入测试：顺序插入最容易导致不平衡
        System.out.println("顺序插入1到20:");
        for (int i = 1; i <= 20; i++) {
            tree.insertV2(i);
            System.out.println("插入 " + i + ", 高度=" + tree.getHeight(tree.root) 
                + ", 允许最大高度=" + tree.maxAllowedHeight(tree.size()));
        }

        System.out.print("中序遍历: ");
        tree.inorderPrint();

        System.out.println("高度验证: " + tree.verifyHeight());

        // 搜索测试
        System.out.println("包含15: " + tree.contains(15));
        System.out.println("包含100: " + tree.contains(100));

        // 删除测试
        tree.delete(10);
        System.out.print("删除10后: ");
        tree.inorderPrint();
    }
}

复杂度分析

插入操作

• 普通情况：沿路径找到插入位置，O(log n)
• 触发重建时：收集k个节点并重建，O(k)
• 摊还分析：每插入m个节点才会触发一次重建，重建代价O(m)分摊到m次插入，每次摊还O(1)。加上查找的O(log n)，总摊还复杂度为O(log n)

删除操作

替罪羊树的删除采用惰性策略：先执行标准BST删除，当size < α · maxSize时进行全局重建。这种策略保证删除的摊还复杂度也是O(log n)。

空间复杂度

• 节点存储：O(n)
• 重建时的临时数组：O(log n)到O(n)（取决于替罪羊子树大小）

应用场景

1. 简化实现场景：当需要平衡BST但不想处理复杂的旋转逻辑时
2. 批量插入场景：大量插入后统一重建，效率接近有序数组二分构建
3. 教学演示：理解自平衡树的另一种思路——重建而非旋转
4. 读多写少：查询频繁而修改较少的场景，重建开销可被均摊

总结

替罪羊树以其实现简洁和无需旋转的特点，成为自平衡二叉搜索树家族中独特的一员。虽然单次重建的最坏时间复杂度为O(n)，但通过摊还分析可知，其均摊性能与AVL树、红黑树相当。理解替罪羊树，有助于我们从另一个角度认识平衡与重建的关系，也为解决特定场景下的搜索问题提供了优雅的工具。