树堆

在树堆中,它可以在O(log⁡ n)时间内完成查找、插入和删除。

import java.util.Random;
 
// 一个 Treap 节点
class TreapNode
{
    int data;
    int priority;
    TreapNode left, right;
 
    // 构造函数
    TreapNode(int data)
    {
        this.data = data;
        this.priority = new Random().nextInt(100);
        this.left = this.right = null;
    }
}
 
class Treap
{
    /* 左旋转给定treap的函数
 
          r                         R
         / \      左旋转      / \
        L   R        ———>         r   Y
           / \                   / \
          X   Y                 L   X
    */
    public static TreapNode rotateLeft(TreapNode root)
    {
        TreapNode R = root.right;
        TreapNode X = root.right.left;
 
        // 旋转
        R.left = root;
        root.right = X;
 
        // 设置一个新的根
        return R;
    }
 
    /* 向右旋转给定的treap的函数
 
            r                        L
           / \     向右旋转     / \
          L   R        ———>        X   r
         / \                          / \
        X   Y                        Y   R
    */
    public static TreapNode rotateRight(TreapNode root)
    {
        TreapNode L = root.left;
        TreapNode Y = root.left.right;
 
        // 旋转
        L.right = root;
        root.left = Y;
 
        // 设置一个新的根
        return L;
    }
 
    // 将具有优先级的给定键插入到treap中的递归的函数
    public static TreapNode insertNode(TreapNode root, int data)
    {
        // 基本情况
        if (root == null) {
            return new TreapNode(data);
        }
 
        // 如果数据小于根节点，则插入左子树；
        // 否则，插入右子树
        if (data < root.data)
        {
            root.left = insertNode(root.left, data);
 
            // 如果堆属性被破坏，则向右旋转
            if (root.left != null && root.left.priority > root.priority) {
                root = rotateRight(root);
            }
        }
        else {
            root.right = insertNode(root.right, data);
 
            // 如果违反了堆属性，则向左旋转
            if (root.right != null && root.right.priority > root.priority) {
                root = rotateLeft(root);
            }
        }
 
        return root;
    }
 
    // 递归的函数在给定的treap中搜索一个键
    public static boolean searchNode(TreapNode root, int key)
    {
        // 如果键不存在于树中
        if (root == null) {
            return false;
        }
 
        // 如果找到密钥
        if (root.data == key) {
            return true;
        }
 
        // 如果key小于根节点，则在左子树中搜索
        if (key < root.data) {
            return searchNode(root.left, key);
        }
 
        // 否则，在右子树中搜索
        return searchNode(root.right, key);
    }
 
    // 从给定的treap中删除一个键的递归的函数
    public static TreapNode deleteNode(TreapNode root, int key)
    {
        // 基本情况：在树中找不到键
        if (root == null) {
            return null;
        }
 
        // 如果key小于根节点，则递归左子树
        if (key < root.data) {
            root.left = deleteNode(root.left, key);
        }
 
        // 如果key大于根节点，则递归到右子树
        else if (key > root.data) {
            root.right = deleteNode(root.right, key);
        }
 
        // 如果找到密钥
        else {
            // 案例一：要删除的节点没有子节点(是叶子节点)
            if (root.left == null && root.right == null)
            {
                // 释放内存并将root更新为null
                root = null;
            }
 
            // 情况2：要删除的节点有两个孩子
            else if (root.left != null && root.right != null)
            {
                // 如果左孩子的优先级低于右孩子
                if (root.left.priority < root.right.priority)
                {
                    // 在根上调用 `rotateLeft()`
                    root = rotateLeft(root);
 
                    //递 归删除左孩子
                    root.left = deleteNode(root.left, key);
                }
                else {
                    // 在根上调用 `rotateRight()`
                    root = rotateRight(root);
 
                    // 递 归删除右孩子
                    root.right = deleteNode(root.right, key);
                }
            }
 
            // 案例3：要删除的节点只有一个孩子
            else {
                // 选择一个子节点
                TreapNode child = (root.left != null)? root.left: root.right;
                root = child;
            }
        }
 
        return root;
    }
 
    // 实用函数来打印一个treap的二维视图
    // 反向中序遍历
    public static void printTreap(TreapNode root, int space)
    {
        final int height = 10;
 
        // 基本情况
        if (root == null) {
            return;
        }
 
        // 增加关卡之间的距离
        space += height;
 
        // 先打印右孩子
        printTreap(root.right, space);
        System.lineSeparator();
 
        // 用空格填充后打印当前节点
        for (int i = height; i < space; i++) {
            System.out.print(' ');
        }
 
        System.out.println(root.data + "(" + root.priority + ")");
 
        //打印左孩子
        System.lineSeparator();
        printTreap(root.left, space);
    }
 
    public static void main(String[] args)
    {
        // Treap 键
        int[] keys = { 5, 2, 1, 4, 9, 8, 10 };
 
        // 构造一个Treap
        TreapNode root = null;
        for (int key: keys) {
            root = insertNode(root, key);
        }
 
        System.out.println("Constructed treap:\n");
        printTreap(root, 0);
 
        System.out.println("\nDeleting node 1:\n");
        root = deleteNode(root, 1);
        printTreap(root, 0);
 
        System.out.println("\nDeleting node 5:\n");
        root = deleteNode(root, 5);
        printTreap(root, 0);
 
        System.out.println("\nDeleting node 9:\n");
        root = deleteNode(root, 9);
        printTreap(root, 0);
    }
}