本页使用了标题或全文手工转换

树堆

维基百科,自由的百科全书
(重定向自Treap
跳到导航 跳到搜索

樹堆(英語:Treap),是有一个随机附加域满足的性质的二叉搜索树,其結構相当于以随机數據插入的二叉搜索树。其基本操作的期望時間複雜度。相對於其他的平衡二叉搜索樹,Treap的特点是實現簡單,且能基本實現隨機平衡的結構。

介绍[编辑]

Treap一词由TreeHeap二词合成而来。其本身是一棵二叉搜索树,它的左子树和右子树也分别是一个Treap,和一般的二叉搜索树不同的是,Treap为每个节点记录优先级。Treap在以关键码构成二叉搜索树的同时,其节点优先级还满足的性质。Treap维护堆性质的方法用到了旋转,且只需要进行两种旋转操作,因此编程复杂度较Splay要小一些。

插入[编辑]

给节点随机分配一个优先级,先和二叉搜索树的插入一样,先把要插入的点插入到一个叶子上,然后跟维护堆一样,如果当前节点的优先级比根大就旋转,如果当前节点是根的左儿子就右旋如果当前节点是根的右儿子就左旋。

由于旋转是的,最多进行h次(h是树的高度),插入的复杂度是的,在期望情况下,所以它的期望复杂度是

删除[编辑]

因为Treap满足堆性质,所以只需要把要删除的节点旋转到叶节点上,然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子,向与其相反的方向旋转,直到那个节点被旋转到了叶节点,然后直接删除。

删除最多进行次旋转,期望复杂度是

查找[编辑]

和一般的二叉搜索树一样,但是由于Treap的随机化结构,Treap中查找的期望复杂度是

算法分析[编辑]

二叉搜索树有一个特性,就是每个子树的形态在优先级唯一确定的情况下都是唯一的,不受其他因素影响,也就是说,左子树的形态与树中大于根节点的值无关,右子树亦然。这是因为Treap满足堆的性质,Treap的根节点是优先级最大的那个节点,考虑它的左子树,树根也是子树里面最大的一点,右子树亦然。所以Treap相当于先把所有节点按照优先级排序,然后插入,实质上就相当于以随机顺序建立的二叉搜索树,只不过它并不需要一次读入所有数据,可以一个一个地插入。而当这个随机顺序确定的时候,这个树是唯一的。因此在给定优先级的情况下,只要是用符合要求的操作,通过任何方式得出的Treap都是一样的,所以不改变优先级的情况下,特殊的操作不会造成Treap结构的退化。而改变优先级可能会使Treap变得不够随机以致退化。

Treap的其它操作的期望复杂度同样是

参考程序[编辑]

与其他结构的比较[编辑]

外部链接[编辑]