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