1.AVL简介
这篇文章我们要介绍的是能够在key插入时一直保持平衡的二叉查找树(AVL树,AVL是发明者的名字缩写)
利用AVL实现ADT MAP,基本上与BST的实现相同。不同之处在于二叉树的生成与维护过程。
2.AVL中的概念
AVL树的实现中,需要对每个节点跟踪“平衡因子balance factor”参数。
平衡因子是根据节点的左右子树的高度来定义的。确切的来说,是左右子树的高度差。balanceFactor = height(leftSubTree) - height(rightSubTree)。
如果平衡因子大于0,称为“左重 left-heavy”,小于0,称为“右重right-heavy”,平衡因子等于0,则称作平衡。
如果一个二叉查找树中每个节点的平衡因子都在-1,0,1之间,则把这个二叉搜索树称为平衡树。
3.AVL树性能分析
分析AVL树最差情形下的性能,即平衡因子为1或者-1时
总结点数N 和比对次数(树的高度h)之间的关系。
h = 1,N = 1
h = 2,N = 2
h = 3,N = 4 = 1 + 1 +2
h = 4,N = 7 = 1 + 2 + 4
Nh = 1 + Nh-1 + Nh-2
h = 1.44logNh
可以说AVL树的搜索时间复杂度为O(logn)
4.AVL树的python实现
AVL平衡树确实能够改进BST树的性能,避免退化情形
我们来看看向AVL树插入一个新key,如何才能保持AVL树的平衡性质。
首先,作为BST,新key必定以叶节点形式插入到AVL树中。而叶节点的平衡因子始终是0,其本身无需重新平衡。但会影响父节点的平衡因子。
- 作为左子节点插入,则父节点平衡因子会增加1
- 作为右子节点插入,则父节点平衡因子会减少1
这种影响可能会随着其父节点到根节点的路径一直传递上去。直到:
- 传递到根节点为止
- 或者某个父节点平衡因子被调整到0,则不再影响上层节点的平衡因子。(无论是从-1到0还是1到0,子树的高度都没有发生改变)
重新定义_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)
self.updateBalance(currenNode.leftChild)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val)
self.updateBalance(currentNode.rightChild)
def updateBalance(self,node):
if node.balanceFactor > 1 or node.balanceFactor < -1:
self.reblance(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(self,node.parent)
# 主要手段:将不平衡的子树进行旋转rotation
def rebalance(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)
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)
5.小结
经过复杂的put方法,avl树始终维持平衡,get方法保持O(logn)高性能。
那么put方法的代价呢?
将put方法分成两个部分:
需要插入的新节点时叶节点,更新其所有父节点和祖先节点的代价最多为O(logn)。
如果插入的新节点引发了不平衡,重新平衡最多需要2次旋转,但旋转的代价与问题的规模无关,是常数O(1)。所以整个put方法的时间复杂度还是O(logn)。