【AVL树】左旋&右旋&添加&删除

Lthero

AVL旋转一共有四种情况（其实只有两种，另外两种对称的）

=================================================================================
树的高度
当前结点A自身高度为0，有一个左子结点B或右子结点C，则结点A的高度加一

如：12的左高度为0，右高度为2；16的左高度为0，右高度为1；18的左高度=右高度=0
结点A左高度=max(左子树的左高度，左子树的右高度)+1
结点A右高度=max(右子树的左高度，右子树的右高度)+1

=================================================================================
左旋转
右子树的高度高于左子树，且差值大于2，所以需要进行左旋转，来降低右子树的高度
情况一：只要一次左旋转

对12和16进行左旋转，将12变成16的左子结点，16的右子树也保持位置不变；16的左子树要转给12，当12的右子树

• 设置当前结点为the_node，temp是当前结点的右子结点
• 下面代码的direction，记录的是当前结点和他父结点的关系(当前结点是他父结点的左子结点，direction='left'
  

[Python] 纯文本查看 复制代码

    def l_rotate(self, the_node):
        direction = self.find(the_node.value, self.head)[1]
        temp = the_node.right
        # 把16的左子树要转给12，当12的右子树
        the_node.right = temp.left
        # 把16的父结点给12
        temp.pre = the_node.pre
        # 把16变成12的左子结点
        temp.left = the_node
        # 如果当前结点是头结点，把头结点重新标记成12
        if the_node.value == self.head.value:
            self.head = temp
        else:
            # 当前结点不是头结点，说明上面有父结点
            # 当前结点16是他父结点的左子结点，把这个关系转给12
            if direction == 'left':
                the_node.pre.left = temp
            else:
                the_node.pre.right = temp
        # 当前结点16的父结点变成（它的原右子结点）12
        the_node.pre = temp
        # 更新两个结点的层数
        if the_node.right is not None:
            the_node.r_height = max(the_node.right.r_height, the_node.right.l_height) + 1
        else:
            the_node.r_height = 0
        self.update_height2(temp)

====================================================================================

情况二：先一次右旋转，再左旋转


12的右高度为2，左高度为0，要调整


先对16和13进行一次右旋转，变成这样


和之前一样，再对12和13进行左旋转，变成下面这样



=====================================================================================
右旋转的代码（左的代码将left改成right,right改成left就行）

[Python] 纯文本查看 复制代码

    def r_rotate(self, the_node):
        direction = self.find(the_node.value, self.head)[1]
        temp = the_node.left
        the_node.left = temp.right
        temp.pre = the_node.pre
        temp.right = the_node
        if the_node.value == self.head.value:
            self.head = temp
        else:
            if direction == 'left':
                the_node.pre.left = temp
            else:
                the_node.pre.right = temp
        the_node.pre = temp
        if the_node.left is not None:
            the_node.l_height = max(the_node.left.l_height, the_node.left.r_height) + 1
        else:
            the_node.l_height = 0
        self.update_height2(temp)

=================================================================================
=============================未完待续==============================================
=================================================================================


附件是全部代码，基本实现了添加，删除结点功能，show方法用的层序遍历

代码有些乱，这两天再改，准备写成个可视化小程序


帖子只作自我记录，有错误的地方欢迎指正

Z-Ero

感谢楼主分享，学习一下

从0开始的小小怪

这种avl树的旋转用3+4重构更简单