本章内容
- 平衡二叉树定义
- AVL树实现
一、平衡二叉树（AVL树定义）
能够在key插入时一直保持平衡的二叉查找树，AVL树的实现中，需要对每个节点跟踪 “平衡因子balance factor”参数。
平衡因子：
平衡因子是根据节点的左右子树的高度来定义的，确切地说，是左右子树高度差：
如果平衡因子大于0，称为“左重left-heavy” ， 小于零称为“右重right-heavy” 平衡因子等于0，则称作平衡。
如果一个二叉查找树中每个节点的平衡因 子都在-1，0，1之间，则把这个二叉搜索树称为平衡树。在平衡树操作过程中，有节点的平衡因子超出此范围，则需要一个重新平衡的过程，同时要保持BST的性质。
二、AVL树的实现
首先，作为BST，插入新key必定以叶节点形式插入到AVL树中。
会引起什么反应？
叶节点的平衡因子：
其本身无需重新平衡。
父节点的平衡因子：
- 作为左子节点插入，则父节点平衡因子会增加1；
- 作为右子节点插入，则父节点平衡因子会减少1。
这种影响可能随着其父节点到根节点的路径一直传递上去，直到： 传递到根节点为止； 或者某个父节点平衡因子被调整到0，不再影响上层节点的平衡因子为止。
主要手段：将不平衡的子树进行旋转rotation
视“左重”或者“右重”进行不同方向的旋转,同时更新相关父节点引用，更新旋转后被影响节点的平衡因子。
最简单情况
如图，是一个“右重”子树A的左旋转 （并保持BST性质） 将右子节点B提升为子树的根，将旧根节点A作为新根节点B的左子节点，如果新根节点B原来有左子节点，则将此节点设 置为A的右子节点（A的右子节点一定有空）
稍微复杂情况：
旋转后，新根节点将旧根节点作为右子节点，但是新根节点原来已有右子节点，需要将原有的右子节点重新定位。 原有的右子节点D改到旧根节点E的左子节点同样，E的左子节点在旋转后一定有空
最复杂的情况：
下图的“右重”子树，单纯的左旋转无法实现平衡 左旋转后变成“左重”了 “左重”再右旋转，还回到“右重”。
所以，在左旋转之前检查右子节点的因子 如果右子节点“左重”的话，先对它进行右旋转 再实施原来的左旋转。同样，在右旋转之前检查左子节点的因子 如果左子节点“右重”的话，先对它进行左旋转 再实施原来的右旋转。
如何调整平衡因子：
A、C、E三个的平衡因子没有变化
新B= hA- hC
旧B= hA- 旧hD
而：
旧hD= 1+ max(hC, hE)，所以旧B= hA- (1+ max(hC, hE))
新B- 旧B= 1+ max(hC, hE)- hC
新B= 旧B+ 1+ max(hC, hE)- hC；把hC移进max函数里就有
新B= 旧B+ 1+ max(0, -旧D) <==> 新B= 旧B+ 1- min(0, 旧D)
代码实现：
class AVLTree(BinarySearchTree):
def __init__(self):
'''
继承于BST，重写方法并在此基础上添加方法修改
'''
super().__init__()
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)
self.updateBalance(currentNode.leftChild) # 调整平衡因子
else:
if currentNode.hasRightChild():
self._put(key, val, currentNode.ritghchild)
else:
currentNode.ritghchild = TreeNode(key, val, parent=currentNode)
self.updateBalance(currentNode.ritghchild)
def updateBalance(self, node):
if node.balanceFactor > 1 or node.balanceFactor < -1:
self.rebalance(node)
return
if node.parent != None:
if node.isLeftChild():
node.parent.balanceFactor += 1
elif node.isRightChild():
node.parent.balanceFactor -= 1
if node.parent.balanceFactor !=0 :
self.updateBalance(node.parent)
def rotateLeft(self,rotRoot):
'''
左旋代码
右旋代码参考同样的流程
'''
newRoot = rotRoot.ritghchild
rotRoot.ritghchild = 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.ritghchild = 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)
def rotateRight(self, rotnode):
pass
def rebalance(self, node):
'''
1、在左旋转之前检查右子节点的因子
如果右子节点“左重”的话，先对它进行右旋转
再实施原来的左旋转
2、在右旋转之前检查左子节点的因子
如果左子节点“右重”的话，先对它进行左旋转
再实施原来的右旋转
'''
# 右重需要左旋
if node.balanceFactor < 0:
if node.ritghchild.balanceFactor > 0:
# RL
self.rotateRight(node.ritghchild)
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)
AVL树总结：
需要插入的新节点是叶节点，更新其所有父节点 和祖先节点的代价最多为O(log n) 如果插入的新节点引发了不平衡，重新平衡最多 需要2次旋转，但旋转的代价与问题规模无关， 是常数O(1) 所以整个put方法的时间复杂度还是O(log n)。
网友评论