教着做美食的网站,怎么增加网站权重,株洲企业网站制作,网站推广的目的数据结构-平衡树 前置知识
二叉树二叉树的中序遍历 问题
维护一个数据结构#xff0c;支持插入元素、删除元素、查询元素的排名、查询排名对应的元素、查询元素的前驱、查询元素的后继等。
BST#xff08;二叉搜索树#xff09;
作为一个基本无效#xff08;很容易卡掉…数据结构-平衡树 前置知识
二叉树二叉树的中序遍历 问题
维护一个数据结构支持插入元素、删除元素、查询元素的排名、查询排名对应的元素、查询元素的前驱、查询元素的后继等。
BST二叉搜索树
作为一个基本无效很容易卡掉的数据结构将其放在这里讲可能更为合适。。。 BST 的思想来自于二叉树的 DFS 序。 设想一下若一个二叉树的中序遍历正好递增也就是说始终有 左儿子 ≤ 根 ≤ 右儿子 左儿子\le根\le右儿子 左儿子≤根≤右儿子那么不就可以达到 O ( 树高 ) O(\text{树高}) O(树高) 的复杂度了吗 可能不是这样。设想一组数据令插入的第 i i i 个节点为 i i iBST 便会退化为 O ( n 2 ) O(n^2) O(n2)长这样
思路
为了弥补 BST 的各种劣势聪明的 OIers 发明了平衡树。 对于上面卡掉 BST 的样例平衡树的一种画法长这样 可以看出来平衡树是非常平衡的。 平衡树的重要处理就是维护其平衡性。 接下来介绍一下用来维护平衡树的平衡性质的两种操作——左旋 Zag \text{Zag} Zag和右旋 Zig \text{Zig} Zig Zag \text{Zag} Zag 如果有一个失衡子树长这样 需要将节点 q \text q q 旋转至节点 p \text p p我们可以这样 注意到其中序遍历是不变的。 Zig \text{Zig} Zig 如果有一个失衡子树长这样 需要将节点 q \text q q 旋转至节点 p \text p p我们可以这样 注意到其中序遍历是不变的。
由于不同的平衡树对失衡子树的处理方式是不同的所以这里不再赘述可以去下方的文章学习。 数据结构参数
单次修改时间复杂度 Θ ( log n ) \Theta(\log n) Θ(logn)单次查询时间复杂度 Θ ( log n ) \Theta(\log n) Θ(logn)空间复杂度 Θ ( n ) \Theta(n) Θ(n) 接下来是三种基本的平衡树
AVLTreapSplay
