什么是二叉查找樹腾务？
二叉查找樹又名二叉排序樹捂龄、二叉搜索樹揩慕，具有如下性質(zhì)：
- 若左子樹不為空漆诽，則左子樹上的所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)上的值
- 若右子樹不為空侮攀，則右子樹上的所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)上的值
- 左、右子樹也分別都為二叉查找樹
- 沒有鍵值相等的兩個(gè)節(jié)點(diǎn)
二叉查找樹的優(yōu)缺點(diǎn)
1. 查找性能
查找過程：從根節(jié)點(diǎn)出發(fā)厢拭，若根節(jié)點(diǎn)的關(guān)鍵字等于要查找的值兰英，則查找完成；如果小于根節(jié)點(diǎn)的值供鸠，則遞歸查找左子樹畦贸；否則遞歸查找右子樹。如果到葉子節(jié)點(diǎn)楞捂，還沒有查找到家制，則說明這個(gè)樹中沒有這個(gè)值。
- 當(dāng)二叉樹中每個(gè)節(jié)點(diǎn)左右子樹的高度大致相同泡一，則樹的高度為logN颤殴。則平均時(shí)間復(fù)雜度也就為O(logN)
- 當(dāng)二叉樹插入節(jié)點(diǎn)時(shí)，關(guān)鍵字本來就有序鼻忠，二叉樹就會(huì)形成一個(gè)單支樹結(jié)構(gòu)涵但，查找也就變得和順序查找一模一樣了杈绸。這時(shí)的查找效率最低為0(n)
2. 插入性能
因?yàn)樾鹿?jié)點(diǎn)插入到樹中的葉子節(jié)點(diǎn)上的，所以插入一個(gè)節(jié)點(diǎn)和查找一個(gè)不存在的值的代價(jià)是一樣的矮瘟。
3. 刪除性能
首先找到這個(gè)要?jiǎng)h除的節(jié)點(diǎn)p瞳脓，代價(jià)和查找這個(gè)值一樣。然后需要改變樹的結(jié)構(gòu)澈侠。如果左右子樹都為空弄痹，則直接刪除這個(gè)葉子節(jié)點(diǎn)灸撰；
1.png
如果這個(gè)刪除節(jié)點(diǎn)的左右子樹只存在一個(gè)槽地，那么直接把左節(jié)點(diǎn)或右節(jié)點(diǎn)的父親設(shè)置為p的父親即可斟珊；
2.png
如果左右子樹都存在，則把右子樹中值最小的節(jié)點(diǎn)找到拳球，交換到要?jiǎng)h除節(jié)點(diǎn)的位置审姓，然后調(diào)整下子樹即可。
3.png
python實(shí)現(xiàn)二叉查找樹
#!/usr/bin/python
# encoding: utf-8
class BinarySearchTree(object):
# 每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)祝峻，left和right的值代表左右子節(jié)點(diǎn)魔吐，value為當(dāng)前節(jié)點(diǎn)關(guān)鍵字的值
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# 插入一個(gè)節(jié)點(diǎn)
def insert(self, x):
if x < self.value:
if self.left:
self.left.insert(x)
else:
self.left = BinarySearchTree(x)
elif x > self.value:
if self.right:
self.right.insert(x)
else:
self.right = BinarySearchTree(x)
# 遍歷二叉樹查找一個(gè)值
def find(self, x, parent=None):
if x == self.value:
return self, parent
elif x < self.value and self.left:
return self.left.find(x, self)
elif x > self.value and self.right:
return self.right.find(x, self)
else:
return None, None
# 關(guān)鍵值最小的節(jié)點(diǎn)
def findMin(self):
if self.left:
return self.left.findMin()
else:
return self
# 關(guān)鍵值最大的節(jié)點(diǎn)
def findMax(self):
if self.right:
return self.right.findMax()
else:
return self
# 刪除一個(gè)節(jié)點(diǎn)
def delete(self, x):
node, parent = self.find(x);
# 如果有這個(gè)值才進(jìn)行刪除操作
if node is not None:
# 如果該節(jié)點(diǎn)下沒有子節(jié)點(diǎn)
if not node.left and not node.right:
if parent.left is node:
parent.left = None
else:
parent.right = None
del node
# 只有一個(gè)子節(jié)點(diǎn)時(shí)，則讓這個(gè)子節(jié)點(diǎn)替換這個(gè)要?jiǎng)h除的節(jié)點(diǎn)
elif (not node.left and node.right) or (node.left and not node.right):
if node.left:
n = node.left
else:
n = node.right
if parent:
if parent.left is node:
parent.left = n
else:
parent.right = n
del node
# 刪除節(jié)點(diǎn)有左子節(jié)點(diǎn)莱找，也有右子節(jié)點(diǎn)酬姆。
else:
parent = node
successor = node.right
while successor.left:
parent = successor
successor = successor.left
# 找到右子樹中最小的值后賦值給要?jiǎng)h除的節(jié)點(diǎn)
node.value = successor.value
# 左右子樹微調(diào)
if parent.left == successor:
parent.left = successor.right
else:
parent.right = successor.right
del successor
# 按照順序打印
def printTree(self):
if self.left:
self.left.printTree()
print self.value,
if self.right:
self.right.printTree()
if __name__ == '__main__':
root = BinarySearchTree(10)
root.insert(6)
root.insert(5)
root.insert(8)
root.insert(7)
root.insert(9)
root.printTree()
print '' # 另起一行
x, y = root.find(9)
print x.value, y.value # 打印查explorer.exe找的值和其父親的值
print root.findMax().value, root.findMin().value # 打印最小值和最大值
root.delete(5)
root.printTree()
執(zhí)行結(jié)果
5 6 7 8 9 10
9 8
10 5
6 7 8 9 10
