动态平衡二叉搜索树的简易实现，Treap 树

Treap 树是一种易于实现的近似平衡的二叉搜索树。Treap 每个结点包括值和优先级两个属性，值满足二叉搜索树性质（左<中<右），优先级满足大顶堆的性质（左<中 && 右<中）。Treap 树的插入和删除的实现比较简单，插入结点时为待插结点随机生产一个优先级值，按照BST的插入算法并通过左旋或右旋调整保持优先级大顶堆的性质；Treap树的查询复杂度期望值为 O(logN) ；

public class TreapTree { 
     
    public static class Node { 
         
        public int v; 
        public int p; 
        Node lc; 
        Node rc; 
         
        public Node(int x) { 
            v = x; 
            p = (int)(Math.random() * Integer.MAX_VALUE); 
            lc = null; 
            rc = null; 
        } 
         
    } 
     
    // Treap树的根结点 
    private Node root = null; 
     
    // 检查优先级公共方法 
    public boolean check() { 
        return check(root); 
    } 
     
    // 检查是否满足Treap树优先级约束 
    private boolean check(Node node) { 
        if ( node == null ) 
            return true; 
        else { 
            if ( node.lc != null && node.p < node.lc.p ) 
                return false; 
            if ( node.rc != null && node.p < node.rc.p ) 
                return false; 
            return ( check(node.lc) && check(node.rc) ); 
                 
        } 
    } 
     
    // 删除公共方法 
    public void delete(int x) { 
        root = searchAndDelete(root, x); 
    } 
     
    // 删除一个结点并通过旋转保持Treap树的性质 
    private Node delete(Node node) { 
         
        if ( node.lc == null ) { 
            return node.rc; 
        } else if ( node.rc == null ) { 
            return node.lc; 
        } else { 
            if ( node.lc.p > node.rc.p ) { 
                node = rotateRight(node); 
                node.rc = delete(node.rc); 
            } else { 
                node = rotateLeft(node); 
                node.lc = delete(node.lc); 
            } 
            return node; 
        } 
         
    } 
     
    // 深度：公共方法 
    public int depth() { 
        return depth(root); 
    } 
     
    // 计算树的深度 
    private int depth(Node node) { 
        if ( node == null ) 
            return 0; 
        else { 
            int x = depth(node.lc); 
            int y = depth(node.rc); 
            return ((x>y)?x:y) + 1; 
        } 
    } 
     
    // 插入：公共方法 
    public void insert(int x) { 
        root = insert(root, x); 
    } 
     
    // 插入：将新结点插入node为根的子树，子树的根可能发生变化 
    private Node insert(Node node, int x) { 
         
        Node cur = new Node(x); 
        if ( node == null ) { 
            return cur; 
        } else { 
            if ( node.v > x ) { 
                node.lc = insert(node.lc, x); 
                // 如果左孩子优先级大，执行右旋 
                if ( node.lc.p > node.p ) return rotateRight(node); 
            } else if ( node.v < x ) { 
                node.rc = insert(node.rc, x); 
                // 如果右孩子优先级大，执行左旋 
                if ( node.rc.p > node.p ) return rotateLeft(node); 
            } 
            return node; 
        } 
         
    } 
     
    // 打印公共方法 
    public void print() { 
        print(root); 
    } 
 
    // 中序遍历打印Treap树 
    private void print(Node node) { 
        if ( node != null ) { 
            print(node.lc); 
            System.out.printf("%d ", node.v); 
            print(node.rc); 
        } 
    } 
     
    // 左旋：当前节点成为右孩子的左子树，右孩子成为根 
    private Node rotateLeft(Node node) { 
        Node right = node.rc; node.rc = right.lc; right.lc = node; 
        return right; 
    } 
     
    // 右旋：当前结点成为其左孩子的右子树，左孩子成为根 
    private Node rotateRight(Node node) { 
        Node left = node.lc; node.lc = left.rc; left.rc = node; 
        return left; 
    } 
     
    // 搜索值等于v的结点并删除它 
    private Node searchAndDelete(Node node, int x) { 
        if ( node == null ) 
            return null; 
        else if ( node.v >  x ) { 
            node.lc = searchAndDelete(node.lc, x); 
        } else if ( node.v < x ) { 
            node.rc = searchAndDelete(node.rc, x); 
        } else { 
            node = delete(node); 
        } 
        return node; 
    } 
 
    // 测试 
    public static void main(String[] args) { 
         
        TreapTree tree = new TreapTree(); 
         
        for ( int i=0; i<1024; i++ ) { 
            tree.insert(i); 
        } 
         
        for ( int i=128; i<256; i++ ) { 
            tree.delete(i); 
        } 
         
        System.out.printf("depth : %d, check : %b%n", tree.depth(), tree.check()); 
        tree.print(); 
    } 
 
}