背景
我們認(rèn)為線性數(shù)據(jù)結(jié)構(gòu)包括：Vector（理解為數(shù)組）捌袜、List（理解為鏈表）说搅、棧、隊(duì)列虏等，半線性結(jié)構(gòu)包括：樹弄唧、二叉樹。
線性結(jié)構(gòu)無法兼顧查找霍衫、插入操作候引，它們要么查找很慢、要么插入很慢敦跌，所以我們引入搜索樹這種半線性結(jié)構(gòu)澄干，希望能兼顧查找和搜索操作。
| 數(shù)據(jù)結(jié)構(gòu) | 查找最差 | 插入最差 | 備注 |
|---|---|---|---|
| 無序數(shù)組 | O(N) | O(N) 或 O(1) | 注1 |
| 有序數(shù)組 | O(logN) | O(N) | |
| 鏈表 | O(N) | O(1) | |
| 二叉搜索樹 | O(N) | O(N) | |
| 平衡二叉搜索樹 | O(logN) | O(logN) |
注1：若采用翻倍擴(kuò)容策略柠傍，則插入的分?jǐn)倳r(shí)間復(fù)雜度為O(1)麸俘，對(duì)本文來說可不必理解那么深入。
雖然二叉搜索樹（BST）的查找携兵、插入操作最壞時(shí)間復(fù)雜度為O(N)疾掰，不甚理想。但在BST的思想基礎(chǔ)上稍加改進(jìn)徐紧，就可以得到平衡二叉搜索樹（BBST）静檬，BBST的查找、插入都是O(logN)并级。BBST有很多種：AVL拂檩、紅黑樹等，本文介紹其中最簡單的AVL嘲碧。
BST的定義和性質(zhì)
BST的順序性：
- 左子樹的所有節(jié)點(diǎn) <= 當(dāng)前節(jié)點(diǎn)
- 右子樹的所有節(jié)點(diǎn) >= 當(dāng)前節(jié)點(diǎn)
由BST的順序性可以引申/推導(dǎo)出幾個(gè)結(jié)論：
- BST的中序遍歷序列必然單調(diào)稻励，見圖（copy自鄧俊輝數(shù)據(jù)結(jié)構(gòu)）
BST的實(shí)現(xiàn)
BST的查找、插入操作是容易的，本文略去不介紹望抽。
而對(duì)于BST的節(jié)點(diǎn)刪除操作加矛，并不是很簡單，需要分幾種情況煤篙。
- 待刪節(jié)點(diǎn)為葉子
- 待刪節(jié)點(diǎn)只有左孩子或右孩子
- 待刪節(jié)點(diǎn)既有左孩子又有右孩子斟览，通過將待刪節(jié)點(diǎn)及其「直接后繼」進(jìn)行交換，從而轉(zhuǎn)為情況2辑奈，直接后繼是指中序遍歷的下一個(gè)節(jié)點(diǎn)苛茂，如圖（copy自鄧俊輝數(shù)據(jù)結(jié)構(gòu)）。
情況1鸠窗、2雖然簡單妓羊，但代碼實(shí)現(xiàn)有點(diǎn)小麻煩。這里你會(huì)發(fā)現(xiàn)C稍计、C++的指針躁绸、引用是那么好用啊丙猬！反倒是Python涨颜、Java實(shí)現(xiàn)起來很難受费韭。不信我們以情況1為例考察下面不同語言的代碼茧球。
# Python語言
def remove(x):
if x.left is None and x.right is None: # 情況1
# 這里麻煩，不但要依賴parent星持，還要判斷自己是左孩子or右孩子
if x == x.parent.left:
x.parent.left = None
else:
x.parent.right = None
// C++語言抢埋，讓調(diào)用者傳入指針的引用
void remove(TreeNode *&x) {
if (x->left == NULL && x->right == NULL) { // 情況1
x = NULL; // 這里就特別方便了
}
}
若不斷插入已經(jīng)升序/降序的元素，BST會(huì)達(dá)到最差情況督暂，此時(shí)BST是極不平衡的揪垄。如圖（copy自鄧俊輝數(shù)據(jù)結(jié)構(gòu)）。
平衡二叉搜索樹：AVL
為了克服BST的最差情況逻翁，我們引入AVL饥努。
todo：剩下內(nèi)容后續(xù)補(bǔ)充，不過我有拖延癥八回。
