每日算法 — 使用java实现Splay树：自调整二叉搜索树与摊还分析

一、Splay 树核心思想

Splay 树（伸展树）是由 Tarjan 和 Sleator 于 1985 年提出的自调整二叉搜索树。与普通平衡树（如 AVL、红黑树）通过显式维护平衡因子不同，Splay 树通过伸展操作（Splay）将最近访问的节点旋转到根，利用局部性原理使得高频访问的元素靠近根节点，从而在均摊意义下达到 O(log n) 的操作复杂度。

核心优势：
– 无需存储额外的平衡信息（高度、颜色等）
– 高频访问的元素自动上浮，缓存友好
– 实现简洁，常数因子小
– 支持分裂（Split）与合并（Merge）操作

二、节点定义与基础结构

/**
 * Splay 树（伸展树）完整实现
 * 支持插入、删除、查找、分裂、合并操作
 */
public class SplayTree<T extends Comparable<T>> {

    /**
     * 树节点
     */
    static class Node<T> {
        T key;
        Node<T> left, right, parent;
        int size; // 子树大小，用于顺序统计

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

    private Node<T> root;
    private int size;

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

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

    /**
     * 判断树是否为空
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 更新节点大小（子树节点数）
     */
    private void updateSize(Node<T> node) {
        if (node != null) {
            node.size = 1 + getSize(node.left) + getSize(node.right);
        }
    }

    private int getSize(Node<T> node) {
        return node == null ? 0 : node.size;
    }

三、核心旋转操作：Zig、Zig-Zig、Zig-Zag

Splay 操作根据目标节点与其父节点、祖父节点的相对位置，分为三种旋转：

    /**
     * 右旋（Zig）：目标节点是父节点的左孩子
     *       p                 x
     *      / \               / \
     *     x   C    -->      A   p
     *    / \                   / \
     *   A   B                 B   C
     */
    private void rotateRight(Node<T> p) {
        Node<T> x = p.left;
        if (x == null) return;

        p.left = x.right;
        if (x.right != null) x.right.parent = p;
        x.parent = p.parent;

        if (p.parent == null) {
            root = x;
        } else if (p == p.parent.left) {
            p.parent.left = x;
        } else {
            p.parent.right = x;
        }

        x.right = p;
        p.parent = x;

        updateSize(p);
        updateSize(x);
    }

    /**
     * 左旋（Zig 的镜像）：目标节点是父节点的右孩子
     */
    private void rotateLeft(Node<T> p) {
        Node<T> x = p.right;
        if (x == null) return;

        p.right = x.left;
        if (x.left != null) x.left.parent = p;
        x.parent = p.parent;

        if (p.parent == null) {
            root = x;
        } else if (p == p.parent.left) {
            p.parent.left = x;
        } else {
            p.parent.right = x;
        }

        x.left = p;
        p.parent = x;

        updateSize(p);
        updateSize(x);
    }

    /**
     * 伸展操作：将指定节点旋转到根
     * 分类讨论三种情况：
     * 1. Zig：父节点是根，单旋一次
     * 2. Zig-Zig：目标节点和父节点同为左/右孩子，先旋父节点再旋目标节点
     * 3. Zig-Zag：目标节点和父节点方向不同，旋两次目标节点
     */
    private void splay(Node<T> x) {
        while (x.parent != null) {
            Node<T> p = x.parent;
            Node<T> g = p.parent;

            if (g == null) {
                // Zig：父节点是根
                if (x == p.left) {
                    rotateRight(p);
                } else {
                    rotateLeft(p);
                }
            } else if (x == p.left && p == g.left) {
                // Zig-Zig：左-左
                rotateRight(g);
                rotateRight(p);
            } else if (x == p.right && p == g.right) {
                // Zig-Zig：右-右
                rotateLeft(g);
                rotateLeft(p);
            } else if (x == p.right && p == g.left) {
                // Zig-Zag：左-右
                rotateLeft(p);
                rotateRight(g);
            } else {
                // Zig-Zag：右-左
                rotateRight(p);
                rotateLeft(g);
            }
        }
        root = x;
    }

四、查找、插入与删除

    /**
     * 查找键值，并将该节点伸展到根
     * @return 如果找到返回对应节点，否则返回最后访问的节点（用于插入定位）
     */
    public Node<T> search(T key) {
        Node<T> curr = root;
        Node<T> last = null;

        while (curr != null) {
            last = curr;
            int cmp = key.compareTo(curr.key);
            if (cmp == 0) {
                splay(curr);
                return curr;
            } else if (cmp < 0) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }

        // 未找到，将最后访问的节点伸展到根（为插入做准备）
        if (last != null) {
            splay(last);
        }
        return null;
    }

    /**
     * 插入键值
     */
    public void insert(T key) {
        if (root == null) {
            root = new Node<>(key);
            size++;
            return;
        }

        Node<T> found = search(key);
        if (found != null && found.key.compareTo(key) == 0) {
            return; // 已存在，不重复插入
        }

        // 此时 root 是最后访问的节点（最接近 key 的节点）
        Node<T> newNode = new Node<>(key);
        int cmp = key.compareTo(root.key);

        if (cmp < 0) {
            newNode.left = root.left;
            if (root.left != null) root.left.parent = newNode;
            newNode.right = root;
            root.left = null;
            root.parent = newNode;
        } else {
            newNode.right = root.right;
            if (root.right != null) root.right.parent = newNode;
            newNode.left = root;
            root.right = null;
            root.parent = newNode;
        }

        root = newNode;
        root.parent = null;
        size++;

        // 更新路径上的 size
        updateSize(root.left);
        updateSize(root.right);
        updateSize(root);
    }

    /**
     * 删除键值
     * 策略：将目标节点伸展到根，然后合并左右子树
     */
    public boolean delete(T key) {
        Node<T> target = search(key);
        if (target == null || target.key.compareTo(key) != 0) {
            return false;
        }

        // 此时 target 是根
        Node<T> leftTree = root.left;
        Node<T> rightTree = root.right;

        if (leftTree != null) leftTree.parent = null;
        if (rightTree != null) rightTree.parent = null;

        if (leftTree == null) {
            root = rightTree;
        } else {
            // 将左子树的最大节点伸展到根
            root = leftTree;
            Node<T> maxNode = leftTree;
            while (maxNode.right != null) {
                maxNode = maxNode.right;
            }
            splay(maxNode);
            // 将右子树接在最大节点右侧
            root.right = rightTree;
            if (rightTree != null) rightTree.parent = root;
            updateSize(root);
        }

        size--;
        return true;
    }

五、高级操作：分裂与合并

    /**
     * 分裂：以 key 为界将树分裂为两棵子树
     * @return [小于等于 key 的树, 大于 key 的树]
     */
    public SplayTree<T>[] split(T key) {
        @SuppressWarnings("unchecked")
        SplayTree<T>[] result = new SplayTree[2];

        if (root == null) {
            result[0] = new SplayTree<>();
            result[1] = new SplayTree<>();
            return result;
        }

        // 查找 key，将最接近的节点伸展到根
        search(key);

        result[0] = new SplayTree<>();
        result[1] = new SplayTree<>();

        int cmp = key.compareTo(root.key);
        if (cmp >= 0) {
            // root 及左子树属于左树，右子树属于右树
            result[0].root = root;
            result[0].size = getSize(root);
            result[1].root = root.right;
            if (result[1].root != null) {
                result[1].root.parent = null;
                result[1].size = getSize(result[1].root);
            }
            root.right = null;
        } else {
            // root 及右子树属于右树，左子树属于左树
            result[1].root = root;
            result[1].size = getSize(root);
            result[0].root = root.left;
            if (result[0].root != null) {
                result[0].root.parent = null;
                result[0].size = getSize(result[0].root);
            }
            root.left = null;
        }

        if (result[0].root != null) {
            result[0].root.parent = null;
            updateSize(result[0].root);
        }
        if (result[1].root != null) {
            result[1].root.parent = null;
            updateSize(result[1].root);
        }

        // 修正 size（精确计算）
        result[0].size = getSize(result[0].root);
        result[1].size = getSize(result[1].root);
        this.size = 0;
        this.root = null;

        return result;
    }

    /**
     * 合并：将两棵树合并（要求 left 树的所有键小于 right 树）
     */
    public static <T extends Comparable<T>> SplayTree<T> merge(
            SplayTree<T> left, SplayTree<T> right) {
        SplayTree<T> result = new SplayTree<>();
        if (left.root == null) {
            result.root = right.root;
            result.size = right.size;
        } else if (right.root == null) {
            result.root = left.root;
            result.size = left.size;
        } else {
            // 将 left 树的最大节点伸展到根
            Node<T> maxNode = left.root;
            while (maxNode.right != null) {
                maxNode = maxNode.right;
            }
            left.splay(maxNode);
            left.root.right = right.root;
            right.root.parent = left.root;
            result.root = left.root;
            result.size = left.size + right.size;
            updateSize(result.root);
        }
        left.root = null;
        right.root = null;
        return result;
    }

六、顺序统计：第 K 小元素

    /**
     * 查找第 k 小元素（1-based）
     */
    public T kthSmallest(int k) {
        if (k < 1 || k > size) {
            throw new IllegalArgumentException("k out of range");
        }
        Node<T> curr = root;
        while (curr != null) {
            int leftSize = getSize(curr.left);
            if (k == leftSize + 1) {
                splay(curr);
                return curr.key;
            } else if (k <= leftSize) {
                curr = curr.left;
            } else {
                k -= leftSize + 1;
                curr = curr.right;
            }
        }
        return null;
    }

    /**
     * 中序遍历输出
     */
    public List<T> inorder() {
        List<T> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }

    private void inorderHelper(Node<T> node, List<T> result) {
        if (node == null) return;
        inorderHelper(node.left, result);
        result.add(node.key);
        inorderHelper(node.right, result);
    }

七、摊还分析概述

Splay 树的均摊复杂度为 O(log n)，可通过势能法严格证明：

定义节点 x 的势能为：

Φ(x) = log₂(size(x))

整棵树的势能为所有节点势能之和。Splay 操作的摊还代价为：

amortized_cost = actual_cost + ΔΦ

可以证明，每次 Splay 操作的摊还代价不超过 3 × log₂(n) + 1。因此，m 次连续操作的序列总时间为 O(m log n)。

关键洞察：Zig-Zig 和 Zig-Zag 旋转虽然做了两次旋转，但能将目标节点的深度大幅减小，势能下降足够多，从而抵消实际旋转代价。

八、性能测试

    public static void main(String[] args) {
        SplayTree<Integer> tree = new SplayTree<>();
        Random rand = new Random(42);
        int n = 100000;

        // 插入测试
        long start = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            tree.insert(rand.nextInt(n * 10));
        }
        long insertTime = System.currentTimeMillis() - start;
        System.out.println("插入 " + n + " 个元素耗时: " + insertTime + "ms");
        System.out.println("树大小: " + tree.size());

        // 查找测试（重复查找热点元素）
        start = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            tree.search(rand.nextInt(n * 10));
        }
        long searchTime = System.currentTimeMillis() - start;
        System.out.println("查找 " + n + " 次耗时: " + searchTime + "ms");

        // 顺序统计测试
        System.out.println("第 100 小: " + tree.kthSmallest(100));
        System.out.println("第 1000 小: " + tree.kthSmallest(1000));

        // 删除测试
        start = System.currentTimeMillis();
        for (int i = 0; i < n / 2; i++) {
            tree.delete(rand.nextInt(n * 10));
        }
        long deleteTime = System.currentTimeMillis() - start;
        System.out.println("删除 " + (n / 2) + " 个元素耗时: " + deleteTime + "ms");
        System.out.println("剩余大小: " + tree.size());
    }
}

九、与其他平衡树对比

Splay 树以其简洁的实现和优秀的局部性表现，在需要频繁访问热点数据的场景（如缓存、内存管理器）中有着不可替代的价值。