二分法猜數(shù)字的游戲應(yīng)該每個人都知道在讶，通過對猜測數(shù)字“大了”、“小了”的情況判斷狼钮，來猜出最終的數(shù)字碳柱。序列范圍為
的集合，復雜度為
燃领，即最多需要
次可以猜到最終數(shù)字士聪。
引子
二分法的查找過程是，在一個有序的序列中猛蔽，每次都會選擇有效范圍中間位置的元素作判斷剥悟，即每次判斷后，都可以排除近一半的元素曼库，直到查找到目標元素或返回不存在区岗，所以 個有序元素構(gòu)成的序列，查找的時間復雜度為
毁枯。既然線性結(jié)構(gòu)能夠做到查詢復雜度為
級別慈缔，那二叉搜索樹產(chǎn)生又有何必要呢？畢竟二叉搜索樹的查詢復雜度只是介于
~
之間种玛，并不存在查詢優(yōu)勢藐鹤。
定義
二叉搜索樹是一種節(jié)點值之間具有一定數(shù)量級次序的二叉樹，對于樹中每個節(jié)點：
- 若其左子樹存在赂韵，則其左子樹中每個節(jié)點的值都不大于該節(jié)點值娱节；
- 若其右子樹存在，則其右子樹中每個節(jié)點的值都不小于該節(jié)點值祭示。
示例：
查詢復雜度
觀察二叉搜索樹結(jié)構(gòu)可知肄满，查詢每個節(jié)點需要的比較次數(shù)為節(jié)點深度加一。如深度為 0，節(jié)點值為 “6” 的根節(jié)點稠歉，只需要一次比較即可掰担；深度為 1，節(jié)點值為 “3” 的節(jié)點怒炸，只需要兩次比較带饱。即二叉樹節(jié)點個數(shù)確定的情況下，整顆樹的高度越低横媚，節(jié)點的查詢復雜度越低纠炮。
二叉搜索樹的兩種極端情況：
【1】 完全二叉樹，所有節(jié)點盡量填滿樹的每一層灯蝴，上一層填滿后還有剩余節(jié)點的話，則由左向右盡量填滿下一層孝宗。如上圖BST所示穷躁，即為一顆完全二叉樹；
【2】每一層只有一個節(jié)點的二叉樹因妇。如下圖SP_BST所示：
第【1】種情況下的查找次數(shù)分析：由上一章 二叉樹 可知问潭，完美二叉樹中樹的深度與節(jié)點個數(shù)的關(guān)系為：。設(shè)深度為
的完全二叉樹節(jié)點總數(shù)為
婚被，因為完全二叉樹中深度為
的葉子節(jié)點層不一定填滿狡忙，所以有
，即：
址芯，因為
為查找次數(shù)灾茁，所以完全二叉樹中查找次數(shù)為：
。
第【2】種情況下谷炸，樹中每層只有一個節(jié)點北专，該狀態(tài)的樹結(jié)構(gòu)更傾向于一種線性結(jié)構(gòu)，節(jié)點的查詢類似于數(shù)組的遍歷旬陡，查詢復雜度為 拓颓。
所以二叉搜索樹的查詢復雜度為 ~
。
構(gòu)造復雜度
二叉搜索樹的構(gòu)造過程描孟，也就是將節(jié)點不斷插入到樹中適當位置的過程驶睦。該操作過程，與查詢節(jié)點元素的操作基本相同匿醒，不同之處在于：
- 查詢節(jié)點過程是场航，比較元素值是否相等，相等則返回青抛，不相等則判斷大小情況旗闽，迭代查詢左、右子樹，直到找到相等的元素适室，或子節(jié)點為空嫡意，返回節(jié)點不存在
- 插入節(jié)點的過程是，比較元素值是否相等捣辆，相等則返回蔬螟，表示已存在，不相等則判斷大小情況汽畴，迭代查詢左旧巾、右子樹，直到找到相等的元素忍些，或子節(jié)點為空鲁猩，則將節(jié)點插入該空節(jié)點位置。
由此可知罢坝，單個節(jié)點的構(gòu)造復雜度和查詢復雜度相同廓握，為 ~
。
刪除復雜度
二叉搜索樹的節(jié)點刪除包括兩個過程嘁酿，查找和刪除隙券。查詢的過程和查詢復雜度已知，這里說明一下刪除節(jié)點的過程闹司。
節(jié)點的刪除有以下三種情況：
- 待刪除節(jié)點度為零娱仔；
- 待刪除節(jié)點度為一；
- 待刪除節(jié)點度為二游桩。
第一種情況如下圖 s_1 所示牲迫，待刪除節(jié)點值為 “6”，該節(jié)點無子樹众弓，刪除后并不影響二叉搜索樹的結(jié)構(gòu)特性恩溅，可以直接刪除。即二叉搜索樹中待刪除節(jié)點度為零時谓娃，該節(jié)點為葉子節(jié)點脚乡，可以直接刪除；
第二種情況如下圖 s_2 所示滨达，待刪除節(jié)點值為 “7”奶稠，該節(jié)點有一個左子樹，刪除節(jié)點后捡遍，為了維持二叉搜索樹結(jié)構(gòu)特性锌订，需要將左子樹“上移”到刪除的節(jié)點位置上。即二叉搜索樹中待刪除的節(jié)點度為一時画株，可以將待刪除節(jié)點的左子樹或右子樹“上移”到刪除節(jié)點位置上辆飘，以此來滿足二叉搜索樹的結(jié)構(gòu)特性啦辐。
第三種情況如下圖 s_3 所示，待刪除節(jié)點值為 “9”蜈项，該節(jié)點既有左子樹芹关，也有右子樹，刪除節(jié)點后紧卒，為了維持二叉搜索樹的結(jié)構(gòu)特性侥衬，需要從其左子樹中選出一個最大值的節(jié)點，“上移”到刪除的節(jié)點位置上跑芳。即二叉搜索樹中待刪除節(jié)點的度為二時轴总，可以將待刪除節(jié)點的左子樹中的最大值節(jié)點“移動”到刪除節(jié)點位置上，以此來滿足二叉搜索樹的結(jié)構(gòu)特性博个。
其實在真實的實現(xiàn)代碼中怀樟，該情況下的實際節(jié)點刪除操作是：
1.查找出左子樹中的最大值節(jié)點
2.替換待刪除節(jié)點的值為
的值
3.刪除
因為
之前提到二叉搜索樹中節(jié)點的刪除操作，包括查詢和刪除兩個過程罪塔，這里稱刪除節(jié)點后，維持二叉搜索樹結(jié)構(gòu)特性的操作為“穩(wěn)定結(jié)構(gòu)”操作养葵，觀察以上三種情況可知：
- 前兩種情況下征堪，刪除節(jié)點后，“穩(wěn)定結(jié)構(gòu)”操作的復雜度都是常數(shù)級別关拒，即整個的節(jié)點刪除操作復雜度為
佃蚜；
- 第三種情況下，設(shè)刪除的節(jié)點為
着绊，“穩(wěn)定結(jié)構(gòu)”操作需要查找
性能分析
由以上查詢復雜度剧包、構(gòu)造復雜度和刪除復雜度的分析可知恐锦，三種操作的時間復雜度皆為 ~
。下面分析線性結(jié)構(gòu)的三種操作復雜度疆液，以二分法為例：
- 查詢復雜度一铅，時間復雜度為
- 元素的插入操作包括兩個步驟潘飘，查詢和插入肮之。查詢的復雜度已知，插入后調(diào)整元素位置的復雜度為
- 刪除操作也包括兩個步驟戈擒，查詢和刪除，查詢的復雜度已知暴凑，刪除后調(diào)整元素位置的復雜度為
由此可知，二叉搜索樹相對于線性結(jié)構(gòu)现喳，在構(gòu)造復雜度和刪除復雜度方面占優(yōu)凯傲；在查詢復雜度方面，二叉搜索樹可能存在類似于斜樹嗦篱，每層上只有一個節(jié)點的情況冰单，該情況下查詢復雜度不占優(yōu)勢。
總結(jié)
二叉搜索樹的節(jié)點查詢灸促、構(gòu)造和刪除性能诫欠，與樹的高度相關(guān)，如果二叉搜索樹能夠更“平衡”一些浴栽，避免了樹結(jié)構(gòu)向線性結(jié)構(gòu)的傾斜荒叼，則能夠顯著降低時間復雜度。二叉搜索樹的存儲方面典鸡，相對于線性結(jié)構(gòu)只需要保存元素值被廓，樹中節(jié)點需要額外的空間保存節(jié)點之間的父子關(guān)系，所以在存儲消耗上要高于線性結(jié)構(gòu)萝玷。
代碼附錄
python版本：3.7嫁乘，樹中的遍歷、節(jié)點插入和刪除操作使用的是遞歸形式
- 樹節(jié)點定義
# tree node definition
class Node(object):
def __init__(self, value, lchild=None, rchild=None):
self.value = value
self.lchild = lchild
self.rchild = rchild
- 樹定義
# 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)中的函數(shù)進行實現(xiàn)
# node in-order traversal(LDR)
def traversal(node):
if not node:
return
traversal(node.lchild)
print(node.value,end=' ')
traversal(node.rchild)
# insert node
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 root
# delete node
def delete(root, value):
if not root:
return None
if value < root.value:
root.lchild = delete(root.lchild, value)
elif value > root.value:
root.rchild = delete(root.rchild, value)
else:
if root.lchild and root.rchild: # degree of the node is 2
target = root.lchild # find the maximum node of the left subtree
while target.rchild:
target = target.rchild
root = delete(root, target.value)
root.value = target.value
else: # degree of the node is [0|1]
root = root.lchild if root.lchild else root.rchild
return root
- 測試代碼與輸出
if __name__ == '__main__':
arr = [5, 3, 4, 0, 2, 1, 8, 6, 9, 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 1 2 3 4 5 6 7 8 9
delete test------------------
after delete 7,BST in-order is = 0 1 2 3 4 5 6 8 9
after delete 9,BST in-order is = 0 1 2 3 4 5 6 8
after delete 6,BST in-order is = 0 1 2 3 4 5 8
after delete 8,BST in-order is = 0 1 2 3 4 5
after delete 1,BST in-order is = 0 2 3 4 5
after delete 2,BST in-order is = 0 3 4 5
after delete 0,BST in-order is = 3 4 5
after delete 4,BST in-order is = 3 5
after delete 3,BST in-order is = 5
after delete 5,BST in-order is =
github鏈接：二叉搜索樹
