動態平衡二叉搜索樹的簡易實現，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(); 
    } 
 
}