作为左子节点插入,则父节点平衡因子会增加1;
作为右子节点插入,则父节点平衡因子会减少1。
传递到根节点为止;或者某个父节点平衡因子被调整到0,不再影响上层节点的平衡因子为止。(无论从-1或者1调整到0,都不会改变子树高度)
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.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
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)
视“左重”或者“右重”进行不同方向的旋转,同时更新相关父节点引用,更新旋转后被影响节点的平衡因子
将右子节点B提升为子树的根,将旧根节点A作为新根节点B的左子节点,如果新根节点B原来有左子节点,则将此节点设置为A的右子节点(A的右子节点一定有空)
旋转后,新根节点将旧根节点作为右子节点,但是新根节点原来已有右子节点,需要将原有的右子节点重新定位!原有的右子节点D改到旧根节点E的左子节点。同样, E的左子节点在旋转后一定有空
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)
保持了次序ABCDE,ACE的平衡因子不变
• hA/hC/hE不变
主要看BD新旧关系
左旋转后变成“左重”了
“左重”再右旋转,还回到“右重”
如果右子节点“左重”的话,先对它进行右旋转再实施原来的左旋转
如果左子节点“右重”的话,先对它进行左旋转再实施原来的右旋转
def rebalance(self,node):
if node.balanceFactor < 0:
if node.rightChild.balanceFactor > 0:
# Do an LR Rotation
self.rotateRight(node.rightChild)
self.rotateLeft(node)
else:
# single left
self.rotateLeft(node)
elif node.balanceFactor > 0:
if node.leftChild.balanceFactor < 0:
# Do an RL Rotation
self.rotateLeft(node.leftChild)
self.rotateRight(node)
else:
# single right
self.rotateRight(node)
不过, put方法的代价有多大?
需要插入的新节点是叶节点,更新其所有父节点和祖先节点的代价最多为O(log n)
如果插入的新节点引发了不平衡,重新平衡最多需要2次旋转,但旋转的代价与问题规模无关,是常数O(1)
所以整个put方法的时间复杂度还是O(log n)
本文地址:https://blog.csdn.net/weixin_39020133/article/details/107080493
如对本文有疑问, 点击进行留言回复!!
【状压dp】[HDU1400 & poj2411] Mondriaan‘s Dream
Qt + Python + OpenCV图标替换工具 之 Qt界面设计(四)
网友评论