• 平衡的二叉查找树——AVL
  *
  • 复杂度问题：
  • 插入新叶节点时：
  • 如何重新平衡——旋转：
  • 如何调整平衡因子
  • 避免死胡同
  • 原本赋值方法
  • 修改后的赋值方法

平衡的二叉查找树——AVL

• 如何保持树的平衡，需要对每个节点跟踪一个“平衡因子”参数
• 平衡因子：左右子树的高度差
• 当每个节点的平衡因子在-1，0，1之间——平衡树
• 当有节点的平衡因子超过范围——需要重新平衡

复杂度问题：

• get方法：问题规模——总结点数，对比次数——深度
• 考虑最差情况下，左重avl，总节点数和的序列很接近fib——时间复杂度o(logn)
• put方法呢？1.需要更新一些父节点2.重新平衡最多旋转两次——时间复杂度还是o(logn)

插入新叶节点时：

• 作为右子节点插入，父节点的平衡度-1，反之+1
• 这种影响会一直传递，直到某个父节点的平衡度被调整到0，不再向上影响。

如何重新平衡——旋转：

• 右重子树左旋转，左重子树右旋转
• 举个例子，一个左重子树A，旋转之后将新根节点B（他的左子节B）的新右子节点A，但是如果原本这个新根节点B有右子节点C了， 就用A替换掉C， 把旧的右子节C改到旋转后的A的左子节点上。

如何调整平衡因子

新平衡因子和旧平衡因子之间的关系

避免死胡同

• 右重左旋转——》左重——》再旋转
• 先检查，左旋转之前，检查右子节点的因子；右旋转之前，检查左子节点的平衡度

原本赋值方法

#### 原本赋值方法
    def put(self, key,val):
        if self.root:   # 如果是空树，直接作为root，如果不是就调用_put
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)  
            self.size = 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)
   

修改后的赋值方法

### 修改后的赋值方法
    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 updataBalance(self,node) :  # 递归调整平衡因子的大小
        if node.balanceFactor>1 or node.balanceFacotr<-1:
            self.rebalance(node)        # 如果不平衡了需要重新调整了
            return
        if not 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.rightchild
        rotRoot.rightchild = newRoot.leftchild
        if newRoot.rightchild!=None: #如果原本有节点
            newRoot.leftchild.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isRoot():    
            self.root = newwRoot
        else :
            if rotRoot.isleftchild():
                rotRoot.parent.leftchild= newRoot
            else:
                rotBoot.parent.rightchild=newRoot
        newRoot.leftchild=rotRoot
        rotRoot.parent = newRoot
        rotRoot.balanceFactor = rotRoot.balanceFactor+1-min(newRoot.balanceFactor,0)
        newwRoot.balanceFactor =newRoot.balanceFactor+1+max(rotRoot.balanceFactor,0)
    
    def rotateRight(self,rotRoot): # 需要旋转的那个节点
        newRoot= rotRoot.leftchild
        rotRoot.leftchild = newRoot.rightchild
        if newRoot.leftchild!=None: #如果原本有节点
            newRoot.rightchild.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isRoot():    
            self.root = newRoot
        else :
            if rotRoot.isrightchild():
                rotRoot.parent.rightchild= newRoot
            else:
                rotBoot.parent.leftchild=newRoot
        newRoot.rightchild=rotRoot
        rotRoot.parent = newRoot
        rotRoot.balanceFactor = rotRoot.balanceFactor+1-min(newRoot.balanceFactor,0)
        newwRoot.balanceFactor =newRoot.balanceFactor+1+max(rotRoot.balanceFactor,0)
    
    def rebalance(self,node):
        if node.balanceFactor<0:
            if node.rigthchild.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)