方法介绍：
通过二叉查找树保存Key，实现快速查找
还有散列表法（散列及解决冲突），与有序表法（二分查找）
BST定义：
左子树节点key比根节点来的小，右子树节点key比根节点大。
image.png
可以看出，根据插入值的顺序，生成的BST树也不一样。不是完全有序。
BST方法介绍：
- put、get方法：
插入BST中，创建新节点。
没啥可说的，注意递归，递归结束条件为找到合适的位置，put创建树节点加入到子节点中去；get方法将找到的节点return。 -
delete方法：
移除当前BST的某个节点。
①先通过get方法去找key，找到需要删除的节点。
②判断节点是否为叶节点，若为叶节点，直接删除（令叶节点为None）
③若有左右子节点，则去找后继节点
后继节点法：通过看删除节点的右子节点中最小的那个节点（取最靠近待删除节点的值取代删除的节点值。）找到后继节点后，拆除待删除节点并放入后继节点
拆除方法：若后继节点为叶节点直接摘除；如果不是，由于后继节点肯定是左节点，且肯定只有右子节点，将后继节点的右节点放在后继节点父节点的左节点。
image.png
④如果只有左节点或者右节点
一、 如果被删除的节点有左子节点：若被删除的节点是左子节点，则删除；右子也是一样；如果被删除的节点是根节点，则直接去他的左子节点替换。
二、 如果被删除的节点有右子节点：同上
算法分析：
查找算法复杂度：如果随机分布，则两边平均分布key值大致相等
put方法的复杂度为O(log2n)
AVL树概念：
AVL树的定义（平衡二叉查找树）：
对每个节点引入平衡因子参数
平衡因子：左右子树的高度差。
AVL树平衡因子为0，-1，1
AVL树搜索的时间复杂度：O(logn)
image.png
AVL树方法：
- 新key以叶节点插入BST
- 重新平衡，并修改父节点的平衡因子（左重或者右重，进行旋转重新平衡AVL树），
直到两种情况：①根节点②父节点的平衡因子被调整为0
旋转方法如下：
1.左重，右旋
2.右重，左转，如果右子节点不存在左重，
则如下图，把右子节点B变为根节点，将A作为B的左子节点，若原B有左子节点，则把该节点挂在A的右子节点处。
更新父节点引用，并更新平衡因子
image.png
image.png
如果右子节点存在左重
则先进行右旋，在实施左旋
image.png
右旋的代码类似左旋
总体代码如下：
# BST树的构建
class BinarySearchTree:
def __init__(self):
# 引用根节点TreeNode类
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
# 迭代器 实现 for key in tree
def __iter__(self):
return self.root.__iter__()
# 插入key，构造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)
# 索引赋值：实现 mytree[key] = value
def __setitem__(self, key, value):
self.put(key, value)
# 在二叉树中找到key所在的节点并取值
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树的方法：
'''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):
# 若节点不平衡，需要调整（旋转）
if node.balancefactor > 1 or node.balancefactor < -1:
self.rebalance(node)
return
# 如果在-1至1之间，平衡，看是否有父节点，如果有，调整父节点
if node.parent is not None:
if node.isleftchild():
node.parent.balancefactor += 1
elif node.isrightchild():
node.parent.balancefactor -= 1
# 调整以后的父节点平衡因子不为0，则再调整父节点的父节点平衡因子
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):
# 节点是不是左重
if node.balancefactor < 0:
# 左重的子节点是不是右重
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)'''
# 索引取值 实现 value = mytree[key]
def __getitem__(self, key):
return self.get(key)
# 寻找索引 实现 key in mytree
def __contains__(self, key):
if self._get(key, self.root):
return True
else:
return False
# 迭代器实现 实现 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')
# 实现方法 del tree(key)
def __delitem__(self, key):
self.delete(key)
def remove(self, currentNode):
# 判断节点是否为叶节点，若为叶节点，直接删除（令叶节点为None）
if currentNode.isleaf():
if currentNode == currentNode.parent.leftchild():
currentNode.parentchild.leftchild = None
else:
currentNode.parentchild.rightchild = None
else:
if currentNode.hasbothchildren():
# 后继节点法：通过看删除节点的右子节点中最小的那个节点（取最靠近待删除节点的值取代删除的节点值。）找到后继节点后，拆除待删除节点并放入后继节点
succ = currentNode.findsuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.payload = succ.payload
elif currentNode.hasleftchild():
# 如果被删除的节点有左子节点
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:
# 如果被删除的节点有右子节点
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)
# 找到后继节点
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
# 找到最小值节点
def findmin(self):
current = self
while current.hasleftchild():
current = current.leftchild
return current
# 将前面找到的节点摘出
def spliceOut(self):
# 若后继节点为叶节点直接摘除
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:
# 由于后继节点肯定是左节点，且肯定只有右子节点，将后继节点的右节点放在后继节点父节点的左节点。
if self.isleftchild():
self.parent.leftchild = self.rightchild
else:
'''self.parent.rightchild = self.rightchild'''
self.rightchild.parent = self.parent
# 树节点定义，BST需要引用树节点类
class TreeNode:
def __init__(self, key, val, left=None, right=None, parent=None):
self.key = key
# key值对应存储的实际值
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
