本文共 771 字，大约阅读时间需要 2 分钟。

平衡树存储：

size就是节点的个数。

value是节点代表的权值。

权值相同的两个节点被视为一个，num记录折叠数量。

rand是随机数，用来维护平衡树。

son就是两个儿子。

 

平衡树size更新：

实际操作中，各个变量的值都是不断更新的，size也不例外。

函数体：

一个节点包括的节点个数用脚也能想到：左儿子size与右儿子size的和，加上这个节点折叠数量。

完整的平衡树size更新代码：

 

平衡树插入：

学习完上面的内容，接下来的基本逼死人的操作插入与删除就很简单了：

由于Treap = Tree + Heap

所以平衡树插入与二叉排序树插入差不多

函数体：

插入节点总会遇到各种增加码量的情况，需要我们一一判断：

[ 1 ]节点不存在

什么？？节点不存在？？杀了出题人！

当插入函数用在建树中，这种情况很常见。

没有节点，那我们就开垦一个节点。（水土流失，土地荒漠化请走开）

├ 节点总数加1

├ 新节点size为1

├ 新节点num为1

├ 权值为data

└ 生成rand

→→→崭新的节点！！（不要998，不要98，只要9.8！）

代码实现就是一个简单的模拟：

 

 

 [ 2 ]有一个权值为data的节点

那更简单了！！

[ 3 ]寻找子树满足情况一或情况二

去哪棵子树呢？？定义一个变量。

有了明确的方向，就应该坚持走下去：

随机数判断，随机旋转：

更新size：

pushup(root);

至此，插入操作基本完成。

完整平衡树插入代码：

 

平衡树旋转：

平衡树旋转不破坏平衡树的性质，也就是说

旋转前：A<B<C<D<E<F

旋转后：A<B<C<D<E<F

完整平衡树旋转代码：

 

 

 

 

 

博客园：OIer|zythonc

学习C/C++编程知识，提升C/C++编程能力，欢迎关注博主微信公众号：C语言编程学习基地，一起来学习编程吧！

转载地址：http://xjnqb.baihongyu.com/