平衡树存储:
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
旋转后:A
完整平衡树旋转代码:
博客园:OIer|zythonc
学习C/C++编程,了解更多C/C++编程知识,欢迎关注笔者~
领取专属 10元无门槛券
私享最新 技术干货