每日算法 — 使用java实现Treap：随机优先级与二叉搜索树平衡策略

算法背景

Treap（Tree + Heap，树堆）是一种结合了二叉搜索树（BST）和堆两种数据结构特性的平衡树。每个节点除了存储键值外，还附加一个随机优先级。Treap以键值满足二叉搜索树性质（左小右大），以优先级满足堆性质（父节点优先级高于子节点）。由于优先级是随机生成的，Treap的期望高度为 $O(\log n)$，实现简单且无需复杂的旋转平衡操作。

核心思想

Treap的平衡不依赖显式旋转维护高度，而是依赖随机优先级天然形成的堆结构。插入时先按BST规则找到位置，然后通过旋转（左旋/右旋）将节点上浮至满足堆性质的位置。删除则通过旋转将目标节点下移至叶子后移除。

Java实现

import java.util.Random;

/**
 * Treap（树堆）实现
 * 结合二叉搜索树与堆的性质，通过随机优先级实现期望O(log n)的平衡
 */
public class Treap {

    private static final Random RANDOM = new Random();

    /**
     * 节点类
     */
    static class Node {
        int key;          // 键值（BST排序依据）
        int priority;     // 随机优先级（堆排序依据）
        int size;         // 以该节点为根的子树大小
        int count;        // 相同键值的计数
        Node left, right; // 左右子节点

        Node(int key) {
            this.key = key;
            this.priority = RANDOM.nextInt();
            this.size = 1;
            this.count = 1;
        }
    }

    private Node root;

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

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

    /**
     * 右旋：将左子节点提升为当前子树的根
     *     y           x
     *    / \   ->    / \
     *   x   c       a   y
     *  / \             / \
     * a   b           b   c
     */
    private Node rotateRight(Node y) {
        Node x = y.left;
        Node b = x.right;
        x.right = y;
        y.left = b;
        updateSize(y);
        updateSize(x);
        return x;
    }

    /**
     * 左旋：将右子节点提升为当前子树的根
     *   x             y
     *  / \    ->     / \
     * a   y         x   c
     *    / \       / \
     *   b   c     a   b
     */
    private Node rotateLeft(Node x) {
        Node y = x.right;
        Node b = y.left;
        y.left = x;
        x.right = b;
        updateSize(x);
        updateSize(y);
        return y;
    }

    /**
     * 插入键值
     * 先按BST找到位置，再通过旋转维护堆性质
     */
    public void insert(int key) {
        root = insert(root, key);
    }

    private Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key);
        }

        if (key == node.key) {
            node.count++;
        } else if (key < node.key) {
            node.left = insert(node.left, key);
            // 左子节点优先级更高，需要右旋上浮
            if (node.left.priority > node.priority) {
                node = rotateRight(node);
            }
        } else {
            node.right = insert(node.right, key);
            // 右子节点优先级更高，需要左旋上浮
            if (node.right.priority > node.priority) {
                node = rotateLeft(node);
            }
        }

        updateSize(node);
        return node;
    }

    /**
     * 删除键值
     * 通过旋转将目标节点下移至叶子后删除
     */
    public void delete(int key) {
        root = delete(root, key);
    }

    private Node delete(Node node, int key) {
        if (node == null) {
            return null;
        }

        if (key < node.key) {
            node.left = delete(node.left, key);
        } else if (key > node.key) {
            node.right = delete(node.right, key);
        } else {
            // 找到目标节点
            if (node.count > 1) {
                node.count--;
            } else {
                // 通过旋转将当前节点下沉至叶子
                if (node.left == null) {
                    return node.right;
                } else if (node.right == null) {
                    return node.left;
                } else if (node.left.priority > node.right.priority) {
                    node = rotateRight(node);
                    node.right = delete(node.right, key);
                } else {
                    node = rotateLeft(node);
                    node.left = delete(node.left, key);
                }
            }
        }

        updateSize(node);
        return node;
    }

    /**
     * 查找键值是否存在
     */
    public boolean contains(int key) {
        Node cur = root;
        while (cur != null) {
            if (key == cur.key) return true;
            cur = key < cur.key ? cur.left : cur.right;
        }
        return false;
    }

    /**
     * 查找第k小的元素（1-based）
     */
    public int kth(int k) {
        if (k < 1 || k > getSize(root)) {
            throw new IllegalArgumentException("k out of range");
        }
        return kth(root, k);
    }

    private int kth(Node node, int k) {
        int leftSize = getSize(node.left);
        if (k <= leftSize) {
            return kth(node.left, k);
        } else if (k <= leftSize + node.count) {
            return node.key;
        } else {
            return kth(node.right, k - leftSize - node.count);
        }
    }

    /**
     * 查找键值的排名（比key小的元素个数+1）
     */
    public int rank(int key) {
        return rank(root, key);
    }

    private int rank(Node node, int key) {
        if (node == null) {
            return 1;
        }
        if (key <= node.key) {
            return rank(node.left, key);
        } else {
            return getSize(node.left) + node.count + rank(node.right, key);
        }
    }

    /**
     * 查找前驱（小于key的最大值）
     */
    public Integer predecessor(int key) {
        Node cur = root;
        Integer result = null;
        while (cur != null) {
            if (cur.key < key) {
                result = cur.key;
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return result;
    }

    /**
     * 查找后继（大于key的最小值）
     */
    public Integer successor(int key) {
        Node cur = root;
        Integer result = null;
        while (cur != null) {
            if (cur.key > key) {
                result = cur.key;
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return result;
    }

    /**
     * 中序遍历（升序输出）
     */
    public void inorder() {
        inorder(root);
        System.out.println();
    }

    private void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        for (int i = 0; i < node.count; i++) {
            System.out.print(node.key + " ");
        }
        inorder(node.right);
    }

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

    public static void main(String[] args) {
        Treap treap = new Treap();
        int[] values = {50, 30, 70, 20, 40, 60, 80, 25, 35};

        System.out.println("=== 插入元素 ===");
        for (int v : values) {
            treap.insert(v);
            System.out.println("插入 " + v + " 后，树大小: " + treap.size());
        }

        System.out.println("\n=== 中序遍历（升序） ===");
        treap.inorder();

        System.out.println("\n=== 查询操作 ===");
        System.out.println("包含 40? " + treap.contains(40));
        System.out.println("包含 100? " + treap.contains(100));
        System.out.println("第3小: " + treap.kth(3));
        System.out.println("40的排名: " + treap.rank(40));
        System.out.println("30的前驱: " + treap.predecessor(30));
        System.out.println("30的后继: " + treap.successor(30));

        System.out.println("\n=== 删除操作 ===");
        treap.delete(30);
        System.out.println("删除30后中序遍历:");
        treap.inorder();
        System.out.println("树大小: " + treap.size());
    }
}

复杂度分析

空间复杂度为 $O(n)$，每个节点存储键值、优先级、计数和子树大小。

算法优势与适用场景

优势：
– 实现简洁，仅需左旋/右旋两种操作
– 无需存储额外平衡因子或颜色信息
– 支持区间查询、第k小等扩展操作

适用场景：
– 需要动态维护有序集合的问题
– 在线算法中需要快速插入删除的场景
– 作为其他高级数据结构（如线段树套Treap）的基础组件