随机二叉树(Treap) Java实现
摘要: Treap=Tree+Heap。Treap本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap记录一个额外的数据，就是优先级。Treap在以关键码构成二叉搜索树的同时，还按优先级来满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。
阅读全文
posted @
2012-05-16 14:37 x.matthew 阅读(4252) |
评论 (0) 编辑