好端端的數據結構，為什麼叫它SB樹呢？
大家好，今天給大家介紹一個很厲害的數據結構，它的名字就很厲害，叫SB樹，業內大佬往往叫做傻叉樹。這個真不是我框你們，而是它的英文縮寫就叫SBT。
SBT其實是英文Size balanced tree的縮寫，翻譯過來可以理解成節點平衡樹，這是大牛陳啟峰在高中參加演算法競賽時期發明的數據結構。不得不說大牛實在是大牛，在高中的時候就已經難以望其項背了。
二叉搜索樹
SBT本質上是一棵二叉搜索樹，我們之前介紹過二叉搜索樹，但是從來沒有真正實現過。我們今天先來複習一下二叉搜索樹的概念。
對於一棵二叉樹而言，如果它滿足對於每一個節點都有，以它右孩子構成的右子樹中的所有元素大於它，左孩子為根構成的左子樹所有元素都小於它，那麼這樣一棵二叉樹就可以被認為是一棵二叉搜索樹。比如下圖，就是一棵經典的二叉搜索樹。
二叉搜索樹有什麼好處呢？我們觀察一下上圖，其實很容易發現，當我們想要查找某個元素是否存在於二叉樹當中的時候，我們可以利用剛才提到的性質進行快速地查找。比如我們想要判斷15這個元素在不在樹當中，我們首先和根節點的11進行判斷，由於15大於11，如果15存在一定在11的右子樹。所以我們移動到它的右子樹16上，繼續判斷。由於15小於16，所以15要存在一定在它的左子樹當中，以此類推，我們只需要經過最多4次比較，就可以找到15。
對於一棵二叉樹而言，如果它是完美二叉樹，每一層的元素都是滿的。我們假設它的層數是k，那麼它一共可以存放個元素。反過來說，如果一個完美二叉樹當中存在n個元素，那麼它的層數應該是。換句話說，我們只需要次操作就可以判斷元素是否存在。
但是這是完美的情況，大多數情況下普通方法構建出來的二叉搜索樹並不是完美的，其中可能存在傾斜。在極端情況下，甚至可以蛻化成鏈表。比如這樣：
正因為如此，所以我們才需要設置一些機制來保證二叉搜索樹的平衡性。平衡性有了，二叉搜索樹的查找效率才能得到保障。
關於讓二叉樹維持平衡的方法，現在有很多種，比如大名鼎鼎的紅黑樹、AVL樹等等，其實本質上都是二叉搜索樹。只是它們維護二叉樹平衡性的方法不同。今天我們介紹的SBT同樣也是一種自平衡二叉搜索樹的實現方法，它的核心機制是旋轉。
旋轉
旋轉是二叉搜索樹維持平衡的常用機制，說是旋轉，其實可以理解成樹上的某些節點之間互換位置。當然位置不能隨意更換，我們必須要保證更換位置之後不會破壞二叉搜索樹的特性，同時讓二叉樹整體更加趨向於平衡。
旋轉分為兩種，一種是左旋，另外一種是右旋。我們一個一個來介紹。
左旋
左旋可以理解成逆時針旋轉，我們來看一個例子：
是不是看著有點蒙，不知道這個旋轉怎麼實現的？這裡我有一個方法，我們可以想像一下，我們把左邊的二叉樹以B為軸逆時針旋轉90度，之後得到的結果是這樣：
我們可以發現B節點擁有三個孩子節點了，這顯然就違反了二叉樹的規則。那麼我們就需要斷掉它的一個孩子，重新分配。那麼為什麼重新分配是把E分配給D而不是把C分配給E或者是D呢？
首先我們觀察一下就知道，C子樹的元素都是比B要大的，那麼把它分配給D顯然不合適。對於把C分配給E，看起來似乎沒有問題，但其實仔細想下也會發現不妥。不妥的原因在哪裡？不妥的地方在於我們不知道E節點的情況，如果E沒有右子樹還好，如果E存在右子樹，那麼怎麼處理？
所以我們只有一種解法，就是把E分配給D做右子樹，因為D原先的右子樹是B，旋轉之後一定就不存在右子樹了。
我們試著寫出偽程式碼：
def left_rotate(u):
ur = u.right
u.right = ur.left
ur.left = u
u = ur
看起來旋轉一通操作猛如虎，但是寫成程式碼也就這麼幾行。
右旋
左旋理解了，右旋也就好辦了，實際上右旋就是左旋的逆操作。左旋剛才是逆時針的旋轉，那麼右旋自然就是順時針的旋轉。這個不需要死記，你只需要記住是向左旋轉或者是向右旋轉就可以了。
對於這樣一棵子樹我們要進行右旋：
之前左旋的時候我們是以右孩子作為旋轉軸，那麼右旋自然就要以左孩子作為旋轉軸了。旋轉90度之後，我們得到了這樣的結果：
同樣我們發現A節點的孩子數量超過了限制，我們需要斷開重連。根據剛才一樣的判斷方法，我們可以發現只有一種重連的方式，就是把C節點作為D的左孩子。因為D的左孩子原本是A，由於旋轉，D沒有左孩子了，這樣連接一定不會引起衝突和問題。最終，我們得到的結果就是：
同樣，我們可以寫出偽程式碼：
def right_rotate(u):
ul = u.left
u.left = ul.right
ul.right = u
u = ul
旋轉很好理解，但是我們為什麼要旋轉呢？我們觀察一下會發現旋轉最重要的功能就是改變了一些節點的位置，這樣可以扭轉一些不平衡的情況。
比如在右旋之前，可能E或者C子樹當中元素過多，引發了不平衡。當我們旋轉之後，我們把E和C分別放到了樹的兩邊。這樣旋轉之後的樹距離平衡也就更接近了一些，但是如何嚴格地保證完全達到完美平衡呢？這裡就需要引入本數據結構的核心概念——size balance了。
Size Balance
前面我們也說過了，實現二叉樹平衡的方法有很多，同樣定義一棵二叉樹是否平衡的標準也有很多。比如在AVL樹當中是通過左右兩棵子樹的樹深來判斷的，兩邊的樹深差不超過1，那麼就認為是平衡了。而在SBT當中，我們對二叉樹平衡的定義是基於節點數量的，也就是Size。
這裡呢，我們需要定義一下size的概念，對於樹上某個節點而言，它的size指的是以它為樹根的子樹當中節點的數量。接下來，我們就要結合size來討論平衡樹不平衡的情況以及我們讓它變得平衡能夠使用的辦法。
首先，我們先來看看我們認為平衡樹達到平衡的條件。這裡呢我們一共有兩個條件，這兩個條件都是對稱的。我們先來看下一個一般意義上的平衡樹。
我們觀察一下上面的圖，來思考一下，什麼情況下可以認為這棵樹達成平衡了呢？是L.size == R.size嗎？這其實是有問題的，因為可能L的節點都落在了A上，R的節點都落在了C上。這同樣是不平衡的，但這種情況除非我們繼續往下遞歸，否則很難識別。
所以這裡換了一種方法，我們判斷R和AB的size的關係，以及L和CD size的關係。我們要求L.size >= C.size, D.size, R.size >= A.size, B.size。
也就是說高層的size一定要比底層來的大，這兩個條件都很直觀，也都很好記。這兩個條件理解了，我們再去分析它不平衡的條件就很清楚了。一共有四種情況：
-
Size of A > size of R
-
Size of B > size of R
-
Size of C > size of L
-
Size of D > size of L
在這4中情況當中，1和3是對稱的，2和4也是對稱的。所以我們只需要著重分析其中兩種就可以了，另外兩種可以通過對稱性得到。
由於我們使用遞歸來維護樹的平衡性的時候，是從底往上的。因此我們可以假設ABCDLR這六棵子樹都是平衡的，這樣可以簡化我們的分析。我們假設我們現在有了一個函數叫做maintain，它可以將一棵不平衡的子樹旋轉到平衡狀態。我們先假設已經有了這個函數，再去看看它裡面需要實現哪些邏輯。
接下來我們來看看上面四種情況如果不滿足的話，我們應該怎麼處理。
情況1
情況1當中A.size > R.size，也就是A當中的節點比較多，為了能夠趨近於平衡。我們將原子樹右旋，得到：
我們右旋之後，A的層級向上提升了一層。我們觀察一下旋轉之後的結果，會發現R子樹的平衡性得到了保持，沒有被破壞，A子樹本身就是平衡的。所以旋轉之後，還有還有兩個節點的平衡性沒有保證。一個是T節點，一個是L節點。那麼，我們遞歸調用maintain(T)和maintain(L)即可。
我們寫成偽程式碼就是：
right_rotate(T)
maintain(T)
maintain(L)
情況2
下面我們來看情況2，也就是B.size > R.size的情況。和上面一種情況類似，由於B的節點比較多，我們希望能夠把B往上提。但是B節點在內部，我們無論對L左旋還是右旋都
既然對T旋轉不行，那麼我們可以對L進行旋轉啊，這樣不就可以影響到B節點了嗎？為了展示地更加清楚，我們把B子樹的孩子節點也畫出來。
接著我們對L進行左旋，這樣可以把B往上提升一層，得到：
雖然我們把B往上提了一層，但是對於T子樹而言，左重右輕的局面仍然沒有改變。要想改變T的不平衡，我們還需要對T進行右旋，得到：
對於這個結果而言，除了L、T和B這三棵樹而言，其他所有的子樹都滿足平衡了。所以我們按順序維護L、T和B即可。
我們寫成程式碼就是：
left_rotate(L)
right_rotate(T)
maintain(L)
maintain(T)
maintain(B)
情況3和情況1剛好相反，我們把左旋和右旋互換即可，情況4和情況2也一樣。
所以我們可以寫出所有的情況來了：
def maintain(t):
if t.left.left.size > t.right.size:
right_rotate(t)
maintain(t.right)
maintain(t)
elif t.left.right.size > t.right.size:
left_rotate(t.left)
right_rotate(t)
maintain(t.left)
maintain(t.right)
maintain(t)
elif t.right.right.size > t.left.size:
left_rotate(t)
maintain(t.left)
maintain(t)
else:
right_rotate(t.right)
left_rotate(t)
maintain(t.left)
maintain(t.right)
maintain(t)
這裡的四種情況羅列出來當然就可以，但是有很多程式碼重複了，我們可以設置一個flag標記，表示我們判斷的是左子樹還是右子樹。這樣我們可以把一些情況歸併在一起，讓程式碼顯得更加簡潔：
def maintain(t, flag):
if flag:
if t.left.left.size > s.right.size:
right_rotate(t)
elif s.left.right.size > t.right.size:
left_rotate(t.left)
right_rotate(t)
else:
return
else:
if t.right.right.size > t.left.size:
left_rotate(t)
elif t.right.left.size > t.left.size:
right_rotate(t.right)
left_rotate(t)
else:
return
maintain(t.left, False)
maintain(t.right, True)
maintain(t, False)
maintain(t, True)
這裡其實我們省略了maintain(t.left, True)和maintain(t.right, False)這兩種情況，這兩種情況我們稍微分析一下會發現其實已經被包含了。
我們搞清楚了這些之後，還有一個疑問沒有解開，就是為什麼旋轉操作可以讓二叉樹趨向於平衡呢，而不是無窮無盡地旋轉下去呢？
儘管我們已經知道了不會，但是還是想要來證明一下。我們以情況一舉例，我們右旋之後的結果是：
我們對比一下旋轉之前的結果，會發現T、R、C、D的高度增加1，而L和A的高度減小了1。由於A.size > R.size，A的size最小等於R.size + 1，也就剛好是T加上R子樹的size。這兩個部分一增一減互相抵消之後，至少還有L這個節點的深度減小了1。也就是說旋轉之後的所有元素的深度和是在減小的，不僅是情況1如此，其他的情況也是一樣。
既然深度和是在減小的，那麼maintain這個操作就一定不是無限的。並且它也的確可以讓樹趨向於穩定，因為完美平衡的情況下所有元素的深度和才是最小的。
實現細節
到這裡我們就已經把SBT的原理都講解完了，但是還存在一些細節上的問題。由於我們是使用Python是引用語言，所以當我們在旋轉的時候進行賦值只是指針之間改變了引用的目標， 並沒有實際對原本的結構進行改變。
我們來看下剛才上面的偽程式碼：
def right_rotate(u):
ul = u.left
u.left = ul.right
ul.right = u
u = ul
由於我們把u的左孩子右旋，代替了u本來的位置。當我們執行u = ul的時候，只是u這個指針改變了指向的位置。至於原本的數據結構當中的內容，並沒有發生變化。因為u、ul這些變數都是臨時變數，都是拷貝出來的，我們隨便更改，也不會影響類當中的值。
在C++當中我們可以傳入引用，這樣我們修改引用就是修改原值了。但是Python當中不行，想要解決這個問題，只有一種方法，就是對於每個節點我們都記錄它父節點的位置。當我們旋轉完了之後，我們需要去更新它父節點中儲存的孩子節點的地址，這樣的話，我們就不只是局部變數之間互相修改了，就真正落實到了數據結構上了。
我們以右旋為例：
def reset_child(self, node, child, left_or_right='left'):
"""
Since Python pass instance by reference, in order to rotate the node in tree, we need to reset the child of father node
Otherwise the modify won't be effective
"""
if node is None:
self.root = child
self.root.father = None
return
if left_or_right == 'left':
node.lchild = child
else:
node.rchild = child
if child is not None:
child.father = node
def rotate_right(self, node, left_or_right='left'):
"""
Right rotate operation of Treap.
Example:
D
/ \
A B
/ \
E C
After rotate:
A
/ \
E D
/ \
C B
"""
father = node.father
lchild = node.lchild
node.lchild = lchild.rchild
if lchild.rchild is not None:
lchild.rchild.father = node
lchild.rchild = node
node.father = lchild
# 要重新reset父節點的孩子節點，這樣整個改動才是真的生效了。
self.reset_child(father, lchild, left_or_right)
# 更新節點買的size
node.size = node_size(node.lchild) + node_size(node.rchild) + 1
lchild.size = node_size(lchild.lchild) + node_size(lchild.rchild) + 1
return lchild
由於每個節點的孩子節點有兩個，所以我們還需要一個變數來記錄我們當前要改變的節點究竟是它父親節點的左孩子還是右孩子，這樣我們才能在reset的時候正確地修改。不僅是旋轉如此，刪除和添加也是一樣的，我們都需要修改父節點當中的資訊，否則我們修改來修改去，改的都只是局部變數而已。
另外一點是我們旋轉之後還需要更新每個節點的size，這個邏輯如果忘記了，那麼後面的maintain就無從談起了。
最後我們思考一個問題，我們在什麼情況下需要maintain操作呢，也就是什麼情況下會破壞樹的平衡性呢？其實很簡單，就是當樹中的元素數量發生改變的時候。無論是增多或者是減少都有可能破壞樹的平衡。所以我們在完成了插入和刪除之後都需要maintain一次樹的平衡。
論文當中對於maintain這個操作還有詳細的分析，可以證明maintain的均攤複雜度是，也就是常數級的操作，這也是為什麼SBT運行效率高的原因。
論文的最後還附上了SBT和其他常用平衡樹數據結構的比較，我們可以看出SBT無論是運行效率還是品質都是其中佼佼者。
最後，我們聊一聊SBT的實現。關於SBT這類複雜數據結構的實現還是C++要更方便一些，主要原因就是因為C++當中帶有引用和指針的傳遞操作。我們可以在函數內部修改全局的值，而Python當中則不行。參數傳遞默認傳遞的是拷貝，我們在函數內部賦值並不會影響結果。所以如果使用Python實現會更加複雜一些，並且需要一些修改父節點的額外操作。
因此網上關於SBT的Python實現非常非常少，我有自信說我的程式碼目前是我能找到的實現得比較好的一個。相關程式碼很長，足足有五百多行，不適合放在文章當中。如果大家感興趣，可以在公眾號內回復SBT關鍵字進行獲取。
今天的文章就到這裡，衷心祝願大家每天都有所收穫。如果還喜歡今天的內容的話，請來一個三連支援吧~（點贊、關注、轉發）
