Treap

树堆，在数据结构中也称Treap，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。

Treap模板
Treap造价信息
Treap介绍

Treap图片

Treap基本信息

名称	treap	性质	自平衡二叉查找树
用途	实现关联数组

Treap模板

模板

支持以下操作

1. 插入x数

2. 删除x数(若有多个相同的数，因只删除一个)

3. 查询x数的排名(若有多个相同的数，因输出最小的排名)

4. 查询排名为x的数

5. 求x的前驱(前驱定义为小于x，且最大的数)

6. 求x的后继(后继定义为大于x，且最小的数)

查看详情

Treap造价信息

市场价

信息价

询价

材料名称	规格/型号	市场价（除税）	工程建议价（除税）	行情	品牌	单位	税率	供应商	报价日期
暂无数据

材料名称	规格/型号	除税信息价	含税信息价	行情	品牌	单位	税率	地区/时间
暂无数据

材料名称	规格/需求量	报价数	最新报价（元）	供应商	报价地区	最新报价时间
暂无数据

我们可以看到，如果一个二叉排序树节点插入的顺序是随机的，这样我们得到的二叉排序树大多数情况下是平衡的，即使存在一些极端情况，但是这种情况发生的概率很小，所以我们可以这样建立一颗二叉排序树，而不必要像AVL那样旋转，可以证明随机顺序建立的二叉排序树在期望高度是O(logn)，但是某些时候我们并不能得知所有的带插入节点，打乱以后再插入。所以我们需要一种规则来实现这种想法，并且不必要所有节点。也就是说节点是顺序输入的，我们实现这一点可以用Treap。

Treap=Tree+Heap

Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。

查看详情

Treap常见问题

Treap相关推荐

相关百科
相关知识
相关专栏

百科

Treap

Treap基本信息

Treap模板

Treap造价信息

Treap介绍

Treap常见问题

最新词条