java实现Treap

Treap树（笛卡尔树）= Heap (堆)+BST (二叉搜索树 binary search trea)。这是一颗既满足堆的性质与BST的性质的树。

当我们只知道一颗二叉查找树（BST）的 valval 的时候，我们可以将任意一个点作为根节点，任意一个比此点 valval 小的点作为左儿子，任意一个比此点 valval 大的点作为右儿子，按照此种方法建树后，如果我们进行中序遍历，会发现遍历出的序列是有序且一定的。

那么小顶堆（Heap）的性质是修正值最小的点一定在最上方，也就是根，左儿子和右儿子的 rndrnd 是左子树和右子树分别的最小值，由于有BST的性质限制，又有了Heap的性质限制后我们就发现这棵树的结构也是一定的。

public class Treap{
    class Node{
        Node right;
        Node left;
        Object data;
        Node parent;
        int priority;
        public Node(Object d,int pro,Node p){
            data=d;priority=pro;parent=p;
        }
        public void printTree(Node root){
            if(root!=null){
                printTree(root.left);
                System.out.println(root.data);
                printTree(root.right);
            }
        }

        /**
         *查找
         */
        public Node query(Node root,int value){
            Node node=root;
            while(node!=null){
                if((int)node.data>value){
                    node=node.left;
                }else if((int)node.data<value){
                    node=node.right;
                }else{
                    return node;
                }
            }
            return null;
        }
        public Node insert(Object value,Node root,Node p){
            if(root==null)
                return new Node(value,(int)(Math.random()*100),p);
            if(root.data.hashCode()>value.hashCode()){
                root.left=insert(value,root.left,root);
                //插入完成后，根据优先级进行旋转操作
                //左子节点的优先级值小于根节点的优先级
                //根据小顶堆的规则，需要进行右旋操作
                if(root.left.priority< root.priority){
                   root=rightRotate(root);
                }
            }else if(root.data.hashCode()<value.hashCode()){
                root.right=insert(value,root.right,root);
                if(root.right.priority<root.priority){
                    root=leftRotated(root);
                }
            }else{

            }
            return root;
        }
/**
 * 进行删除操作
 * 如果是叶子节点 则直接删除，不是叶子节点，就进行旋转，直至该节点是叶子节点，然后删除
 */
    public Node delete(Object value,Node root){
        if(root!=null){
            if(root.data.hashCode()>value.hashCode()){
                root.left=delete(value,root.left);
            }
        }else if(root.data.hashCode()<value.hashCode()){
            root.right=delete(value,root.right);
        }else{
            //root 已经成为该目标节点
            if(root.left==null && root.right==null){
                return null;
            }
            else if(root.left!=null &&root.right!=null){
                if(root.left.priority<root.right.priority){
                    root=rightRotate(root);
                    root.right=delete(value,root.right);
                }else{
                    root=leftRotated(root);
                    root.left=delete(value,root.left);
                }
            }else if(root.right==null){
                  root=rightRotate(root);
                root.right=delete(value,root.right);
            }else if(root.left==null){
                root=leftRotated(root);
                root.left=delete(value,root.left);
            }

        }
        return root;
    }
    //左子节点右旋
    public Node rightRotate(Node treeNode) {
        // temp为左子结点
        Node temp = treeNode.left;
        //将父结点的左边指向 temp的右子结点
        treeNode.left = temp.right;
        // 将temp结点的右边指向父结点
        temp.right = treeNode;
        // 进行上面两步操作，在纸上画一下就找到其右旋成功了，
        // 即左子结点变为根结点了

        // 返回此时旋转后的真正根结点
        return temp;
    }
    //右子节点左旋
    public Node leftRotated(Node node){
        
       Node tem=node.right;
        
        node.right=tem.left;
       
        tem.left=node;
        return tem;
    }
    }
    Node root;
    public void insert(Object value){
        if(root==null)
            root=new Node(value,(int)(Math.random()*100),null);
        else root.insert(value,root,null);
    }
    public void print(){
        root.printTree(root);
    }
    public void rotated(){
        root.leftRotated(root);
    }
}