Python 樹表查找（二叉排序樹、平衡二叉樹）
什么是樹表查詢？
借助具有特殊性質(zhì)的樹數(shù)據(jù)結(jié)構(gòu)進(jìn)行關(guān)鍵字查找。
本文所涉及到的特殊結(jié)構(gòu)性質(zhì)的樹包括：
二叉排序樹。 平衡二叉樹。
使用上述樹結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)時(shí)，因其本身對(duì)結(jié)點(diǎn)之間的關(guān)系以及順序有特殊要求，也得益于這種限制，在查詢某一個(gè)結(jié)點(diǎn)時(shí)會(huì)帶來(lái)性能上的優(yōu)勢(shì)和操作上的方便。
樹表查詢屬于動(dòng)態(tài)查找算法。
所謂動(dòng)態(tài)查找，不僅僅能很方便查詢到目標(biāo)結(jié)點(diǎn)。而且可以根據(jù)需要添加、刪除結(jié)點(diǎn)，而不影響樹的整體結(jié)構(gòu)，也不會(huì)影響數(shù)據(jù)的查詢。
本文并不會(huì)深入講解樹數(shù)據(jù)結(jié)構(gòu)的基本的概念，僅是站在使用的角度說清楚動(dòng)態(tài)查詢。閱讀此文之前，請(qǐng)預(yù)備一些樹的基礎(chǔ)知識(shí)。
1. 二叉排序樹
二叉樹是樹結(jié)構(gòu)中具有艷明特點(diǎn)的子類。
二叉樹要求樹的每一個(gè)結(jié)點(diǎn)（除葉結(jié)點(diǎn)）的子結(jié)點(diǎn)最多只能有 2 個(gè)。在二叉樹的基礎(chǔ)上，繼續(xù)對(duì)其進(jìn)行有序限制則變成二叉排序樹。
二叉排序樹特點(diǎn)：
基于二叉樹結(jié)構(gòu)，從根結(jié)點(diǎn)開始，從上向下，每一個(gè)父結(jié)點(diǎn)的值大于左子結(jié)點(diǎn)（如果存在左子結(jié)點(diǎn)）的值，而小于右子結(jié)點(diǎn)（如果存在右子結(jié)點(diǎn)）的值。則把符合這種特征要求的樹稱為二叉排序樹。
1.1 構(gòu)建一棵二叉排序樹
如有數(shù)列 nums=[5,12,4,45,32,8,10,50,32,3]。通過下面流程，把每一個(gè)數(shù)字映射到二叉排序樹的結(jié)點(diǎn)上。
如果樹為空，把第一個(gè)數(shù)字作為根結(jié)點(diǎn)。如下圖，數(shù)字 5 作為根結(jié)點(diǎn)。
如果已經(jīng)存在根結(jié)點(diǎn)，則把數(shù)字和根結(jié)點(diǎn)比較，小于根結(jié)點(diǎn)則作為根結(jié)點(diǎn)的左子結(jié)點(diǎn)，大于根結(jié)點(diǎn)的作為根結(jié)點(diǎn)的右子結(jié)點(diǎn)。如數(shù)字 4 插入到左邊，數(shù)字 12 插入到右邊。
數(shù)列中后面的數(shù)字依據(jù)相同法則，分別插入到不同子的位置。
原始數(shù)列中的數(shù)字是無(wú)序的，根據(jù)二叉排序樹的插入算法，最終可得到一棵有排序性質(zhì)的樹結(jié)構(gòu)。對(duì)此棵樹進(jìn)行中序遍歷就可得到從小到大的一個(gè)遞增有序數(shù)列。
綜觀二叉排序樹，進(jìn)行關(guān)鍵字查找時(shí)，也應(yīng)該是接近于二分查找算法的時(shí)間度。
這里有一個(gè)要注意的地方。
原始數(shù)列中的數(shù)字順序不一樣時(shí)，生成的二叉排序樹的結(jié)構(gòu)也會(huì)有差異性。對(duì)于查找算法的性能會(huì)產(chǎn)生影響。
1.2 二叉排序樹的數(shù)據(jù)結(jié)構(gòu)
現(xiàn)在使用OOP設(shè)計(jì)方案描述二叉排序樹的數(shù)據(jù)結(jié)構(gòu)。
首先，設(shè)計(jì)一個(gè)結(jié)點(diǎn)類，用來(lái)描述結(jié)點(diǎn)本身的信息。
'''
二叉排序樹的結(jié)點(diǎn)類
'''
class TreeNode():
def __init__(self, value):
# 結(jié)點(diǎn)上的值
self.value = value
# 左結(jié)點(diǎn)
self.l_child = None
# 右結(jié)點(diǎn)
self.r_child = None結(jié)點(diǎn)類中有 3 個(gè)屬性：
value：結(jié)點(diǎn)上附加的數(shù)據(jù)信息。 l_child：左子結(jié)點(diǎn)，初始值為 None 。 r_child：右子結(jié)點(diǎn)，初始值為 None。
二叉排序樹類： 用來(lái)實(shí)現(xiàn)樹的增、刪、改、查。
'''
二叉排序樹類
'''
class BinarySortTree:
# 初始化樹
def __init__(self, value=None):
pass
'''
在整棵樹上查詢是否存在給定的關(guān)鍵字
'''
def find(self, key):
pass
'''
使用遞歸進(jìn)行查詢
'''
def find_dg(self, root, key):
pass
'''
插入新結(jié)點(diǎn)
'''
def insert(self, value):
pass
'''
中序遍歷
'''
def inorder_traversal(self):
pass
'''
刪除結(jié)點(diǎn)
'''
def delete(self, key):
pass
'''
檢查是不是空樹
'''
def is_empty(self):
return self.root == None二叉排序樹中可以有更多方法，本文只關(guān)注與查找主題有關(guān)的方法。
1.3 實(shí)現(xiàn)二叉排序樹類中的方法：
__init__ 初始化方法：
# 初始化樹
def __init__(self, value=None):
self.root = None
if value is not None:
root_node = TreeNode(value)
self.root = root_node在初始化樹對(duì)象時(shí)，如果指定了數(shù)據(jù)信息，則創(chuàng)建有唯一結(jié)點(diǎn)的樹，否則創(chuàng)建一個(gè)空樹。
關(guān)鍵字查詢方法：查詢給定的關(guān)鍵字在二叉排序樹結(jié)構(gòu)中是否存在。
查詢流程：
把給定的關(guān)鍵字和根結(jié)點(diǎn)相比較。如果相等，則返回查找成功，結(jié)束查詢. 如果根結(jié)點(diǎn)的值大于關(guān)鍵字，則繼續(xù)進(jìn)入根結(jié)點(diǎn)的左子樹中開始查找。 如果根結(jié)點(diǎn)的值小于關(guān)鍵字，則進(jìn)入根結(jié)點(diǎn)的右子樹中開始查找。 如果沒有查詢到關(guān)鍵字，則返回最后訪問過的結(jié)點(diǎn)和查詢不成功信息。
關(guān)鍵字查詢的本質(zhì)是二分思想，以當(dāng)前結(jié)點(diǎn)為分界線，然后向左或向右進(jìn)行分枝查找。
非遞歸實(shí)現(xiàn)查詢方法：
'''
在整棵樹上查詢是否存在給定的關(guān)鍵字
key: 給定的關(guān)鍵字
'''
def find(self, key):
# 從根結(jié)點(diǎn)開始查找。
move_node = self.root
# 用來(lái)保存最后訪問過的結(jié)點(diǎn)
last_node = None
while move_node is not None:
# 保存當(dāng)前結(jié)點(diǎn)
last_node = move_node
# 把關(guān)鍵字和當(dāng)前結(jié)點(diǎn)相比較
if self.root.value == key:
# 出口一：成功查找
return move_node
elif move_node.value > key:
# 在左結(jié)點(diǎn)查找
move_node = move_node.l_child
else:
# 在右結(jié)點(diǎn)中查找
move_node = move_node.r_child
# 出口二：如果沒有查詢到，則返回最后訪問過的結(jié)點(diǎn)及None（None 表示沒查詢到）
return last_node, None注意：當(dāng)沒有查詢到時(shí)，返回的值有 2 個(gè)，最后訪問的結(jié)點(diǎn)和沒有查詢到的信息。
為什么要返回最后一次訪問過的結(jié)點(diǎn)？
反過來(lái)想想，本來(lái)應(yīng)該在這個(gè)地方找到，但是沒有，如果改成插入操作，就應(yīng)該插入到此位置。
基于遞歸實(shí)現(xiàn)的查找：
'''
使用遞歸進(jìn)行查詢
'''
def find_dg(self, root, key):
# 結(jié)點(diǎn)不存在
if root is None:
return None
# 相等
if root.value == key:
return root
if root.value > key:
return self.find_dg(root.l_child, key)
else:
return self.find_dg(root.r_child, key)再看看如何把數(shù)字插入到二叉排序樹中，利用二叉排序樹進(jìn)行查找的前提條件就是要把數(shù)字映射到二叉排序樹的結(jié)點(diǎn)上。
插入結(jié)點(diǎn)的流程：
當(dāng)需要插入某一個(gè)結(jié)點(diǎn)時(shí)，先搜索是否已經(jīng)存在于樹結(jié)構(gòu)中。 如果沒有，則獲取到查詢時(shí)訪問過的最一個(gè)結(jié)點(diǎn)，并和此結(jié)點(diǎn)比較大小。 如果比此結(jié)點(diǎn)大，則插入最后訪問過結(jié)點(diǎn)的右子樹位置。 如果比此結(jié)點(diǎn)小，則插入最后訪問過結(jié)點(diǎn)的左子樹位置。
insert 方法的實(shí)現(xiàn)：
'''
插入新結(jié)點(diǎn)
'''
def insert(self, value):
# 查詢是否存在此結(jié)點(diǎn)
res = self.find(value)
if type(res) != TreeNode:
# 沒找到，獲取查詢時(shí)最后訪問過的結(jié)點(diǎn)
last_node = res[0]
# 創(chuàng)建新結(jié)點(diǎn)
new_node = TreeNode(value)
# 最后訪問的結(jié)點(diǎn)是根結(jié)點(diǎn)
if last_node is None:
self.root = new_node
if value > last_node.value:
last_node.r_child = new_node
else:
last_node.l_child = new_node怎么檢查插入的結(jié)點(diǎn)是符合二叉樹特征？
再看一下前面根據(jù)插入原則手工繪制的插入演示圖：
上圖有 4 個(gè)子結(jié)點(diǎn)，寫幾行代碼測(cè)試一下，看從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的順序是否正確。
測(cè)試插入方法：
if __name__ == "__main__":
nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
tree = BinarySortTree(5)
for i in range(1, len(nums)):
tree.insert(nums[i])
print("測(cè)試根5 -> 左4 ->左3:")
tmp_node = tree.root
while tmp_node != None:
print(tmp_node.value, end=" ->")
tmp_node = tmp_node.l_child
print("\n測(cè)試根5 -> 右12 ->右45->右50：")
tmp_node = tree.root
while tmp_node != None:
print(tmp_node.value, end=" ->")
tmp_node = tmp_node.r_child
'''
輸出結(jié)果：
測(cè)試根5 -> 左4 ->左3:
5 ->4 ->3 ->
測(cè)試根5 -> 右12 ->右45->右50：
5 ->12 ->45 ->50 ->
''' 查看結(jié)果，可以初步判斷插入的數(shù)據(jù)是符合二叉排序樹特征的。當(dāng)然，更科學(xué)的方式是寫一個(gè)遍歷方法。樹的遍歷方式有 3 種：
前序：根，左，右。 中序：左，根，右。 后序。左，右，根。
對(duì)二叉排序樹進(jìn)行中序遍歷，理論上輸出的數(shù)字應(yīng)該是有序的。這里寫一個(gè)中序遍歷，查看輸出的結(jié)點(diǎn)是不是有序的，從而驗(yàn)證查詢和插入方法的正確性。
使用遞歸實(shí)現(xiàn)中序遍歷：
'''
中序遍歷
'''
def inorder_traversal(self, root):
if root is None:
return
self.inorder_traversal(root.l_child)
print(root.value,end="->")
self.inorder_traversal(root.r_child)測(cè)試插入的順序：
if __name__ == "__main__":
nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
tree = BinarySortTree(5)
# res = tree.find(51)
for i in range(1, len(nums)):
tree.insert(nums[i])
tree.inorder_traversal(tree.root)
'''
輸出結(jié)果
3->4->5->8->10->12->32->45->50->
'''二叉排序樹很有特色的數(shù)據(jù)結(jié)構(gòu)，利用其存儲(chǔ)特性，可以很方便地進(jìn)行查找、排序。并且隨時(shí)可添加、刪除結(jié)點(diǎn)，而不會(huì)影響排序和查找操作。基于樹表的查詢操作稱為動(dòng)態(tài)查找。
二叉排序樹中如何刪除結(jié)點(diǎn)
從二叉樹中刪除結(jié)點(diǎn)，需要保證整棵二叉排序樹的有序性依然存在。刪除操作比插入操作要復(fù)雜，下面分別討論。
如果要?jiǎng)h除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)。
只需要把要?jiǎng)h除結(jié)點(diǎn)的父結(jié)點(diǎn)的左結(jié)點(diǎn)或右結(jié)點(diǎn)的引用值設(shè)置為空就可以了。
刪除的結(jié)點(diǎn)只有一個(gè)右子結(jié)點(diǎn)。如下圖刪除結(jié)點(diǎn) 8。
因?yàn)榻Y(jié)點(diǎn)8沒有左子樹，在刪除之后，只需要把它的右子結(jié)點(diǎn)替換刪除結(jié)點(diǎn)就可以了。
刪除的結(jié)點(diǎn)即存在左子結(jié)點(diǎn)，如下圖刪除值為 25 的結(jié)點(diǎn)。
一種方案是：找到結(jié)點(diǎn) 25 的左子樹中的最大值，即結(jié)點(diǎn) 20（該結(jié)點(diǎn)的特點(diǎn)是可能會(huì)存在左子結(jié)點(diǎn)，但一定不會(huì)有右子結(jié)點(diǎn)）。用此結(jié)點(diǎn)替換結(jié)點(diǎn)25 便可。
為什么要這么做？
道理很簡(jiǎn)單，既然是左子樹中的最大值，替換刪除結(jié)點(diǎn)后，整個(gè)二叉排序樹的特性可以繼續(xù)保持。
如果結(jié)點(diǎn) 20 存在左子結(jié)點(diǎn)，則把它的左子結(jié)點(diǎn)作為結(jié)點(diǎn)18的右子結(jié)點(diǎn)。
另一種方案：同樣找到結(jié)點(diǎn)25中左子樹中的最大值結(jié)點(diǎn) 20，然后把結(jié)點(diǎn) 25 的右子樹作為結(jié)點(diǎn) 20 的右子樹。
再把結(jié)點(diǎn) 25 的左子樹移到 25 位置。
這種方案會(huì)讓樹增加樹的深度。所以，建議使用第一種方案。
刪除方法的實(shí)現(xiàn)：
'''
刪除結(jié)點(diǎn)
key 為要要?jiǎng)h除的結(jié)點(diǎn)
'''
def delete(self, key):
# 從根結(jié)點(diǎn)開始查找，move_node 為搜索指針
move_node = self.root
# 要?jiǎng)h除的結(jié)點(diǎn)的父結(jié)點(diǎn),因?yàn)楦Y(jié)點(diǎn)沒有父結(jié)點(diǎn)，初始值為 None
parent_node = None
# 結(jié)點(diǎn)存在且沒有匹配上要找的關(guān)鍵字
while move_node is not None and move_node.value != key:
# 保證當(dāng)前結(jié)點(diǎn)
parent_node = move_node
if move_node.value > key:
# 在左子樹中繼續(xù)查找
move_node = move_node.l_child
else:
# 在右子樹中繼續(xù)查找
move_node = move_node.r_child
# 如果不存在
if move_node is None:
return -1
# 檢查要?jiǎng)h除的結(jié)點(diǎn)是否存在左子結(jié)點(diǎn)
if move_node.l_child is None:
if parent_node is None:
# 如果要?jiǎng)h除的結(jié)點(diǎn)是根結(jié)點(diǎn)
self.root = move_node.r_child
elif parent_node.l_child == move_node:
# 刪除結(jié)點(diǎn)的右結(jié)點(diǎn)作為父結(jié)點(diǎn)的左結(jié)點(diǎn)
parent_node.l_child = move_node.r_child
elif parent_node.r_child == move_node:
parent_node.r_child = move_node.r_child
return 1
else:
# 如果刪除的結(jié)點(diǎn)存在左子結(jié)點(diǎn),則在左子樹中查找最大值
s = move_node.l_child
q = move_node
while s.r_child is not None:
q = s
s = s.r_child
if q == move_node:
move_node.l_child = s.l_child
else:
q.r_child = s.l_child
move_node.value = s.value
q.r_child = None
return 1測(cè)試刪除后的二叉樹是否依然維持其有序性。
if __name__ == "__main__":
nums = [5, 12, 4, 45, 32, 8, 10, 50, 32, 3]
tree = BinarySortTree(5)
# res = tree.find(51)
for i in range(1, len(nums)):
tree.insert(nums[i])
tree.delete(12)
tree.inorder_traversal(tree.root)
'''
輸出結(jié)果
3->4->5->8->10->32->45->50->
'''無(wú)論刪除哪一個(gè)結(jié)點(diǎn)，其二叉排序樹的中序遍歷結(jié)果都是有序的，很好地印證了刪除算法的正確性。
3. 平衡二叉排序樹
二叉排序樹中進(jìn)行查找時(shí)，其時(shí)間復(fù)雜度理論上接近二分算法的時(shí)間復(fù)雜度，其查找時(shí)間與樹的深度有關(guān)。但是，這里有一個(gè)問題，前面討論過，如果數(shù)列中的數(shù)字順序不一樣時(shí)，所構(gòu)建出來(lái)的二叉排序樹的深度會(huì)有差異性，對(duì)最后評(píng)估時(shí)間性能也會(huì)有影響。
如有數(shù)列 [36,45,67,28,20,40]構(gòu)建的二叉排序樹如下圖：
基于上面的樹結(jié)構(gòu)，查詢?nèi)魏我粋€(gè)結(jié)點(diǎn)的次數(shù)不會(huì)超過 3 次。
稍調(diào)整一下數(shù)列中數(shù)字的順序 [20,28,36,40,45,67]，由此構(gòu)建出來(lái)的樹結(jié)構(gòu)會(huì)出現(xiàn)一邊倒的現(xiàn)象，也增加了樹的深度。
此棵樹的深度為6，最多查詢次數(shù)是 6 次。在二叉排序樹中，減少查找次數(shù)的最好辦法，就是盡可能維護(hù)樹左右子樹之間的對(duì)稱性，也就讓其有平衡性。
所謂平衡二叉排序樹，顧名思義，基于二叉排序樹的基礎(chǔ)之上，維護(hù)任一結(jié)點(diǎn)的左子樹和右子樹之間的深度之差不超過 1。把二叉樹上任一結(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為該結(jié)點(diǎn)的平衡因子。
平衡因子只可能是:
0 ：左、右子樹深度一樣。 1：左子樹深度大于右子樹。 -1：左子樹深度小于右子樹。
如下圖，就是平衡二叉排序樹，根結(jié)點(diǎn)的 2 個(gè)子樹深度相差為 0， 結(jié)點(diǎn) 28 的左、右子樹深度為 1，結(jié)點(diǎn) 45 的左右子樹深度相差為 0。
平衡二叉排序樹相比較于二叉排序樹，其 API 多了保持平衡的算法。
3.1 二叉平衡排序樹的數(shù)據(jù)結(jié)構(gòu)
結(jié)點(diǎn)類：
'''
結(jié)點(diǎn)類
'''
class TreeNode:
def __init__(self,value):
self.value=value
self.l_child=None
self.r_child=None
self.balance=0結(jié)點(diǎn)類中有 4 個(gè)屬性：
value：結(jié)點(diǎn)上附加的值。 l_child：左子結(jié)點(diǎn)。 r_child：右子結(jié)點(diǎn)。 balance：平衡因子，默認(rèn)平衡因子為 0。
二叉平衡排序樹類：
'''
樹類
'''
class Tree:
def __init__(self, value):
self.root = None
'''
LL型調(diào)整
'''
def ll_rotate(self, node):
pass
'''
RR 型調(diào)整
'''
def rr_rotate(self, node):
pass
'''
LR型調(diào)整
'''
def lr_rotate(self, node):
pass
'''
RL型調(diào)整
'''
def rl_rotate(self, node):
pass
'''
插入新結(jié)點(diǎn)
'''
def insert(self, value):
pass
'''
中序遍歷
'''
def inorder_traversal(self, root):
pass
def is_empty(self):
pass在插入或刪除結(jié)點(diǎn)時(shí)，如果導(dǎo)致樹結(jié)構(gòu)發(fā)生了不平衡性，則需要調(diào)整讓其達(dá)到平衡。這里的方案可以有 4種。
LL型調(diào)整（順時(shí)針）：左邊不平衡時(shí)，向右邊旋轉(zhuǎn)。
如上圖，現(xiàn)在根結(jié)點(diǎn) 36 的平衡因子為 1。如果現(xiàn)插入值為 18 結(jié)點(diǎn)，顯然要作為結(jié)點(diǎn) 20 的左子結(jié)點(diǎn)，才符合二叉排序樹的有序性。但是破壞了根結(jié)點(diǎn)的平衡性。根結(jié)點(diǎn)的左子樹深度變成 3，右子樹深度為1，平衡被打破，結(jié)點(diǎn) 36 的平衡因子變成了2。
這里可以使用順時(shí)針旋轉(zhuǎn)方式，讓其繼續(xù)保持平衡，旋轉(zhuǎn)流程：
讓結(jié)點(diǎn) 28 成為新根結(jié)點(diǎn)，結(jié)點(diǎn)36成為結(jié)點(diǎn)28的左子結(jié)點(diǎn)。 結(jié)點(diǎn)29成為結(jié)點(diǎn)36的新左子結(jié)點(diǎn)。
旋轉(zhuǎn)后，樹結(jié)構(gòu)即滿足了有序性，也滿足了平衡性。
LL 旋轉(zhuǎn)算法具體實(shí)現(xiàn)：
'''
LL型調(diào)整
順時(shí)針對(duì)調(diào)整
'''
def ll_rotate(self, p_root):
# 原父結(jié)點(diǎn)的左子結(jié)點(diǎn)成為新父結(jié)點(diǎn)
new_p_root = p_root.l_child
# 新父結(jié)點(diǎn)的右子結(jié)點(diǎn)成為原父結(jié)點(diǎn)的左子結(jié)點(diǎn)
p_root.l_child = new_p_root.r_child
# 原父結(jié)點(diǎn)成為新父結(jié)點(diǎn)的右子結(jié)點(diǎn)
new_p_root.r_child = p_root
# 重置平衡因子
p_root.balance = 0
new_p_root.balance = 0
return new_p_rootRR 型調(diào)整(逆時(shí)針旋轉(zhuǎn))：RR旋轉(zhuǎn)和 LL旋轉(zhuǎn)的算法差不多，只是當(dāng)右邊不平衡時(shí)，向左邊旋轉(zhuǎn)。
如下圖所示，結(jié)點(diǎn) 50 插入后，樹的平衡性被打破。
這里使用左旋轉(zhuǎn)（逆時(shí)針）方案。結(jié)點(diǎn) 36 成為結(jié)點(diǎn) 45 的左子結(jié)點(diǎn)，結(jié)點(diǎn)45 原來(lái)的左子結(jié)點(diǎn)成為結(jié)點(diǎn)36的右子結(jié)點(diǎn)。
向逆時(shí)針旋轉(zhuǎn)后，結(jié)點(diǎn)45的平衡因子為 0，結(jié)點(diǎn)36的平衡因子為0，結(jié)點(diǎn) 48 的平衡因子為 -1。樹的有序性和平衡性得到保持。
RR 旋轉(zhuǎn)算法具體實(shí)現(xiàn)：
'''
RR 型調(diào)整
'''
def rr_rotate(self, node):
# 右子結(jié)點(diǎn)
new_p_node = p_node.r_child
p_node.r_child = new_p_node.l_child
new_p_node.l_child = p_node
# 重置平衡因子
p_node.balance = 0
new_p_node.balance = 0
return new_p_node**LR型調(diào)整（先逆后順）：**如下圖當(dāng)插入結(jié)點(diǎn) 28 后，結(jié)點(diǎn) 36 的平衡因子變成 2，則可以使用 LR 旋轉(zhuǎn)算法。
以結(jié)點(diǎn) 29 作為新的根結(jié)點(diǎn)，結(jié)點(diǎn)27以結(jié)點(diǎn)29為旋轉(zhuǎn)中心，逆時(shí)針旋轉(zhuǎn)。
結(jié)點(diǎn)36以結(jié)點(diǎn)29為旋轉(zhuǎn)中心向順時(shí)針旋轉(zhuǎn)。
最后得到的樹還是一棵二叉平衡排序樹。
LR 旋轉(zhuǎn)算法實(shí)現(xiàn)：
'''
LR型調(diào)整
'''
def lr_rotate(self, p_node):
# 左子結(jié)點(diǎn)
b = p_node.l_child
new_p_node = b.r_child
p_node.l_child = new_p_node.r_child
b.r_child = new_p_node.l_child
new_p_node.l_child = b
new_p_node.r_child = p_node
if new_p_node.balance == 1:
p_node.balance = -1
b.balance = 0
elif new_p_node.balance == -1:
p_node.balance = 0
b.balance = 1
else:
p_node.balance = 0
b.balance = 0
new_p_node.balance = 0
return new_p_nodeRL型調(diào)整： 如下圖插入結(jié)點(diǎn)39 后，整棵樹的平衡打破，這時(shí)可以使用 RL 旋轉(zhuǎn)算法進(jìn)行調(diào)整。
把結(jié)點(diǎn)40設(shè)置為新的根結(jié)點(diǎn)，結(jié)點(diǎn)45以結(jié)點(diǎn) 40 為中心點(diǎn)順時(shí)針旋轉(zhuǎn)，結(jié)點(diǎn)36逆時(shí)針旋轉(zhuǎn)。
RL 算法具體實(shí)現(xiàn)：
'''
RL型調(diào)整
'''
def rl_rotate(self, p_node):
b = p_node.r_child
new_p_node = b.l_child
p_node.r_child = new_p_node.l_child
b.l_child = new_p_node.r_child
new_p_node.l_child = p_node
new_p_node.r_child = b
if new_p_node.balance == 1:
p_node.balance = 0
b.balance = -1
elif new_p_node.balance == -1:
p_node.balance = 1
b.balance = 0
else:
p_node.balance = 0
b.balance = 0
new_p_node.balance = 0
return new_p_node編寫完上述算法后，就可以編寫插入算法。在插入新結(jié)點(diǎn)時(shí)，檢查是否破壞二叉平衡排序樹的的平衡性，否則調(diào)用平衡算法。
當(dāng)插入一個(gè)結(jié)點(diǎn)后，為了保持平衡，需要找到最小不平衡子樹。
什么是最小不平衡子樹？
指離插入結(jié)點(diǎn)最近，且平衡因子絕對(duì)值大于 1 的結(jié)點(diǎn)為根結(jié)點(diǎn)構(gòu)成的子樹。
'''
插入新結(jié)點(diǎn)
'''
def insert(self, val):
# 新的結(jié)點(diǎn)
new_node = TreeNode(val)
if self.root is None:
# 空樹
self.root = new_node
return
# 記錄離 s 最近的平衡因子不為 0 的結(jié)點(diǎn)。
min_b = self.root
# f 指向 a 的父結(jié)點(diǎn)
f_node = None
move_node = self.root
f_move_node = None
while move_node is not None:
if move_node.value == new_node.value:
# 結(jié)點(diǎn)已經(jīng)存在
return
if move_node.balance != 0:
# 尋找最小不平衡子樹
min_b = move_node
f_node = f_move_node
f_move_node = move_node
if new_node.value < move_node.value:
move_node = move_node.l_child
else:
move_node = move_node.r_child
if new_node.value < f_move_node.value:
f_move_node.l_child = new_node
else:
f_move_node.r_child = new_node
move_node = min_b
# 修改相關(guān)結(jié)點(diǎn)的平衡因子
while move_node != new_node:
if new_node.value < move_node.value:
move_node.balance += 1
move_node = move_node.l_child
else:
move_node.balance -= 1
move_node = move_node.r_child
if min_b.balance > -2 and min_b.balance < 2:
# 插入結(jié)點(diǎn)后沒有破壞平衡性
return
if min_b.balance == 2:
b = min_b.l_child
if b.balance == 1:
move_node = self.ll_rotate(min_b)
else:
move_node = self.lr_rotate(min_b)
else:
b = min_b.r_child
if b.balance == 1:
move_node = self.rl_rotate(min_b)
else:
move_node = self.rr_rotate(min_b)
if f_node is None:
self.root = move_node
elif f_node.l_child == min_b:
f_node.l_child = move_node
else:
f_node.r_child = move_node中序遍歷： 此方法為了驗(yàn)證樹結(jié)構(gòu)還是排序的。
'''
中序遍歷
'''
def inorder_traversal(self, root):
if root is None:
return
self.inorder_traversal(root.l_child)
print(root.value, end="->")
self.inorder_traversal(root.r_child)二叉平衡排序樹本質(zhì)還是二樹排序樹。如果使用中序遍歷輸出的數(shù)字是有序的。測(cè)試代碼。
if __name__ == "__main__":
nums = [3, 12, 8, 10, 9, 1, 7]
tree = Tree(3)
for i in range(1, len(nums)):
tree.inster(nums[i])
# 中序遍歷
tree.inorder_traversal(tree.root)
'''
輸出結(jié)果
1->3->7->8->9->10->12->
'''4. 總結(jié)
利用二叉排序樹的特性，可以實(shí)現(xiàn)動(dòng)態(tài)查找。在添加、刪除結(jié)點(diǎn)之后，理論上查找到某一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度與樹的結(jié)點(diǎn)在樹中的深度是相同的。
但是，在構(gòu)建二叉排序樹時(shí)，因原始數(shù)列中數(shù)字順序的不同，則會(huì)影響二叉排序樹的深度。
這里引用二叉平衡排序樹，用來(lái)保持樹的整體結(jié)構(gòu)是平衡，方能保證查詢的時(shí)間復(fù)雜度為 Ologn(n 為結(jié)點(diǎn)的數(shù)量)。
到此這篇關(guān)于Python 樹表查找（二叉排序樹、平衡二叉樹）的文章就介紹到這了,更多相關(guān)Python 樹表查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Django 實(shí)現(xiàn)對(duì)已存在的model進(jìn)行更改
這篇文章主要介紹了Django 實(shí)現(xiàn)對(duì)已存在的model進(jìn)行更改，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧2020-03-03
python調(diào)用java的Webservice示例
這篇文章主要介紹了python調(diào)用java的Webservice具體方法,包含java端和python實(shí)現(xiàn)代碼,需要的朋友可以參考下2014-03-03
Python利用reportlab實(shí)現(xiàn)制作pdf報(bào)告
這篇文章主要為大家詳細(xì)介紹了reportlab生成流文件格式、reportlab分頁(yè)和圖片流文件寫入reportlab等內(nèi)容，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-12-12
今天小編就為大家分享一篇關(guān)于Python生成器的使用方法和示例代碼，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-03-03
這篇文章主要介紹了Python自動(dòng)連接ssh的方法,實(shí)例分析了基于Python實(shí)現(xiàn)連接ssh的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)Floyd算法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
Python根據(jù)區(qū)號(hào)生成手機(jī)號(hào)碼的方法
這篇文章主要介紹了Python根據(jù)區(qū)號(hào)生成手機(jī)號(hào)碼的方法,涉及Python隨機(jī)數(shù)與字符串的相關(guān)操作技巧,需要的朋友可以參考下2015-07-07
使用Python進(jìn)行同期群分析(Cohort?Analysis)
同期群(Cohort)的字面意思(有共同特點(diǎn)或舉止類同的)一群人，比如不同性別，不同年齡。這篇文章主要介紹了用Python語(yǔ)言來(lái)進(jìn)行同期群分析，感興趣的同學(xué)可以閱讀參考一下本文2023-03-03
Python實(shí)現(xiàn)的序列化和反序列化二叉樹算法示例
這篇文章主要介紹了Python實(shí)現(xiàn)的序列化和反序列化二叉樹算法,結(jié)合實(shí)例形式分析了Python二叉樹的構(gòu)造、遍歷、序列化、反序列化等相關(guān)操作技巧,需要的朋友可以參考下2019-03-03
Python中的單下劃線和雙下劃線使用場(chǎng)景詳解
這篇文章主要介紹了Python中的單下劃線和雙下劃線使用場(chǎng)景詳解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09