AVL树插入的python实现

AVL树的插入python实现

• AVL树：AVL树是一棵自平衡的二叉搜素树

• AVL树有以下性质：

  • 根的左右子树的高度之差的绝对值不超过1
  • 根的左右子树都是平衡二叉树
    

• 插入一个节点可能会破坏AVL树的平衡，可以通过旋转操作来进行修正

• 插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能改变。我们需要找出第一个破坏了平衡条件的节点,称之为k，k的两个子树的高度差为2

• 不平衡的出现可能有四种情况

  • 左旋：不平衡是由对K的右孩子的右子树插入导致的：左旋
    

  • 右旋：不平衡是由于对k的左孩子的左子树插入导致的：右旋
    

  • 右旋-左旋：不平衡是由于对k的右孩子的左子树插入导致的：右旋-左旋
    

  • 左旋-右旋：不平衡是由于对k的左孩子的右子树插入导致的：左旋-右旋
    

代码实现

class AVLNode:
    def __init__(self,data):
        self.data = data
        self.rchild = None
        self.lchild = None
        self.parent = None
        self.bf=0 #bf为平衡值，默认为0，插入右孩子时bf+1，插入左孩子时bf-1
class AVLTree:
    def __init__(self,li=None):
        self.root=None
        #循环插入AVL树
        if li:
            for val in li:
                self.insert_no_rec(val)
    def rotate_left(self,p,c):#左旋：由右子树的右孩子插入引起失衡
        #根据左旋的规律，如果右子树的左孩子存在，左旋后，右子树的左孩子将成为原始根节点的右孩子，原始根节点成为右子树的左孩子
        s2=c.lchild
        p.rchild=s2
        if s2:
            s2.parent=p
        c.lchild=p
        p.parent=c


        p.bf=0
        c.bf=0
        return c
    def rotate_right(self,p,c):#右旋：由左子树的左孩子插入导致失衡
        #根据右旋的规律，如果左子树的右孩子存在，右旋后，左子树的右孩子将成为原始根节点的左孩子，原始根节点成为原始左子树的右孩子
        s2=c.rchild
        p.lchild=s2
        if s2:
            s2.parent=p
        c.rchild=p
        p.parent=c

        p.bf=0
        c.bf=0
        return c
    def rotate_right_left(self,p,c):#右旋-左旋： 不平衡是由于对k的右孩子的左子树插入导致的

        
        g=c.lchild
        s3=g.rchild
        c.lchild=s3
        if s3:
            s3.parent=c
        g.rchild=c
        c.parent=g

        s2=g.lchild
        p.rchild=s2
        if s2:
            s2.parent=p
        g.lchild=p
        p.parent=g

        #更新bf
        if g.bf>0:#往右偏
            c.bf=0
            p.bf=-1
        elif g.bf<0: #插入到s2中
            c.bf=1
            p.bf=0
        else:#s1,s2,s3,s4都是空
            p.bf=0
            c.bf=0
        g.bf=0
        return g
    def rotate_left_right(self,p,c):
        g=c.rchild
        s2=g.lchild
        c.rchild=s2
        if s2:
            s2.parent=c
        g.lchild=c
        c.parent=g

        s3=g.rchild
        p.lchild=s3
        if s3:
            s3.parent=p
        g.rchild=p
        p.parent=g

        if g.bf>0: #右边多
            p.bf=0
            c.bf=-1
        elif g.bf<0:#左边多
            c.bf=0
            p.bf=1
        else:
            c.bf=0
            p.bf=0
        g.bf=0
        return g

    def pre_order(self, root):  # 前序遍历
        if root:
            print(root.data, end=',')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    def in_order(self, root):  # 中序遍历
        if root:
            self.in_order(root.lchild)
            print(root.data, end=',')
            self.in_order(root.rchild)

    def post_order(self, root):  # 后序遍历
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data, end=',')

    def insert_no_rec(self,val):
        #插入
        p=self.root
        #当根节点不存在时，插入的点即为根节点
        if not p:
            self.root=AVLNode(val)
            return
        #当根节点存在时
        while True:
            #如果值小于当前节点的值，则查询他的左孩子，如果左孩子存在，则另左孩子节点为当前节点，进入下次插入，如果左孩子不存在，则将插入节点插入到当前节点的左孩子，并使当前节点的bf-1
            if val< p.data:
                if p.lchild:
                    p=p.lchild
                else:
                    p.lchild=AVLNode(val)
                    p.lchild.parent=p
                    node=p.lchild
                    p.bf=p.bf-1
                    break
             #如果值大于当前节点的值，则查询他的右孩子，如果右孩子存在，则令右孩子节点为当前节点，进行下一次插入，如果右孩子不存在，则将插入节点插入到当前节点的右孩子，使当前节点的bf+1
            elif val > p.data:
                if p.rchild:
                    p =p.rchild
                else:
                    p.rchild=AVLNode(val)
                    p.rchild.parent=p
                    node=p.rchild
                    p.bf=p.bf+1
                    break

            else:
                return
        #2.更新balance factor
        #p为当前节点，p.parent存在即当前节点不是根节点时
        while p.parent:#node.parent不空
            if p.parent.lchild==p:#传递是从左子树开始
                if p.parent.bf== -1: #原来的p.parent.bf==-1,更新后为-2                 
                    #记录当前节点的父亲节点和祖父节点，以便后面的链接
                    head=p.parent.parent
                    tmp=p.parent
                    #插入节点后，当前节点有三种状态，只有左孩子，只有右孩子，左右孩子都有，对应了三种不同的结果
                    if p.bf>0:#只有右孩子时，发生左旋-右旋
                        n=self.rotate_left_right(p.parent,p)
                        n.parent=head
                        if head:  # head不是空
                            if tmp == head.lchild:
                                head.lchild = n
                            else:
                                head.rchild = n
                            break
                        else:
                            self.root = n
                            break
                    elif p.bf<0:#只有左孩子时，发生右旋
                        n=self.rotate_right(p.parent,p)
                        n.parent=head
                        if head:  # head不是空
                            if tmp == head.lchild:
                                head.lchild = n
                            else:
                                head.rchild = n
                            break
                        else:
                            self.root = n
                            break
                    else:
                        break
                elif p.parent ==1: #原来的p.parent.bf==1,更新后变为0              
                    #当前节点只有一个孩子节点时/或平衡点不为0时，当前节点的父亲节点bf=0
                    if p.bf ==0:
                        break
                    else:
                        p.parent.bf=0
                        break
                else:#当前节点父亲节点bf=0,当前节点只有一个孩子节点时/或平衡点不为0时，当前节点的父亲节点bf=-1,并将问题向上传递
                    if p.bf==0:
                        break
                    else:
                        p.parent.bf=-1
                        p=p.parent
                        continue
            else:#右子树插入
                if p.parent.bf ==1:
                    head = p.parent.parent
                    tmp = p.parent
                    if p.bf<0:#右子树的左孩子插入
                        n=self.rotate_right_left(p.parent,p)
                        n.parent=head
                        if head:  # head不是空
                            if tmp == head.lchild:
                                head.lchild = n
                            else:
                                head.rchild = n
                            break
                        else:
                            self.root = n
                            break
                    elif p.bf>0:
                        n=self.rotate_left(p.parent,p)
                        n.parent=head
                        if head:  # head不是空
                            if tmp == head.lchild:
                                head.lchild = n
                            else:
                                head.rchild = n
                            break
                        else:
                            self.root = n
                            break
                    else:
                        break
                elif p.parent.bf == -1:
                    if  p.bf==0:
                        break
                    else:
                        p.parent.bf=0
                else:
                    if p.bf==0:
                        break
                    else:
                        p.parent.bf=1
                        p=p.parent
                        continue