BBST - 自平衡二叉搜索樹
- 二叉搜索 ： 依舊滿足二叉搜索樹的性質(zhì)（充要條件）
- 實(shí)現(xiàn)自平衡 ： 在插入和刪除后帜平，二叉搜索樹性質(zhì)＆平衡性破壞需要自行調(diào)整恢復(fù)
寫在前面
1. BST 的平衡
若BST的拓?fù)浣Y(jié)構(gòu)如下圖這種結(jié)構(gòu)
BST的復(fù)雜度為 O(h)锭硼，上面拓?fù)浣Y(jié)構(gòu) 樹高 h = 節(jié)點(diǎn)個(gè)數(shù) n蟆融，刪除操作的復(fù)雜度達(dá)到了O(n)，明顯不符合 BST 的高效性绞愚，為了解決這種情況馋没，我們?yōu)?BST 引入了
平衡的概念辟犀，來有效的控制樹高，以追求更低的樹
2. 理想平衡
- 節(jié)點(diǎn)數(shù)目固定出皇，兄弟子樹高度越接近（平衡）羞芍，全樹的樹高也將傾向于更低，稱之為理想平衡 ; 如完全二叉樹恶迈，滿二叉樹...
3. 適度平衡
- 理想平衡出現(xiàn)的概率極低涩金，維護(hù)的成本過高谱醇，故須適當(dāng)?shù)姆诺蜆?biāo)準(zhǔn)暇仲，引入
適度平衡 - 高度漸進(jìn)地不超過
O(log n)，即可稱之為適度平衡 副渴，即 height(Tree) = O(log n) -
適度平衡 的 BST 奈附，稱作 平衡二叉搜索樹
BBST
那么采用什么樣的辦法將 BST 恢復(fù)成 BBST?
概括而言 ： 所有的這些方法都必須是等價(jià)變換
何為等價(jià)變換？
對于 BST 煮剧，拓?fù)浣Y(jié)構(gòu)不盡相同斥滤，但中序遍歷序列如果相同，則稱之為 等價(jià) BST
等價(jià) BST
通過上圖等價(jià)BST勉盅，可總結(jié)等價(jià)BST規(guī)律
- 上下可變 ： 聯(lián)結(jié)關(guān)系不盡相同
- 左右不亂 ： 中序序列不變
等價(jià) BST 的相互轉(zhuǎn)換佑颇，由一系列的基本操作串接而成，這種基本操作總結(jié)為兩類草娜，彼此對稱
zig ： 順時(shí)針旋轉(zhuǎn)
zag ：逆時(shí)針旋轉(zhuǎn)詳見下圖基于兩類基本操作的等價(jià)變換
Zig(V)
Zag(V)
