4. 平衡二叉搜索树 --- BBST(Balance Bina
2018-06-12 本文已影响0人
執著我們的執著
BBST - 自平衡二叉搜索树
- 二叉搜索 ： 依旧满足二叉搜索树的性质（充要条件）
- 实现自平衡 ： 在插入和删除后，二叉搜索树性质＆平衡性破坏需要自行调整恢复
写在前面
1. BST 的平衡
若BST的拓扑结构如下图这种结构
BST的复杂度为 O(h)，上面拓扑结构 树高 h = 节点个数 n，删除操作的复杂度达到了O(n)，明显不符合 BST 的高效性，为了解决这种情况，我们为 BST 引入了
平衡的概念，来有效的控制树高，以追求更低的树
2. 理想平衡
- 节点数目固定，兄弟子树高度越接近（平衡），全树的树高也将倾向于更低，称之为理想平衡 ; 如完全二叉树，满二叉树...
3. 适度平衡
- 理想平衡出现的概率极低，维护的成本过高，故须适当的放低标准，引入
适度平衡 - 高度渐进地不超过
O(log n)，即可称之为适度平衡 ，即 height(Tree) = O(log n) -
适度平衡 的 BST ，称作 平衡二叉搜索树
BBST
那么采用什么样的办法将 BST 恢复成 BBST?
概括而言 ： 所有的这些方法都必须是等价变换
何为等价变换？
对于 BST ，拓扑结构不尽相同，但中序遍历序列如果相同，则称之为 等价 BST
等价 BST
通过上图等价BST，可总结等价BST规律
- 上下可变 ： 联结关系不尽相同
- 左右不乱 ： 中序序列不变
等价 BST 的相互转换，由一系列的基本操作串接而成，这种基本操作总结为两类，彼此对称
zig ： 顺时针旋转
zag ：逆时针旋转详见下图基于两类基本操作的等价变换
Zig(V)
Zag(V)
