方法介紹：
通過(guò)二叉查找樹(shù)保存Key湖笨，實(shí)現(xiàn)快速查找
還有散列表法（散列及解決沖突）舀寓，與有序表法（二分查找）
BST定義：
左子樹(shù)節(jié)點(diǎn)key比根節(jié)點(diǎn)來(lái)的小，右子樹(shù)節(jié)點(diǎn)key比根節(jié)點(diǎn)大杜秸。
image.png
可以看出外永，根據(jù)插入值的順序，生成的BST樹(shù)也不一樣匙铡。不是完全有序图甜。
BST方法介紹：
- put、get方法：
插入BST中鳖眼，創(chuàng)建新節(jié)點(diǎn)黑毅。
沒(méi)啥可說(shuō)的，注意遞歸具帮，遞歸結(jié)束條件為找到合適的位置博肋，put創(chuàng)建樹(shù)節(jié)點(diǎn)加入到子節(jié)點(diǎn)中去低斋；get方法將找到的節(jié)點(diǎn)return。 -
delete方法：
移除當(dāng)前BST的某個(gè)節(jié)點(diǎn)匪凡。
①先通過(guò)get方法去找key膊畴，找到需要?jiǎng)h除的節(jié)點(diǎn)。
②判斷節(jié)點(diǎn)是否為葉節(jié)點(diǎn)病游，若為葉節(jié)點(diǎn)唇跨，直接刪除（令葉節(jié)點(diǎn)為None）
③若有左右子節(jié)點(diǎn)，則去找后繼節(jié)點(diǎn)
后繼節(jié)點(diǎn)法：通過(guò)看刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)中最小的那個(gè)節(jié)點(diǎn)（取最靠近待刪除節(jié)點(diǎn)的值取代刪除的節(jié)點(diǎn)值衬衬。）找到后繼節(jié)點(diǎn)后买猖，拆除待刪除節(jié)點(diǎn)并放入后繼節(jié)點(diǎn)
拆除方法：若后繼節(jié)點(diǎn)為葉節(jié)點(diǎn)直接摘除；如果不是滋尉，由于后繼節(jié)點(diǎn)肯定是左節(jié)點(diǎn)玉控，且肯定只有右子節(jié)點(diǎn)，將后繼節(jié)點(diǎn)的右節(jié)點(diǎn)放在后繼節(jié)點(diǎn)父節(jié)點(diǎn)的左節(jié)點(diǎn)狮惜。
image.png
④如果只有左節(jié)點(diǎn)或者右節(jié)點(diǎn)
一高诺、 如果被刪除的節(jié)點(diǎn)有左子節(jié)點(diǎn)：若被刪除的節(jié)點(diǎn)是左子節(jié)點(diǎn)，則刪除碾篡；右子也是一樣虱而；如果被刪除的節(jié)點(diǎn)是根節(jié)點(diǎn)，則直接去他的左子節(jié)點(diǎn)替換开泽。
二牡拇、 如果被刪除的節(jié)點(diǎn)有右子節(jié)點(diǎn)：同上
算法分析：
查找算法復(fù)雜度：如果隨機(jī)分布，則兩邊平均分布key值大致相等
put方法的復(fù)雜度為O(log2n)
AVL樹(shù)概念：
AVL樹(shù)的定義（平衡二叉查找樹(shù)）：
對(duì)每個(gè)節(jié)點(diǎn)引入平衡因子參數(shù)
平衡因子：左右子樹(shù)的高度差穆律。
AVL樹(shù)平衡因子為0惠呼，-1，1
AVL樹(shù)搜索的時(shí)間復(fù)雜度：O(logn)
image.png
AVL樹(shù)方法：
- 新key以葉節(jié)點(diǎn)插入BST
- 重新平衡众旗，并修改父節(jié)點(diǎn)的平衡因子（左重或者右重罢杉，進(jìn)行旋轉(zhuǎn)重新平衡AVL樹(shù)）趟畏，
直到兩種情況：①根節(jié)點(diǎn)②父節(jié)點(diǎn)的平衡因子被調(diào)整為0
旋轉(zhuǎn)方法如下：
1.左重贡歧，右旋
2.右重，左轉(zhuǎn)赋秀，如果右子節(jié)點(diǎn)不存在左重利朵，
則如下圖，把右子節(jié)點(diǎn)B變?yōu)楦?jié)點(diǎn)猎莲，將A作為B的左子節(jié)點(diǎn)绍弟，若原B有左子節(jié)點(diǎn)，則把該節(jié)點(diǎn)掛在A的右子節(jié)點(diǎn)處著洼。
更新父節(jié)點(diǎn)引用樟遣，并更新平衡因子
image.png
image.png
如果右子節(jié)點(diǎn)存在左重
則先進(jìn)行右旋而叼，在實(shí)施左旋
image.png
右旋的代碼類似左旋
總體代碼如下：
# BST樹(shù)的構(gòu)建
class BinarySearchTree:
def __init__(self):
# 引用根節(jié)點(diǎn)TreeNode類
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
# 迭代器 實(shí)現(xiàn) for key in tree
def __iter__(self):
return self.root.__iter__()
# 插入key，構(gòu)造BST
def put(self, key, val):
if self.root:
self._put(key, val, self.root)
else:
self.root = TreeNode(key, val)
self.size += 1
def _put(self, key, val, currentNode):
if key < currentNode.key:
if currentNode.hasleftchild():
self._put(key, val, currentNode.leftchild)
else:
currentNode.leftchild = TreeNode(key, val, parent=currentNode)
else:
if currentNode.hasrightchild():
self._put(key, val, currentNode.rightchild)
else:
currentNode.rightchild = TreeNode(key, val, parent=currentNode)
# 索引賦值：實(shí)現(xiàn) mytree[key] = value
def __setitem__(self, key, value):
self.put(key, value)
# 在二叉樹(shù)中找到key所在的節(jié)點(diǎn)并取值
def get(self, key):
if self.root:
res = self._get(key, self.root)
if res:
return res.payload
else:
return None
else:
return None
def _get(self, key, currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key, currentNode.leftchild)
else:
return self._get(key, currentNode.rightchild)
# AVL樹(shù)的方法：
'''def _put(self, key, val, currentNode):
if key < currentNode.key:
if currentNode.hasleftchild():
return self._put(key, val, currentNode.leftchild)
else:
currentNode.leftchild = TreeNode(key, val, parent=currentNode)
# 更新平衡因子
self.updateBalance(currentNode.leftchild)
else:
if currentNode.hasrightchild():
return self._put(key, val, currentNode.rightchild)
else:
currentNode.rightchild = TreeNode(key, val, parent=currentNode)
self.updateBalance(currentNode.rightchild)
def updateBalance(self, node):
# 若節(jié)點(diǎn)不平衡豹悬，需要調(diào)整（旋轉(zhuǎn)）
if node.balancefactor > 1 or node.balancefactor < -1:
self.rebalance(node)
return
# 如果在-1至1之間葵陵，平衡，看是否有父節(jié)點(diǎn)瞻佛，如果有脱篙，調(diào)整父節(jié)點(diǎn)
if node.parent is not None:
if node.isleftchild():
node.parent.balancefactor += 1
elif node.isrightchild():
node.parent.balancefactor -= 1
# 調(diào)整以后的父節(jié)點(diǎn)平衡因子不為0，則再調(diào)整父節(jié)點(diǎn)的父節(jié)點(diǎn)平衡因子
if node.parent.balancefactor != 0:
self.updateBalance(node.parent)
# 左旋的方法
def rotateLeft(self, rotRoot):
newRoot = rotRoot.rightchild
rotRoot.rightchild = newRoot.leftchild
if newRoot.leftchild is not None:
newRoot.leftchild.parent = rotRoot
newRoot.parent = rotRoot.parent
if rotRoot.isroot():
self.root = newRoot
else:
if rotRoot.isleftchild():
rotRoot.parent.leftchild = newRoot
else:
rotRoot.parent.rightchild = newRoot
newRoot.leftchild = rotRoot
rotRoot.parent = newRoot
rotRoot.balancefactor = rotRoot.balancefactor + 1 - min(newRoot.balancefactor, 0)
rotRoot.balancefactor = newRoot.balancefactor + 1 + max(rotRoot.balancefactor, 0)
def rebalance(self, node):
# 節(jié)點(diǎn)是不是左重
if node.balancefactor < 0:
# 左重的子節(jié)點(diǎn)是不是右重
if node.rightchild.balancefactor > 0:
self.rotateRight(node.rightchild)
self.rotateLeft(node)
else:
self.rotateLeft(node)
elif node.balancefactor > 0:
if node.leftchild.balancefactor < 0:
self.rotateLeft(node.leftchild)
self.rotateRight(node)
else:
self.rotateRight(node)'''
# 索引取值 實(shí)現(xiàn) value = mytree[key]
def __getitem__(self, key):
return self.get(key)
# 尋找索引 實(shí)現(xiàn) key in mytree
def __contains__(self, key):
if self._get(key, self.root):
return True
else:
return False
# 迭代器實(shí)現(xiàn) 實(shí)現(xiàn) for key in tree
def __iter__(self):
if self:
if self.hasleftchild():
for elem in self.leftchild:
yield elem
yield self.key
if self.hasrightchild():
for elem in self.rightchild:
yield elem
# 刪除方法
def delete(self, key):
if self.size > 1:
node_to_remove = self._get(key, self.root)
if node_to_remove:
self.remove(node_to_remove)
self.size -= 1
else:
raise KeyError('error, key not in tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size -= 1
else:
raise KeyError('error, key not in tree')
# 實(shí)現(xiàn)方法 del tree(key)
def __delitem__(self, key):
self.delete(key)
def remove(self, currentNode):
# 判斷節(jié)點(diǎn)是否為葉節(jié)點(diǎn)伤柄，若為葉節(jié)點(diǎn)绊困，直接刪除（令葉節(jié)點(diǎn)為None）
if currentNode.isleaf():
if currentNode == currentNode.parent.leftchild():
currentNode.parentchild.leftchild = None
else:
currentNode.parentchild.rightchild = None
else:
if currentNode.hasbothchildren():
# 后繼節(jié)點(diǎn)法：通過(guò)看刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)中最小的那個(gè)節(jié)點(diǎn)（取最靠近待刪除節(jié)點(diǎn)的值取代刪除的節(jié)點(diǎn)值。）找到后繼節(jié)點(diǎn)后适刀，拆除待刪除節(jié)點(diǎn)并放入后繼節(jié)點(diǎn)
succ = currentNode.findsuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.payload = succ.payload
elif currentNode.hasleftchild():
# 如果被刪除的節(jié)點(diǎn)有左子節(jié)點(diǎn)
if currentNode.isleftchild():
currentNode.leftchild.parent = currentNode.parent
currentNode.parent.leftchild = currentNode.leftchild
elif currentNode.isrightchild():
currentNode.leftchild.parent = currentNode.parent
currentNode.parent.rightchild = currentNode.leftchild
else:
currentNode.replacenodedata(currentNode.leftchild.key,
currentNode.leftchild.payload,
currentNode.leftchild.leftchild,
currentNode.leftchild.rightchild)
else:
# 如果被刪除的節(jié)點(diǎn)有右子節(jié)點(diǎn)
if currentNode.isleftchild():
currentNode.rightchild.parent = currentNode.parent
currentNode.parent.leftchild = currentNode.rightchild
elif currentNode.isrightchild():
currentNode.rightchild.parent = currentNode.parent
currentNode.parent.righchild = currentNode.rightchild
else:
currentNode.replacenodedata(currentNode.rightchild.key,
currentNode.rightchild.payload,
currentNode.rightchild.leftchild,
currentNode.rightchild.rightchild)
# 找到后繼節(jié)點(diǎn)
def findsuccessor(self):
succ = None
if self.hasrightchild():
succ = self.rightchild().findmin()
else:
'''if self.parent:
if self.isleftchild():
succ = self.parent
else:
self.parent.rightchild = None
succ = self.parent.findsuccessor()
self.parent.rightchild = self'''
return succ
# 找到最小值節(jié)點(diǎn)
def findmin(self):
current = self
while current.hasleftchild():
current = current.leftchild
return current
# 將前面找到的節(jié)點(diǎn)摘出
def spliceOut(self):
# 若后繼節(jié)點(diǎn)為葉節(jié)點(diǎn)直接摘除
if self.isleaf():
if self.isleftchild():
self.parent.leftchild = None
'''else:
self.parent.rightchild = None'''
elif self.hasanychildren():
if self.hasleftchild():
'''if self.isleftchild():
self.parent.leftchild = self.leftchild
else:
self.parent.rightchild = self.leftchild
self.leftchild.parent = self.parent'''
else:
# 由于后繼節(jié)點(diǎn)肯定是左節(jié)點(diǎn)秤朗，且肯定只有右子節(jié)點(diǎn)，將后繼節(jié)點(diǎn)的右節(jié)點(diǎn)放在后繼節(jié)點(diǎn)父節(jié)點(diǎn)的左節(jié)點(diǎn)笔喉。
if self.isleftchild():
self.parent.leftchild = self.rightchild
else:
'''self.parent.rightchild = self.rightchild'''
self.rightchild.parent = self.parent
# 樹(shù)節(jié)點(diǎn)定義川梅，BST需要引用樹(shù)節(jié)點(diǎn)類
class TreeNode:
def __init__(self, key, val, left=None, right=None, parent=None):
self.key = key
# key值對(duì)應(yīng)存儲(chǔ)的實(shí)際值
self.payload = val
self.leftchild = left
self.rightchild = right
self.parent = parent
def hasleftchild(self):
return self.leftchild
def hasrightchild(self):
return self.rightchild
def isleftchild(self):
return self.parent and self.parent.leftchild == self
def isrightchild(self):
return self.parent and self.parent.rightchild == self
def isroot(self):
return not self.parent
def isleaf(self):
return not (self.rightchild or self.leftchild)
def hasanychildren(self):
return self.rightchild or self.leftchild
def hasbothchildren(self):
return self.rightchild and self.leftchild
def replacenodedata(self, key, val, lc, rc):
self.key = key
self.payload = val
self.leftchild = lc
self.rightchild = rc
if self.hasleftchild():
self.leftchild.parent = self
if self.hasrightchild():
self.rightchild.parent = self
