4. 平衡二叉搜索树 --- BBST(Balance Bina

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规律

1. 上下可变 ： 联结关系不尽相同
2. 左右不乱 ： 中序序列不变

---

等价 BST 的相互转换，由一系列的基本操作串接而成，这种基本操作总结为两类，彼此对称

zig ： 顺时针旋转
zag ：逆时针旋转

详见下图基于两类基本操作的等价变换

Zig(V) Zag(V)

---

---

BBST :满足平衡性质的 BST；

基于上述两种基本操作 zig 和 zag，可将 BST 转换成想要的 BBST