C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

平衡树存储:

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

size就是节点的个数。

value是节点代表的权值。

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

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

son就是两个儿子。

平衡树size更新:

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

函数体:

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

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

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

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

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

平衡树插入:

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

由于Treap = Tree + Heap

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

函数体:

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

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

[ 1 ]节点不存在

什么??节点不存在??杀了出题人!

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

没有节点,那我们就开垦一个节点。(水土流失,土地荒漠化请走开)

├ 节点总数加1

├ 新节点size为1

├ 新节点num为1

├ 权值为data

└ 生成rand

→→→崭新的节点!!(不要998,不要98,只要9.8!)

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

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

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

那更简单了!!

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

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

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

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

有了明确的方向,就应该坚持走下去:

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

随机数判断,随机旋转:

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

更新size:

pushup(root);

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

完整平衡树插入代码:

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

平衡树旋转:

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

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

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

完整平衡树旋转代码:

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

C/C++学习笔记:算法知识之平衡树学习笔记,收藏一波吧

博客园:OIer|zythonc

想要在程序员生涯内有更高的成就的话,C/C++就是一个既可以强化思维能力,又可以打好编程基础的编程语言,你想要做软件开发,成为核心程序员的话,学习C/C++的话笔者有一个C/C++的编程俩千人羣(Q艘索:C/C++编程学习13)群,你如果感觉自学C/C++语言有困难的话,有兴趣学习或者了解一下C/C++编程的小伙伴就可以进来交流。

为您推荐

Leave a Reply

Your email address will not be published.