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

}