通過之前對二叉搜索樹介紹可知畔塔，將集合構(gòu)造為二叉搜索樹結(jié)構(gòu)，該結(jié)構(gòu)下對樹中節(jié)點的查詢、刪除和插入三種操作澈吨，時間復(fù)雜度均為
~
把敢。影響時間復(fù)雜度的因素即為二叉樹的高，為了盡量避免樹中每層上只有一個節(jié)點的情況棚辽，這里引入平衡二叉樹技竟。
定義
平衡二叉樹也叫自平衡二叉搜索樹（Self-Balancing Binary Search Tree），所以其本質(zhì)也是一顆二叉搜索樹屈藐，不過為了限制左右子樹的高度差榔组，避免出現(xiàn)傾斜樹等偏向于線性結(jié)構(gòu)演化的情況，所以對二叉搜索樹中每個節(jié)點的左右子樹作了限制联逻，左右子樹的高度差稱之為平衡因子搓扯，樹中每個節(jié)點的平衡因子絕對值不大于 ，此時二叉搜索樹稱之為平衡二叉樹包归。
自平衡是指锨推，在對平衡二叉樹執(zhí)行插入或刪除節(jié)點操作后，可能會導(dǎo)致樹中某個節(jié)點的平衡因子絕對值超過 公壤，即平衡二叉樹變得“不平衡”呐赡，為了恢復(fù)該節(jié)點左右子樹的平衡翔试，此時需要對節(jié)點執(zhí)行旋轉(zhuǎn)操作宦棺。
情景分析
在執(zhí)行插入或刪除節(jié)點操作后施流，平衡因子絕對值變?yōu)榇笥? 的情況，即左右子樹的高度差為
或
的情況确憨，可以歸納為如下四種：
- 左左情況(LL)
情況是指根節(jié)點的平衡因子為
译荞，根節(jié)點的左子節(jié)點平衡因子為
或
。
如圖 LL_1 所示休弃，當(dāng)節(jié)點 的子節(jié)點被刪除吞歼，或者節(jié)點
插入子節(jié)點
時，根節(jié)點
的平衡因子變?yōu)?
塔猾，
的左子節(jié)點
的平衡因子為
篙骡。
或者如圖 LL_2 所示，當(dāng)節(jié)點 的子節(jié)點被刪除丈甸，根節(jié)點
的平衡因子變?yōu)?
医增，
的左子節(jié)點
的平衡因子為
。
當(dāng)根節(jié)點的左子樹高度比右子樹的高度大
老虫，因為平衡二叉樹是一種有序結(jié)構(gòu)，節(jié)點值之間具有大小關(guān)系茫多，所以如果根節(jié)點保持不變祈匙，左右子樹始終分隔兩岸，則無論如何調(diào)整節(jié)點位置，二叉樹始終不可能恢復(fù)平衡夺欲。所以需要更換根節(jié)點跪帝，使得新的根節(jié)點的左右子樹的高度趨于平衡。
該情況下需要對平衡二叉樹執(zhí)行右旋操作：
- 設(shè)置根節(jié)點
的左子節(jié)點為新的根節(jié)點
些阅；
- 將
對于圖 LL_1缤谎，節(jié)點 的平衡因子為
抒倚，設(shè)
節(jié)點的左子樹
高度為
，則右子樹
高度為
坷澡，因為
的平衡因子為
托呕，所以二叉樹
的高度為：
。則右旋操作后频敛，
的左子樹高度不變?yōu)?
项郊，右子樹高度為：
，此時二叉樹為平衡二叉樹斟赚，如下圖 balanced_LL_1着降。
對于圖 LL_2，節(jié)點 的平衡因子為
汁展，設(shè)
節(jié)點的左右子樹高度為
鹊碍，則二叉樹
的高度為：
。右旋操作后食绿，
的左子樹高度不變?yōu)?
侈咕，右子樹高度為：
，此時二叉樹為平衡二叉樹器紧，如下圖 balanced_LL_2耀销。
右旋代碼
# rotate from left to right with the left-child node as the axis
def rotateL2R(node):
leftChild = node.lchild
leftChild.rchild,node.lchild = node,leftChild.rchild # rotate
updateHeight(node)
updateHeight(leftChild)
return leftChild
其中 函數(shù)作用為更新調(diào)整后節(jié)點的平衡因子，因為右旋操作平衡因子變化的節(jié)點只有兩個：原根節(jié)點和新根節(jié)點铲汪，即根節(jié)點和根節(jié)點的左子節(jié)點熊尉，所以只需要對這兩個節(jié)點執(zhí)行
函數(shù)。函數(shù)代碼參考如下：
更新二叉樹高度
# update the height of the node
def updateHeight(root):
if root.lchild and root.rchild:
root.height = max(root.lchild.height, root.rchild.height) + 1
elif root.lchild:
root.height = root.lchild.height + 1
elif root.rchild:
root.height = root.rchild.height + 1
else:
root.height = 0
樹的高度也就是左右子樹的高度最大值加一掌腰，若無子樹狰住，則設(shè)置樹高為零。
- 右右情況(RR)
該情況與上面的左左情況具有對稱性齿梁，對平衡二叉樹執(zhí)行插入或刪除節(jié)點操作后催植，根節(jié)點的平衡因子變?yōu)?肮蛹，根節(jié)點的右子節(jié)點平衡因子為
或
，為了恢復(fù)二叉樹的平衡创南，需要進行左旋伦忠，來使得新的左右子樹高度區(qū)域平衡。
如上圖 所示稿辙，該情況下需要對平衡二叉樹執(zhí)行左旋操作：
- 設(shè)置根節(jié)點
- 將
左旋操作后冬耿，平衡二叉樹如圖 balanced_RR 所示。
左旋代碼
# rotate from right to left with the right-child node as the axis
def rotateR2L(node):
rightChild = node.rchild
rightChild.lchild, node.rchild = node, rightChild.lchild # rotate
updateHeight(node)
updateHeight(rightChild)
return rightChild
左旋操作同右旋一樣萌壳，只更改了原根節(jié)點和新根節(jié)點的平衡因子亦镶，所以只需要對這兩個節(jié)點執(zhí)行 函數(shù)。
- 左右情況
該情況下根節(jié)點的平衡因子與左左情況相同袱瓮，都為 缤骨，不同之處在于左子節(jié)點的平衡因子為
，若按照之前直接進行右旋操作尺借，則旋轉(zhuǎn)操作后二叉樹扔處于不平衡狀態(tài)绊起。
對于圖 LR，節(jié)點 的平衡因子為
燎斩，設(shè)
節(jié)點的左子樹
高度為
虱歪，則右子樹
高度為
，因為
的平衡因子為
栅表，所以二叉樹
的高度為：
笋鄙。則右旋操作后，
的左子樹高度不變?yōu)?
怪瓶，右子樹高度為：
萧落，因為
的平衡因子為
，所以按此方式的旋轉(zhuǎn)操作沒有效果洗贰。
所以該情況下找岖，首先需要對根節(jié)點的左子節(jié)點進行調(diào)整，即將左子節(jié)點的平衡因子由 調(diào)整為
敛滋， 使得當(dāng)前情況轉(zhuǎn)換為
情況许布，然后再對二叉樹執(zhí)行右旋操作。
step 1:對左子樹執(zhí)行左旋操作
step 2:對二叉樹執(zhí)行右旋操作
- 右左情況
該情況與上面左右情況對稱绎晃，根節(jié)點的平衡因子為 爹脾，右子節(jié)點平衡因子為
帖旨，需要首先對右子樹進行右旋操作，調(diào)整二叉樹為
情況灵妨，再對二叉樹執(zhí)行左旋操作。
step 1:對右子樹執(zhí)行右旋操作
step 2:對二叉樹執(zhí)行左旋操作
性能分析
因為平衡二叉樹也是二叉搜索樹落竹，回顧二叉搜索樹中的操作復(fù)雜度泌霍，查詢、插入和刪除復(fù)雜度均為
~
述召。平衡二叉樹中查詢復(fù)雜度影響因素自然為樹的高度朱转；插入節(jié)點操作可以拆分為兩個步驟：查詢節(jié)點位置，插入節(jié)點后平衡操作积暖；刪除節(jié)點操作同理可以拆分為兩個步驟：查詢節(jié)點位置藤为，刪除節(jié)點后平衡操作。
平衡調(diào)節(jié)過程中可能存在旋轉(zhuǎn)操作夺刑，遞歸執(zhí)行的次數(shù)則依賴于樹的高度（可以優(yōu)化為當(dāng)前節(jié)點平衡因子不發(fā)生變化缅疟，則取消向上遞歸）。所以平衡二叉樹中查詢遍愿、插入和刪除節(jié)點操作的復(fù)雜度依賴于樹高存淫。
平衡二叉樹因為左右子樹的平衡因子限制，所以不可能存在類似于斜樹的情況沼填，因為任一節(jié)點的左右子樹高度差最大為一桅咆，且二叉樹具有對稱性，所以不妨設(shè)每個子樹的左子樹高度大于右子樹高度坞笙。
根據(jù)平衡二叉樹定義可知岩饼，若二叉樹左子樹高度為
，則右子樹高度最少也要是
薛夜，方能滿足平衡二叉樹的平衡特性籍茧。以
表示高度為
的平衡二叉樹的最少節(jié)點個數(shù)，若二叉樹不是空樹則有：
根據(jù)推導(dǎo)公式可知却邓，平衡二叉樹的高度最大為 硕糊。當(dāng)二叉樹向完全二叉樹靠攏，盡量填滿每層上的節(jié)點時腊徙，樹的高度最小简十，為
。所以相對于二叉搜索樹撬腾，平衡二叉樹避免了向線性結(jié)構(gòu)演化的傾向螟蝙，查詢、插入和刪除節(jié)點的時間復(fù)雜度為
~
民傻。因為每個節(jié)點上需要保存平衡因子胰默，所以空間復(fù)雜度要略高于二叉搜索樹场斑。
代碼附錄
python版本：3.7，樹中的遍歷牵署、節(jié)點插入和刪除操作使用的是遞歸形式
- 樹節(jié)點定義
# tree node definition
class Node(object):
def __init__(self, value, height=0, lchild=None, rchild=None):
self.lchild = lchild
self.rchild = rchild
self.value = value
self.height = height
相對于二叉搜索樹的節(jié)點定義漏隐，增加了 屬性。
- 樹定義
# tree definition
class Tree(object):
def __init__(self, root=None):
self.root = root
# node in-order traversal(LDR)
def traversal(self):
traversal(self.root)
# insert node
def insert(self, value):
self.root = insert(self.root, value)
# delete node
def delete(self, value):
self.root = delete(self.root, value)
樹結(jié)構(gòu)定義與二叉搜索樹中結(jié)構(gòu)相同保持不變奴迅。
- 模塊中對樹結(jié)構(gòu)中的函數(shù)進行實現(xiàn)
# node in-order traversal(LDR)
def traversal(node):
if not node:
return
traversal(node.lchild)
print(node.value, 'height=', node.height, end=', ')
traversal(node.rchild)
# insert node
'''
the recursive insert operation has a flaw,
that the binary tree will recursively updates the height of the parent node
even if the inserted element already exists.
'''
def insert(root, value):
if not root:
return Node(value)
if value < root.value:
root.lchild = insert(root.lchild, value)
elif value > root.value:
root.rchild = insert(root.rchild, value)
return checkBalance(root)
# check whether the tree is balanced
def checkBalance(root):
if not root:
return None
if abs(heightDiffL2R(root)) < 2: # the tree is balance
updateHeight(root)
elif heightDiffL2R(root) == 2: # situation L
if heightDiffL2R(root.lchild) == -1: # situation LR
root.lchild = rotateR2L(root.lchild)
root = rotateL2R(root)
else: # situation LL
root = rotateL2R(root)
elif heightDiffL2R(root) == -2: # situation R
if heightDiffL2R(root.rchild) == 1: # situation RL
root.rchild = rotateL2R(root.rchild)
root = rotateR2L(root)
else: # situation RR
root = rotateR2L(root)
return root
# get the height difference between left-child and right-child
def heightDiffL2R(node):
if node.lchild and node.rchild:
return node.lchild.height - node.rchild.height
if node.lchild:
return node.lchild.height + 1
if node.rchild:
return -(node.rchild.height + 1)
return 0
# update the height of the node
def updateHeight(root):
if root.lchild and root.rchild:
root.height = max(root.lchild.height, root.rchild.height) + 1
elif root.lchild:
root.height = root.lchild.height + 1
elif root.rchild:
root.height = root.rchild.height + 1
else:
root.height = 0
# rotate from left to right with the left-child node as the axis
def rotateL2R(node):
leftChild = node.lchild
leftChild.rchild, node.lchild = node, leftChild.rchild
updateHeight(node)
updateHeight(leftChild)
return leftChild
# rotate from right to left with the right-child node as the axis
def rotateR2L(node):
rightChild = node.rchild
rightChild.lchild, node.rchild = node, rightChild.lchild
updateHeight(node)
updateHeight(rightChild)
return rightChild
def delete(root, value):
if not root:
return None
if root.value > value:
root.lchild = delete(root.lchild, value)
elif root.value < value:
root.rchild = delete(root.rchild, value)
else:
if root.lchild and root.rchild: # degree of the node is 2
target = transferDeleteNode(root)
root = delete(root, target)
root.value = target
else: # degree of the node is [0|1]
root = root.lchild if root.lchild else root.rchild
return checkBalance(root)
# find the maximum node or the minimum node in the tree
def transferDeleteNode(node):
if node.rchild.height > node.lchild.height:
target = node.rchild
while target.lchild:
target = target.lchild
else:
target = node.lchild
while target.rchild:
target = target.rchild
return target.value
- 測試代碼與輸出
if __name__ == '__main__':
arr = [5, 3, 4, 0, 2, 1, 8, 6, 9, 7,7]
T = Tree()
for i in arr:
T.insert(i)
print('BST in-order traversal------------------')
T.traversal()
print('\ndelete test------------------')
for i in arr[::-1]:
print('after delete', i, end=',BST in-order is = ')
T.delete(i)
T.traversal()
print()
- 輸出結(jié)果為：
BST in-order traversal------------------
0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 0, 6 height= 2, 7 height= 0, 8 height= 1, 9 height= 0,
delete test------------------
after delete 7,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 0, 6 height= 2, 8 height= 1, 9 height= 0,
after delete 7,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 0, 6 height= 2, 8 height= 1, 9 height= 0,
after delete 9,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 0, 6 height= 2, 8 height= 0,
after delete 6,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 3, 3 height= 0, 4 height= 1, 5 height= 2, 8 height= 0,
after delete 8,BST in-order is = 0 height= 1, 1 height= 0, 2 height= 2, 3 height= 0, 4 height= 1, 5 height= 0,
after delete 1,BST in-order is = 0 height= 0, 2 height= 2, 3 height= 0, 4 height= 1, 5 height= 0,
after delete 2,BST in-order is = 0 height= 0, 3 height= 2, 4 height= 1, 5 height= 0,
after delete 0,BST in-order is = 3 height= 0, 4 height= 1, 5 height= 0,
after delete 4,BST in-order is = 3 height= 1, 5 height= 0,
after delete 3,BST in-order is = 5 height= 0,
after delete 5,BST in-order is =
github鏈接：平衡二叉樹
