简单_随机平衡二叉树(Treap)
我们可以看到，如果一个二叉排序树节点插入的顺序是随机的，这样我们得到的二叉排序树大多数情况下是平衡的，即使存在一些极端情况，但是这种情况发生的概率很小，所以我们可以这样建立一颗二叉排序树，而不必要像AVL那样旋转，可以证明随机顺序建立的二叉排序树在期望高度是，但是某些时候我们并不能得知所有的带插入节点，打乱以后再插入。所以我们需要一种规则来实现这种想法，并且不必要所有节点。也就是说节点是顺序输入的，我们实现这一点可以用Treap。
Treap=Tree+Heap
Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。
貌似TreapDB用的就是Treap算法实现的，当然肯定还有其他的数据结构进行了混搭。
package sunfa.tree;import java.util.Comparator;import java.util.Random;/** * 随机平衡二叉树Treap=Tree+heap,Tree取前3个单词，heap取后2个单词 * * 其实这棵树还是比较好理解的，与普通的BST相比节点多了个随机数，普通BST的旋转是以插入的key的大小为评判标准的，<br> * 而Treap是以节点的随机数的大小作为评判标准的。为什么要给节点弄个随机数呢？因为普通的BST之所以会退化为线性表<br> * 主要原因是顺序插入造成的。 * * @param <K> * @param <V> */public class Treap<K, V> {public static void main(String[] args) {Treap<Integer, Integer> tree = new Treap<Integer, Integer>(new Comparator<Integer>() {public int compare(Integer o1, Integer o2) {return o1 - o2;}});//测试200W条数据插入Treap树 时间是1600毫秒左右，树的深度：50long start = System.currentTimeMillis();for (int i = 0; i < tree.n; i++) {tree.put(i, i);}System.out.println(System.currentTimeMillis()-start);System.out.println("h:" + tree.h());//tree.printTree(tree.root);}Comparator<K> comp;public Treap(Comparator<K> c) {this.comp = c;}private Entry<K, V> root;private Random ran = new Random();private int n = 2000000;private void printTree(Entry<K, V> node) {if (node == null)return;System.out.print("[" + node.key + "=" + node.fix + "],");printTree(node.left);printTree(node.right);}public void put(K key, V value) {put0(null, root, key, value, 2);}/** * 插入的方式和SBT类似 * @param p 根节点 * @param node 插入节点 * @param key * @param value * @param i */private void put0(Entry<K, V> p, Entry<K, V> node, K key, V value, int i) {if (key == null)throw new NullPointerException();if (node == null) {node = new Entry<K, V>(p, null, null, key, value, ran.nextInt(n));if (null == this.root)this.root = node;if (i == 0)p.left = node;else if (i == 1)p.right = node;return;}int c = compare(key, node.key);if (c < 0) {put0(node, node.left, key, value, 0);if (node.left.fix < node.fix)// 之所以递归put0里面进行旋转也是为了压缩路径,改成非递归的形式就起不到路径压缩了，和SBT树的插入算法类似rightRotate(node);} else {put0(node, node.right, key, value, 1);if (node.right.fix < node.fix)leftRotate(node);}}/** * Treap的查找和普通的BST的查找一样,并且不会改变Treap的结构 * @param key * @return */public V get(K key) {Entry<K, V> entry = getEntry(key);return entry==null?null:entry.value;}private Entry<K, V> getEntry(K key){if (key == null)return null;Entry<K, V> t = root;while (true) {int c = compare(key, t.key);if (c == 0) {return t;} else if (c < 0) {if (t.left != null)t = t.left;elsereturn null;} else {if (t.right != null)t = t.right;elsereturn null;}}}private int compare(K k1, K k2) {return this.comp != null ? (((comp).compare(k1, k2))): (((Comparable<K>) k1).compareTo(k2));}//public V remove(K key){//Entry<K, V> entry = getEntry(key);//if(entry==null)//return null;////}private void delete0(Entry<K, V> p,K key){int c = compare(key, p.key);if(c==0){if(p.left==null || p.right==null){Entry<K, V> t = p;if(p.right==null){p = p.left;}else{p = p.right;}}}}private void leftRotate(Entry<K, V> x) {// ①Entry<K, V> y = x.right;// 分离出旋转元素的右子节点// ②x.right = y.left;// 旋转元素的右子节点的左子节点挂接到旋转元素的右子节点处if (y.left != null) {y.left.parent = x;//}// ③y.parent = x.parent;// 分离出来的部分挂接到旋转元素的父节点下if (x.parent == null) {// 如果旋转元素为根节点,就让旋转元素成为根this.root = y;} else if (x == x.parent.left) {// 如果旋转元素是它父节点的左子节点,让旋转元素父节点的左指针指向分离出的节点x.parent.left = y;} else {// 如果是右子节点，就用父节点的右指针指向分离节点x.parent.right = y;}// ④y.left = x;// 分离出来的部分的左子节点指向旋转元素x.parent = y;// 旋转元素的父节点指向分离出的元素}private void rightRotate(Entry<K, V> x) {// ①Entry<K, V> y = x.left;// 分离出旋转元素的右子节点// ②x.left = y.right;// 旋转元素的右子节点的左子节点挂接到旋转元素的右子节点处if (y.right != null)y.right.parent = x;//// ③y.parent = x.parent;// 分离出来的部分挂接到旋转元素的父节点下if (x.parent == null) {// 如果旋转元素为根节点,就让旋转元素成为根this.root = y;} else if (x == x.parent.left) {// 如果旋转元素是它父节点的左子节点,让旋转元素父节点的左指针指向分离出的节点x.parent.left = y;} else {// 如果是右子节点，就用父节点的右指针指向分离节点x.parent.right = y;}// ④y.right = x;// 分离出来的部分的左子节点指向旋转元素x.parent = y;// 旋转元素的父节点指向分离出的元素}public int h() {return h0(this.root);}private int h0(Entry<K, V> p) {if (p == null)return -1;return 1 + Math.max(h0(p.left), h0(p.right));}static class Entry<K, V> {Entry<K, V> parent, left, right;K key;V value;int fix;//随机数public Entry(Entry<K, V> parent, Entry<K, V> left, Entry<K, V> right,K key, V value, int fix) {super();this.parent = parent;this.left = left;this.right = right;this.key = key;this.value = value;this.fix = fix;}}}