AVL树：AVL树是一棵自平衡的二叉搜索树
    AVL树具有与以下性质：
    根的左右子树高度差的绝对值不超过1
    根的左右子树都是平衡二叉树

    image.png

    image.png
    插入一个节点可能会破坏AVL树的平衡，可以通过旋转操作来进行修正。
    插入一个节点后，只有从插入节点到根节点的路径上的节点平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为K。K的两颗子树的高度查2。
    不平衡的出现可能有4中情况。
    旋转口诀：
    对于K，右右->左旋，左左->右旋，右左->右左，左右->左右

    IMG_0616.PNGIMG_0618.PNGIMG_0619.PNGIMG_0620.PNG

    1、需引用二叉搜索树

    1. # -*- encoding= utf-8 -*-
    2. from bst_new import BiTreeNode,BST
    4. class AVLNode(BiTreeNode):
    5.     def __init__(self,data):
    6.         BiTreeNode.__init__(self,data)
    7.         #self.bf=0  #此处的self.bf添加到BiTreeNode.__inint__中去
    8. class AVLTree(BST):
    9.     def __init__(self,li=None):
    10.         BST.__init__(self,li)
    11.     def rotate_left(self,p,c):   #此函数只用于插入时，没问题，用于删除时，有问题
    12.         s2=c.lchild
    13.         p.rchild=s2
    14.         if s2:
    15.             s2.parent=p
    16.         c.lchild=p
    17.         p.parent=c
    18.         p.bf=0
    19.         c.bf=0
    20.         return c
    22.     def rotate_right(self,p,c):
    23.         s2=c.rchild
    24.         p.lchild=s2
    25.         if s2:
    26.             s2.parent=p
    27.         c.rchild=p
    28.         p.parent=c
    29.         p.bf=0
    30.         c.bf=0
    31.         return c
    32.     def rotate_right_left(self,p,c):
    33.         g=c.lchild
    34.         s3=g.rchild
    35.         c.lchild=s3
    36.         if s3:
    37.             s3.parent=c
    38.         g.rchild=c
    39.         c.parent=g
    40.         s2=g.lchild
    41.         p.rchild=s2
    42.         if s2:
    43.             s2.parent=p
    44.         g.lchild=p
    45.         p.parent=g
    47.         #更新bf
    48.         if g.bf>0:
    49.             p.bf=-1
    50.             c.bf=0
    51.         elif g.bf<0:
    52.             p.bf=0
    53.             c.bf=1
    54.         else: #插入的是g
    55.             p.bf=0
    56.             c.bf=0
    57.         return g #返回根节点
    58.     def rotate_left_right(self,p,c):
    59.         g=c.rchild
    60.         s2=g.lchild
    61.         c.rchild=s2
    62.         if s2:
    63.             s2.parent=c
    64.         g.lchild=c
    65.         c.parent=g
    66.         s3=g.rchild
    67.         p.lchild=s3
    68.         if s3:
    69.             s3.parent=p
    70.         g.rchild=p
    71.         p.parent=g
    72.         #更新bf
    73.         if g.bf<0:
    74.             c.bf=0
    75.             p.bf=1
    76.         elif g.bf>0:
    77.             p.bf=0
    78.             c.bf=-1
    79.         else: #插入的是g
    80.             p.bf=0
    81.             c.bf=0
    82.         return g
    83.     def insert_no_rec(self,val):
    84.         # 1、和二叉搜索(bst)数一样，插入
    85.         p=self.root
    86.         if not p:    #空树时，直接定义个二叉树根节点
    87.             self.root=BiTreeNode(val)
    88.             return
    89.         while True:
    90.             if val<p.data:
    91.                 if p.lchild:      #此处可看出与递归的方式的区别
    92.                     p=p.lchild
    93.                 else:           #左孩子不存在
    94.                     p.lchild=BiTreeNode(val)
    95.                     p.lchild.parent=p
    96.                     node=p.lchild   #node存储的是插入的节点
    97.                     break
    98.             elif val>p.data:
    99.                 if p.rchild:
    100.                     p=p.rchild
    101.                 else:
    102.                     p.rchild=BiTreeNode(val)
    103.                     p.rchild.parent=p
    104.                     node=p.rchild
    105.                     break
    106.             else:   # val=p.data
    107.                 return
    108.         #2、更新bf
    109.         while node.parent: #node.parent不空
    110.             if node.parent.lchild==node:#传递是从左子树来的，左子树更沉了
    111.                 #更新node.parent的bf  -=1
    112.                 if node.parent.bf <0: #原来node.parent.bf=-1,更新之后变成-2
    113.                     #做旋转
    114.                     #看node哪边沉
    115.                     x=node.parent #旋转前的子树的根
    116.                     g=node.parent.parent   #为了连接旋转之后的子树
    117.                     if node.bf>0:
    118.                         n=self.rotate_left_right(node.parent,node)
    119.                     else:
    120.                         n=self.rotate_right(node.parent,node)
    121.                     # 记得把n和g连起来
    122.                 elif node.parent.bf>0: #原来node.parent.bf=1,更新之后变成0
    123.                     node.parent.bf=0
    124.                     break
    125.                 else: #原来node.parent.bf=0,更新之后变成-1
    126.                     node.parent.bf=-1
    127.                     node=node.parent
    128.                     continue
    129.             else:#传递是从右子树来的，右子树更沉了
    130.                 #更新node.parent.bf+=1
    131.                 if node.parent.bf>0: #原来node.parent.bf=1,更新之后变成2
    132.                     #做旋转
    133.                     #看node哪边沉
    134.                     g=node.parent.parent
    135.                     x=node.parent #旋转前的子树的根
    136.                     if node.bf<0:  #node.bf= -1
    137.                         n=self.rotate_right_left(node.parent,node)
    138.                     else:   #node.bf= 1
    139.                         n=self.rotate_left(node.parent,node)
    140.                     # 记得连起来
    141.                 elif node.parent.bf<0: #原来node.parent.bf=-1,更新之后变成0
    142.                     node.parent.bf=0
    143.                     break
    144.                 else: #原来node.parent.bf=0,更新之后变成1
    145.                     node.parent.bf=1
    146.                     node=node.parent
    147.                     continue
    149.             #连接旋转后的子树
    150.             n.parent=g
    151.             if g: #g不是空
    152.                 if x==g.lchild:
    153.                     g.lchild=n
    154.                 else:
    155.                     g.rchild=n
    156.                 break
    157.             else:
    158.                 self.root=n
    159.                 break
    162. tree=AVLTree([9,8,7,6,5,4,3,2,1])
    163. tree.pre_order(tree.root)
    164. print("")
    165. tree.in_order(tree.root)