简单_随机平衡二叉树(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毫秒左右，树的深度：50
		long 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;
				else
					return null;
			} else {
				if (t.right != null)
					t = t.right;
				else
					return 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;
		}
	}
}