平衡二叉搜索树（Balanced Binary Tree）：
是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。它能在O(log n)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。
常见的平衡二叉搜索树有
：AVL树、红黑树、Treap、节点大小平衡树。
注意
：移动树的节点时，被移动节点及其原新两个位置的父、子节点的指向均需重新指向，保证各节点指向正确。
平衡二叉搜索树(AVL树)，可以自动进行调整，以确保树时时保持平衡。
平衡因子(balance factor)
：为实现AVL树，需要在树的每个节点加入一个平衡因子(balance factor)以跟踪其变化情况。
一个节点的平衡因子为其左子树的高度和右子树的高度之差，即balanceFactor=height(leftSubTree)−height(rightSubTree)。
如果平衡因子大于零，则子树左重(left-heavy)。如果平衡因子小于零，则子树右重(right-heavy)。如果平衡因子是零，那么树完美平衡。
为实现AVL树，定义平衡因子为-1、0或1时这个树是平衡的，一旦树的节点的平衡因子超出了这个范围，则需要将树恢复平衡。
此例与BST二叉查找树的代码区别：
1、TreeNode类中，__init__多了balanceFactor属性；
2、BinarySearchTree类中，_put()中多了2行更新平衡因子的代码；
3、BinarySearchTree类中，多了updateBalance()、rotateLeft()、rotateRight()、rebalance()四个函数；
4、此例中删除节点时的平衡未实现。
示例：
# 创建树的节点类
class TreeNode(object):
# 初始化树的节点
def __init__(self, key, val, left=None, right=None, parent=None, balanceFactor=0):
self.key = key #节点值，节点位置，索引
self.payload = val #有效载荷，节点显示的值
self.leftChild = left #左子节点
self.rightChild = right #右子节点
self.parent = parent #父节点
self.balanceFactor = balanceFactor #节点的平衡因子
# 判断是否有左子节点，若有则返回左子节点
def hasLeftChild(self):
return self.leftChild
# 判断是否有右子节点，若有则返回右子节点
def hasRightChild(self):
return self.rightChild
# 判断是否是左子节点(父节点存在，并且self与self父节点的左子节点相同)
def isLeftChild(self):
# 下面的含义是(self.parent is not None) and (self.parent.leftChild == 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 #有左或右子节点
# 判断是否有2个子节点
def hasBothChildren(self):
return self.rightChild and self.leftChild #有左右2个子节点
# 替换节点数据
def replaceNodeData(self, key, value, lc, rc):
self.key = key #更新节点值
self.payload = value #更新有效载荷
self.leftChild = lc #更新左子节点
self.rightChild = rc #更新右子节点
if self.hasLeftChild(): #若有左子节点
self.leftChild.parent = self #将该节点的左子节点的父节点指向self
if self.hasRightChild(): #若有右子节点
self.rightChild.parent = self #将该节点的右子节点的父节点指向self
# 中序遍历
# 只要用了yield语句，普通函数就是生成器，也是迭代器，在定义过程中不需要像迭代器那样写__iter__()和__next__()方法。yield语句的作用就是在调用的时候返回相应的值和作为生成器的标志。
def __iter__(self):
if self: #若当前节点存在，则
if self.hasLeftChild(): #若当前节点有左子节点，则
for elem in self.leftChild: #循环输出当前节点的左子树的节点值
yield elem #在for循环中，每次执行到yield时，就返回一个迭代值，且不会终止循环；下个循环时，代码从yield返回值的下一行继续返回
yield self.key #返回当前节点值
if self.hasRightChild(): #若当前节点有右子节点，则
for elem in self.rightChild: #循环输出当前节点的右子树的节点值
yield elem
# 将被删除节点的继任者拼接到被删除的节点位置
def spliceOut(self):
if self.isLeaf(): #若被删除节点是叶节点，则无需再拼接
if self.isLeftChild(): #若被删除节点是父节点的左子节点，则
self.parent.leftChild = None #被删除节点为None，无需再拼接
else: #若被删除节点是父节点的右子节点，则
self.parent.rightChild = None #被删除节点为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
# 查找被删除节点的继任者，继任者节点最多只能有一个子节点
def findSuccessor(self):
succ = None #初始化被删除节点的继任者为None
if self.hasRightChild(): #若被删除节点有右子节点，则
succ = self.rightChild.findMin() #获取被删除节点的右子树中的最小节点作为继任者
else: #若被删除节点没有右子节点，则
if self.parent: #若被删除节点有父节点，则
if self.isLeftChild(): #若被删除节点是父节点的左子节点，则
succ = self.parent #被删除节点的父节点是继任者
else: #若被删除节点是父节点的右子节点，则被删除节点的继任者是其父节点的继任者，不会是被删除节点
self.parent.rightChild = None #暂时将None赋值给被删除节点，则继任者不会是被删除节点，方便下一行递归查找
succ = self.parent.findSuccessor() #将被删除节点的父节点的继任者作为继任者
self.parent.rightChild = self #获得继任者后，重新将被删除节点赋值给自己，以免被删除节点为None扰乱树结构
return succ
# 查找当前树的最小子节点，因此例是BST搜索树，左子节点的值是最小的，所以只找左子节点
def findMin(self):
current = self #将自身设置为当前节点
while current.hasLeftChild(): #若当前节点有左子节点，则循环
current = current.leftChild #将当前节点的左子节点作为下一个当前节点
return current #返回最终左子节点，即此树中的最小节点
# 二叉查找树类(此例为BST搜索树类)
class BinarySearchTree(object):
# 初始化空二叉树
def __init__(self):
self.root = None
self.size = 0
# 获取树的大小
def length(self):
return self.size
# 通过__len__方法使用len()
def __len__(self):
return self.size
# 实现了__iter__方法的对象就是可迭代对象，__iter__覆盖for x in操作，因此它是递归的！因它是在TreeNode实例上递归的，所以__iter__方法在TreeNode类中定义
def __iter__(self):
return self.root.__iter__() #返回二叉查找树根节点的迭代，即遍历二叉查找树
# 创建二叉搜索树
def put(self, key, val):
if self.root: #若树已经有根节点，则
self._put(key, val, self.root) #从树的根开始，搜索二叉树
else: #若树没有根节点，则
self.root = TreeNode(key, val) #创建一个新的TreeNode并把它作为树的根节点
self.size = self.size + 1 #增加树的大小
# 搜索树，put()的辅助函数
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) #创建一个新的TreeNode并把它作为当前节点的左子节点
self.updateBalance(currentNode.leftChild) #更新当前节点的左子节点的平衡因子
elif key == currentNode.key: #若新的键值=当前节点键值，则
currentNode.payload = val #更新当前节点的有效载荷
self.size = self.size - 1 #由于只修改，未增加，又因put()中+1，所以此处-1
else: #若新的键值>=当前节点键值，则搜索右子树
if currentNode.hasRightChild(): #若当前节点有右子树要搜索，则
self._put(key, val, currentNode.rightChild) #递归搜索右子树
else: #若当前节点无右子树要搜索，则
currentNode.rightChild = TreeNode(key, val, parent = currentNode) #创建一个新的TreeNode并把它作为当前节点的右子节点
self.updateBalance(currentNode.rightChild) #更新当前节点的右子节点的平衡因子
# 更新平衡因子
def updateBalance(self, node):
if node.balanceFactor > 1 or node.balanceFactor < -1: #若节点的平衡因子不是-1、0、1，则
self.rebalance(node) #该节点再平衡
return
if node.parent != None: #若该节点有父节点，即该节点不是根节点，则
if node.isLeftChild(): #若该节点是左子节点，则
node.parent.balanceFactor += 1 #该节点的父节点的平衡因子+1
elif node.isRightChild(): #若该节点是右子节点，则
node.parent.balanceFactor -= 1 #该节点的父节点的平衡因子-1
if node.parent.balanceFactor != 0: #若该节点的父节点的平衡因子不为0，则
self.updateBalance(node.parent) #更新该节点的父节点的平衡因子
# 左旋转（右重的树要左旋转才平衡）
"""
示例：B为原根，D为新根，节点的高度为子孙节点的最大层级+1，下面为树的图
B D
A D B E
C E A C
newBal(B) = hA - hC #新B节点的平衡因子为A与C节点的高度差
oldBal(B) = hA - hD #原B节点的平衡因子为A与D节点的高度差
oldBal(B) = hA - (1 + max(hC, hE)) #原D节点的高度为两子树高度中较大者加1，hC和hE没有改变
newBal(B) - oldBal(B) = hA - hC - (hA - (1 + max(hC, hE))) = 1 + max(hC, hE) - hC
newBal(B) = oldBal(B) + 1 + max(hC, hE) - hC = oldBal(B) + 1 + max(hC - hC, hE - hC)
= oldBal(B) + 1 + max(hE - hC, 0) = oldBal(B) + 1 + max(-oldBal(D), 0)
= oldBal(B) + 1 - min(oldBal(D), 0) #根据平衡因子计算公式：oldBal(D)=hC-hE，得出hE-hC=−oldBal(D)
newBal(D) = hB - hE
oldBal(D) = hC - hE
newBal(D) - oldBal(D) = hB - hC = 1 + max(hA, hC) - hC = 1 + max(hA - hC, hC - hC)
newBal(D) = oldBal(D) + 1 + max(hA - hC, 0) = oldBal(D) + 1 + max(newBal(B), 0)
"""
def rotateLeft(self, rotRoot):
newRoot = rotRoot.rightChild #待旋转节点的右子节点设为新的根节点
rotRoot.rightChild = newRoot.leftChild #新根的原左子节点作为原根的新右子节点
if newRoot.leftChild != 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) #更新原根节点的平衡因子，被移动的子树内的节点的平衡因子不受旋转影响，计算方法见上方注释
newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0) #更新新根节点的平衡因子，被移动的子树内的节点的平衡因子不受旋转影响，计算方法见上方注释
# 右旋转（左重的树要右旋转才平衡）
"""
示例：E为原根，C为新根，节点的高度为子孙节点的最大层级
E C
C F B E
B D A D F
A
newBal(E) = hD - hF
oldBal(E) = hC - hF
newBal(E) - oldBal(E) = hD - hC = hD - (1 + max(hB, hD)) = -1 + min(hD - hB, hD - hD)
= -1 + min(hD - hB, 0) = -1 - max(hB - hD, 0)
= - max(oldBal(C), 0) - 1
newBal(E) = oldBal(E) - 1 - max(oldBal(C), 0)
newBal(C) = hB - hE
oldBal(C) = hB - hD
newBal(C) - oldBal(C) = hD - hE = hD - (1 + max(hD, hF)) = -1 + min(hD - hD, hD - hF)
= -1 + min(0, hD - hF) = -1 + min(0, newBal(E))
newBal(C) = oldBal(C) - 1 + min(0, newBal(E))
"""
def rotateRight(self, rotRoot):
newRoot = rotRoot.leftChild #待旋转节点的左子节点设为新的根节点
rotRoot.leftChild = newRoot.rightChild #新根的原右子节点作为原根的新左子节点
if newRoot.rightChild != None: #若新根原来有右子节点，则
newRoot.rightChild.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.rightChild = rotRoot #将新根的右子节点指向原根
rotRoot.parent = newRoot #将原根的父节点指向新根
rotRoot.balanceFactor = rotRoot.balanceFactor - 1 - max(newRoot.balanceFactor, 0) #更新原根节点的平衡因子，被移动的子树内的节点的平衡因子不受旋转影响，计算方法见上方注释
newRoot.balanceFactor = newRoot.balanceFactor - 1 + min(0, rotRoot.balanceFactor) #更新新根节点的平衡因子，被移动的子树内的节点的平衡因子不受旋转影响，计算方法见上方注释
# 再平衡
def rebalance(self, node):
if node.balanceFactor < 0: #若该节点的平衡因子<0，则
if node.rightChild.balanceFactor > 0: #若该节点的右子节点的平衡因子>0，则
self.rotateRight(node.rightChild) #右旋转该节点的右子节点
self.rotateLeft(node) #左旋转该节点
elif node.balanceFactor > 0: #若该节点的平衡因子>0，则
if node.leftChild.balanceFactor < 0: #若该节点的左子节点的平衡因子<0，则
self.rotateLeft(node.leftChild) #左旋转该节点的左子节点
self.rotateRight(node) #右旋转该节点
# 通过__setitem__方法使用mytree[3]="red"方式，否则只能用put()方法
def __setitem__(self, k, v):
self.put(k, v)
# 根据索引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
# 搜索树，get()的辅助函数
def _get(self, key, currentNode):
if not currentNode: #若没有当前节点，则返回None
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) #递归查找当前节点的右子树
# 通过__getitem__方法使用mytree[3]获取值的方式，否则只能用get()方法
def __getitem__(self, key):
return self.get(key)
# 通过__contains__方法使用in方法
def __contains__(self, key):
if self._get(key, self.root):
return True
else:
return False
# 根据索引key删除其对应的节点
def delete(self, key):
if self.size > 1: #若树的大小>1，则
nodeToRemove = self._get(key, self.root) #获取要删除的节点
if nodeToRemove: #若该节点存在，则
self.remove(nodeToRemove) #删除该节点
self.size = self.size - 1 #树的大小减1
else: #若该节点不存在，则
raise KeyError('错误，键值不在树中') #报错
elif self.size == 1 and self.root.key == key: #若树的大小为1，且要删除的是根，则
self.root = None #根节点为None
self.size = self.size - 1 #树的大小减1
else: #若树的大小为0，则为空树
raise KeyError('错误，键值不在树中') #报错
# 通过__delitem__方法使用del方法
def __delitem__(self, key):
self.delete(key)
# 删除节点
def remove(self, currentNode):
if currentNode.isLeaf(): #若被删除节点是叶节点，则没有子节点
if currentNode == currentNode.parent.leftChild: #若被删除节点是其父节点的左子节点，则
currentNode.parent.leftChild = None #被删除节点为None
else: #若被删除节点是其父节点的右子节点，则
currentNode.parent.rightChild = None #被删除节点为None
elif currentNode.hasBothChildren(): #若被删除节点有2个子节点，则
succ = currentNode.findSuccessor() #获取被删除节点的继任者(防止树结构混乱)
succ.spliceOut() #将被删除节点的继任者拼接到被删除节点位置
currentNode.key = succ.key #将被删除节点位置的值设置为继任者的值
currentNode.payload = succ.payload #将被删除节点的有效载荷设置为继任者的有效载荷
else: #若被删除节点只有1个子节点，则
if 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.rightChild = currentNode.rightChild
else: #若被删除节点无父节点，则被删除节点为根节点
# 替换被删除节点的右子节点的键、有效载荷、左子节点和右子节点数据
currentNode.replaceNodeData(currentNode.rightChild.key, currentNode.rightChild.payload, currentNode.rightChild.leftChild, currentNode.rightChild.rightChild)
mytree = BinarySearchTree() #实例化二叉搜索树
mytree[2]="yellow" #此例中第一个添加到mytree的索引值为2
mytree[0]="red" #通过__setitem__方法添加节点
mytree[1]="blue"
mytree[3]="at"
print(mytree[3])
mytree[3]="at2" #修改mytree[3]的值
print(mytree[3])
mytree.put(4, 'val') #通过put()方法在索引为4的位置添加'val'
if 4 in mytree: #in使用__contains__()判断索引是否在树中
print('in')
print(len(mytree)) #通过__len__方法获取mytree树的大小
print(mytree.length()) #通过length()方法获取mytree树的大小
print(mytree[4]) #通过__getitem__方法获取索引为4的节点
print(mytree.get(4)) #通过get()方法获取索引为4的节点
print(mytree.root.key) #树的根节点的key
mytree.delete(2) #通过delete()方法删除索引为2的节点
# del mytree[2] #通过__delitem__方法删除索引为2的节点
print(mytree[2])
for i in mytree: #通过两个类中的__iter__方法进行迭代
print(i)
结果为：
at
at2
in
5
5
val
val
1
None
0
1
3
4
版权声明：本文为qq_38882327原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。