樹的平衡與再平衡。

02-03

這篇文章說一下樹的平衡和再平衡。

在一個二分搜索樹中插入隨機值，都能維持一個平均意義上的均衡。但是也可能變得不平衡，然後就會變成一個類似於鏈表的結構。

這時候我們對樹進行再平衡操作的時候。主要有兩種操作：

節點的分割：一個節點如果溢出，可以被分割成為兩個節點。

節點的翻轉：該類操作依舊作用於二叉樹，不過會對邊進行切換，也就是如果x是y的父節點，現在就要讓y成為x的父節點。另外，這個過程x還必須接管y的另外一個子節點。

這裡引入一個AA樹的結構，AA樹（AA-Tree）是計算機科學中數據結構的一種，屬於自平衡二叉查找樹（Self-balancing binary search tree），是紅黑樹的變種。

這裡如果我直接說各種東西可能有點枯燥，我直接上一段Python的代碼：

# 用AA樹結構實現再平衡的二分搜索樹nclass Node:n lft = Nonen rgt = Nonen lvl = 1nn def __init__(self, key, val):n self.key = keyn self.val = valnn def skew(node):n if None in [node, node.lft]:n return noden if node.lft.lvl != node.lvl:n return noden lft = node.lftn node.lft = lft.rgtn lft.rgt = noden return lftnn def split(node):n if None in [node, node.rgt, node.rgt.rgt]:n return noden if node.rgt.rgt.lvl != node.lvl:n return noden rgt = node.rgtn node.rgt = rgt.lftn rgt.lft = noden rgt.lvl += 1n return rgtnn def insert(node, key, val):n if node is None:n return Node(key, val)n if node.key == key:n node.val = valn elif key < node.key:n node.lft = insert(node.lft, key, val)n else:n node.rgt = insert(node.rgt, key, val)n node = skew(node)n node = split(node)n return noden

其實說AA樹之前要先看一個2-3樹結構，這個結構其實是B樹的一種特殊情況。我們知道B樹幾乎是所有資料庫和磁碟的樹形系統。

2-3樹有兩種，一個是雙節點型，另外一個是三節點型。因為他允許一個節點擁有一到兩個鍵，最多三個子節點，這就是三節點型。

而節點翻轉操作。AA樹是有很多的簡單性。但是翻轉過程中會有兩種非法情況，我們必須修復。

第一種是偏斜。比如一個三節點樹內部邊線是指向右邊，如果現在指向的是左邊，我們需要向右翻轉。比如兩個節點為b，d。那麼我們就要將d的父節點變為b的父節點。但是，指向的子節點也就跟著發生了改變。

另一種非法情況是偽節點溢出，比如三個節點連在了同一層。這時候我們也要進行修復，通過翻轉操作修復。直接將中間值變為移動到父節點中，就是向左翻轉或者向右翻轉中間件和左邊或者右邊節點的位置。這樣做會讓提升中間值的等級，我們把這種處理方法叫做分割。

至於具體的代碼實現，或者不太懂得可以看一下代碼實現。

如果你對其他的感興趣，也可以多了解了解插值搜索法，布隆篩選器，還有許多平衡機制，類似於紅黑樹和AVL樹，或者是延伸樹。

謝謝大家關注。樹的平衡和再平衡就說到這裡。