1. AVL樹(shù)

(1) 定義

平衡因子（Balance Factor）：某節(jié)點(diǎn)的 左右子樹(shù) 的高度差

AVL樹(shù)的特點(diǎn)：

• 每個(gè)節(jié)點(diǎn)的 平衡因子 只可能是1、0、-1（絕對(duì)值<=1，否則失衡）
• 每個(gè)節(jié)點(diǎn)的 左右子樹(shù) 高度差不超過(guò)1
• 搜索、添加、刪除的時(shí)間復(fù)雜度是

平衡

失衡

(2) 解決失衡方法

1> LL - 右旋轉(zhuǎn)（單旋）

LL

2> RR - 左旋轉(zhuǎn)（單旋）

RR

3> LR - RR左旋轉(zhuǎn)，LL右旋轉(zhuǎn)（雙旋）

LR

4> RL - LL右旋轉(zhuǎn)，RR左旋轉(zhuǎn)（雙旋）

RL

(3) 添加導(dǎo)致的失衡

示例：往下面這棵子樹(shù)添加 13

• 最壞情況：可能會(huì)導(dǎo)致 所有祖先節(jié)點(diǎn) 都失衡
• 父節(jié)點(diǎn)、非祖先節(jié)點(diǎn)，都不可能失衡

添加導(dǎo)致的失衡

(4) 刪除導(dǎo)致的失衡

示例：刪除子樹(shù)中的 16

• 可能會(huì)導(dǎo)致 父節(jié)點(diǎn)或祖先節(jié)點(diǎn) 失衡
• 只有一個(gè)節(jié)點(diǎn)會(huì)失衡，其他節(jié)點(diǎn) 都不可能失衡

刪除導(dǎo)致的失衡

刪除導(dǎo)致的失衡

(5) 總結(jié)

添加

• 可能會(huì)導(dǎo)致 所有祖先節(jié)點(diǎn) 都失衡
• 只要讓 高度最低的失衡節(jié)點(diǎn) 恢復(fù)平衡，整棵樹(shù)就恢復(fù)平衡【僅需次調(diào)整】

刪除

• 可能會(huì)導(dǎo)致 父節(jié)點(diǎn)或祖先節(jié)點(diǎn) 失衡（只有1個(gè)節(jié)點(diǎn)會(huì)失衡）
• 恢復(fù)平衡后，可能會(huì)導(dǎo)致 更高層的祖父節(jié)點(diǎn) 失衡【最多需要次調(diào)整】

平均時(shí)間復(fù)雜度

• 搜索：
• 添加：，僅需次的旋轉(zhuǎn)操作
• 刪除：，最多需要次的旋轉(zhuǎn)操作