這是一位 google 工程師分享的8小時(shí)的數(shù)據(jù)結(jié)構(gòu)的視頻,我的筆記
Balanced Binary Search Trees (BBST)
- 滿足low (logarithmic) height for fast insertions and deletions
- clever usage of a
tree invairantandtree rotation
AVL Tree
一種BBST率碾，滿足O(log n)的插入刪除和查找復(fù)雜度检诗，也是第一種BBST，后續(xù)出現(xiàn)的更多的：2-3 tree, AA tree, scapegoat tree, red-black tree(avl的最主要競(jìng)爭(zhēng)對(duì)手)
能保持平衡的因子：Balance Factor (BF)
- BF(node) = H(node.right) - H(node.left)
- H(x) = height of node = # of edges between (x, furthest leaf)
- 平衡就是左右平均分配匣掸，所以要么均分有额，要么某一邊多一個(gè)癣猾，BF其實(shí)就是(-1, 0, 1)里的一個(gè)了 <- avl tree invariant
一個(gè)node需要存：
- 本身的(comparable) value
- balance factor
- the
heightof this node - left/right pointer
使樹(shù)保持左右平衡主要是靠rotation，極簡(jiǎn)情況下（三個(gè)node）零聚，我們有兩種基本情況（left-left, right-right）袍暴，有其它情況就旋轉(zhuǎn)一次變成這兩種情況之一：
2021-12-02-13-41-34.png
Insertion
一次插入需要考慮的是，插在哪邊隶症，以及插入后對(duì)bf, height和balance的破壞
2021-12-02-15-00-15.png
其中修復(fù)平衡就是上圖中幾個(gè)基本結(jié)構(gòu)的轉(zhuǎn)換
Removal
avl樹(shù)就是一棵BST政模，刪除節(jié)點(diǎn)分兩步：
- 按照bst的方法查找節(jié)點(diǎn)，即小的在左邊找蚂会，大的在右邊找
- 也按bst的原則刪除元素淋样，即找到元素后，把左邊的最大值或右邊的最小值拿過(guò)來(lái)補(bǔ)上刪除的位置
- 這一步是多出來(lái)的胁住，顯然是要更新一下節(jié)點(diǎn)的bf和height趁猴，及重新balance一次了。
前兩部分參考BST一章彪见，流程偽代碼：
function remove(node, value): ...
# Code for BST item removal here
...
# Update balance factor
update(node)
# Rebalance tree
return balance(node)
