每日算法 — 使用java实现替罪羊树：自平衡二叉搜索树的局部重建策略

引言

替罪羊树（Scapegoat Tree）是一种优雅的自平衡二叉搜索树，由Galperin和Rivest于1993年提出。与AVL树和红黑树通过旋转维持平衡不同，替罪羊树采用”局部重建”策略：当某个子树失去平衡时，直接将其重构为一棵完美平衡的二叉搜索树。本文用Java实现替罪羊树的完整操作，并分析其均摊时间复杂度。

核心算法原理

1. 平衡判定

替罪羊树使用参数 ( \alpha \in (0.5, 1) ) 控制平衡度。节点 ( u ) 的子树大小为 ( size(u) )，若其子节点 ( v ) 满足：

[ size(v) > \alpha \cdot size(u) ]

则 ( u ) 为”替罪羊”，需要重建。

2. 局部重建：中序遍历构建完美平衡树

找到替罪羊节点后，将其子树展平为有序数组，然后递归取中点作为根，构建完美平衡二叉搜索树。

3. 均摊分析

重建代价 ( O(size(u)) ) 可通过势能分析均摊到之前的插入操作中，证明插入、删除和查找的均摊时间复杂度均为 ( O(\log n) )。

Java完整实现

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

/**
 * 替罪羊树（Scapegoat Tree）完整实现
 * 核心算法：平衡因子判定 + 中序遍历重建 + 均摊复杂度保证
 */
public class ScapegoatTree<K extends Comparable<K>, V> {

    private static final double ALPHA = 0.6; // 平衡因子阈值
    private static final double LOG_INV_ALPHA = Math.log(1.0 / ALPHA);

    private class Node {
        K key;
        V value;
        Node left, right;
        int size; // 以该节点为根的子树节点数

        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.size = 1;
        }
    }

    private Node root;
    private int size; // 整棵树节点数
    private int maxSize; // 历史最大节点数，用于控制重建时机

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

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }

    /**
     * 获取子树大小
     */
    private int getSize(Node node) {
        return node == null ? 0 : node.size;
    }

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

    /**
     * 检查节点是否平衡
     */
    private boolean isBalanced(Node node) {
        if (node == null) return true;
        int leftSize = getSize(node.left);
        int rightSize = getSize(node.right);
        return leftSize <= (int)(ALPHA * node.size) && rightSize <= (int)(ALPHA * node.size);
    }

    /**
     * 查找键对应的值
     */
    public V get(K key) {
        Node cur = root;
        while (cur != null) {
            int cmp = key.compareTo(cur.key);
            if (cmp == 0) return cur.value;
            cur = cmp < 0 ? cur.left : cur.right;
        }
        return null;
    }

    /**
     * 插入键值对
     */
    public void put(K key, V value) {
        if (root == null) {
            root = new Node(key, value);
            size = 1;
            maxSize = 1;
            return;
        }

        // 使用路径记录寻找插入位置和替罪羊
        List<Node> path = new ArrayList<>();
        Node cur = root;
        while (true) {
            path.add(cur);
            int cmp = key.compareTo(cur.key);
            if (cmp == 0) {
                cur.value = value; // 更新已有键
                return;
            }
            Node next = cmp < 0 ? cur.left : cur.right;
            if (next == null) {
                // 找到插入位置
                Node newNode = new Node(key, value);
                if (cmp < 0) cur.left = newNode;
                else cur.right = newNode;
                break;
            }
            cur = next;
        }

        size++;
        if (size > maxSize) maxSize = size;

        // 从插入点向上更新大小并寻找替罪羊
        Node scapegoat = null;
        for (int i = path.size() - 1; i >= 0; i--) {
            Node node = path.get(i);
            updateSize(node);
            if (!isBalanced(node)) {
                scapegoat = node;
            }
        }

        // 重建最深的替罪羊子树
        if (scapegoat != null) {
            rebuild(scapegoat);
        }
    }

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

    /**
     * 从有序节点列表构建完美平衡BST
     */
    private Node buildBalanced(List<Node> nodes, int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        Node root = nodes.get(mid);
        root.left = buildBalanced(nodes, left, mid - 1);
        root.right = buildBalanced(nodes, mid + 1, right);
        updateSize(root);
        return root;
    }

    /**
     * 重建以target为根的子树
     */
    private void rebuild(Node target) {
        List<Node> nodes = new ArrayList<>();
        inorderCollect(target, nodes);

        // 断开与原树的连接，重建后重新连接
        Node newSubtree = buildBalanced(nodes, 0, nodes.size() - 1);
        target.key = newSubtree.key;
        target.value = newSubtree.value;
        target.left = newSubtree.left;
        target.right = newSubtree.right;
        target.size = newSubtree.size;
    }

    /**
     * 删除键（惰性删除策略：重建时真正删除）
     * 这里使用标记删除 + 适时重建
     */
    public void delete(K key) {
        root = deleteRecursive(root, key);
        size--;

        // 当实际节点数远小于历史最大值时，重建整棵树
        if (size < ALPHA * maxSize) {
            rebuildAll();
            maxSize = size;
        }
    }

    private Node deleteRecursive(Node node, K 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 successor = findMin(node.right);
            node.key = successor.key;
            node.value = successor.value;
            node.right = deleteRecursive(node.right, successor.key);
        }
        updateSize(node);
        return node;
    }

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

    /**
     * 重建整棵树
     */
    private void rebuildAll() {
        if (root == null) return;
        List<Node> nodes = new ArrayList<>();
        inorderCollect(root, nodes);
        root = buildBalanced(nodes, 0, nodes.size() - 1);
    }

    /**
     * 计算树高
     */
    public int height() {
        return height(root);
    }

    private int height(Node node) {
        if (node == null) return -1;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    /**
     * 中序遍历输出
     */
    public void inorder() {
        System.out.print("中序遍历: ");
        inorderPrint(root);
        System.out.println();
    }

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

    /**
     * 验证BST性质和平衡性
     */
    public boolean validate() {
        return validateNode(root, null, null) && checkBalance(root);
    }

    private boolean validateNode(Node node, K min, K max) {
        if (node == null) return true;
        if (min != null && node.key.compareTo(min) <= 0) return false;
        if (max != null && node.key.compareTo(max) >= 0) return false;
        return validateNode(node.left, min, node.key) && validateNode(node.right, node.key, max);
    }

    private boolean checkBalance(Node node) {
        if (node == null) return true;
        return isBalanced(node) && checkBalance(node.left) && checkBalance(node.right);
    }

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

        System.out.println("=== 替罪羊树实现与测试 ===\n");

        // 顺序插入，测试平衡重建
        System.out.println("顺序插入 1 到 20:");
        for (int i = 1; i <= 20; i++) {
            tree.put(i, "value" + i);
        }
        tree.inorder();
        System.out.printf("树大小: %d, 树高: %d%n", tree.size(), tree.height());
        System.out.printf("BST性质: %s, 平衡性: %s%n%n", tree.validate(), tree.checkBalance(tree.root));

        // 查找测试
        System.out.println("查找测试:");
        for (int i = 5; i <= 15; i += 5) {
            System.out.printf("  get(%d) = %s%n", i, tree.get(i));
        }

        // 删除测试
        System.out.println("\n删除 5, 10, 15:");
        tree.delete(5);
        tree.delete(10);
        tree.delete(15);
        tree.inorder();
        System.out.printf("树大小: %d, 树高: %d%n", tree.size(), tree.height());
        System.out.printf("BST性质: %s, 平衡性: %s%n", tree.validate(), tree.checkBalance(tree.root));
    }

    // 辅助方法
    private boolean checkBalance(Node node) {
        if (node == null) return true;
        return isBalanced(node) && checkBalance(node.left) && checkBalance(node.right);
    }
}

复杂度分析

总结

本文完整实现了替罪羊树，其核心优势在于：
1. 无旋转设计：相比AVL树的四种旋转和红黑树的多种情况，替罪羊树只需一种重建操作
2. 局部重建：不平衡时仅重建最小不平衡子树，而非整棵树
3. 均摊效率：通过势能分析保证 ( O(\log n) ) 均摊复杂度
4. 实现简洁：代码逻辑清晰，易于理解和维护

替罪羊树适合读多写少、对实现复杂度敏感的场景，是平衡二叉搜索树家族中一颗独特而优雅的明珠。