class AVLNode(object):

     def __init__(self,data):

         self.data = data

         self.lchild = None

         self.rchild = None

         self.parent = None

         self.bf = 0

 class AVLTree(object)

     def __init__(self,li=None)

         self.root = None

         if li:

             for val in li:

                 self.insert(self.root,val)

     def insert(self,node,val):

         if not node:

             node = AVLNode(val)

         elif val < node.data:

             node.lchild = self.insert(node.lchild,val)

             node.lchild.parent = node

         elif val > node.data:

             node.rchild = self.insert(node.rchild,val)

             node.rchild.parent = node

         return node

     def rorate_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 rorate_right(self,p,c):

         s2 = c.rchild

         p.lchild = s2

         if s2:

             s2.parent

         c.rchild = p

         p.parent = c

         p.bf = 0

         c.bf = 0

         return c

     def rotate_right_left(self,p,c):

         g = c.lchild

         #右旋

         s3 = g.rchild #1.把右孩子拿出来

         c.lchild = s3 #2.右孩子交给 C

         if s3:

             s3.parent = c

         g.rchild = c #3.链接右孩子

         c.parent = g #4.链接父结点

         #左旋

         s2 = g.lchild

         p.rchild = s2

         if s2:

             s2.parent = p

         g.lchild = p

         p.parent = g

         #更新bf

         if g.bf > 0: #插入到s3 #是指刚插入节点的g的平衡值

             p.bf = -1

             c.bf = 0

         elif g.bf < 0: #插入到s2

             p.bf = 0

             c.bf = 1

         else:  #插入的是G本身

             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

         #更新bf

         if g.bf < 0: #插入到s2

             p.bf = 1

             c.bf = 0

         elif g.bf > 0: #插入到s3

             p.bf = 0

             c.bf = -1

         else:  #插入的是G本身

             p.bf = 0

             c.bf = 0

         g.bf = 0

         return g

     def insert_no_rec(self,val):

         #1.插入

         p = self.root

         if not p:

             self.root = AVLNode(val)

             return

         while True:

             if val < p.data:

                 if p.lchild: #左孩子存在

                     p = p.lchild

                 else:  #左孩子不存在

                     p.lchild = AVLNode(val)

                     p.lchild.parent = p

                     node = p.lchild #node 存储的就是插入的节点

                     break

             else val > p.data:

                 if p.rchild:

                     p = p.rchild

                 else:

                     p.rchild = AVLNode(val)

                     p.rchild.parent = p

                     node = p.rchild

                     break

             else: #等于 #同样的元素不多次插入

                   #avl尽量不允许两个相同的数插入

                 return 

         #2.更新balance factor

         while node.parent: #node.parent 不为空时

             if node.parent.lchild == node: #传递节点是在左子树,左子树更沉了

                 #第一乱循环,更新node.parent的bf -= 1

                 if node.parent.bf < 0: #原来node.parent.bf == -1 (更新后会变成-2)

                     # 做旋转

                     # 看node哪边沉

                     head = node.parent.parent #为了链接旋转之后的子树

                     tmp = node.parent #旋转前的子树的根

                     if node.bf > 0:

                         n = self.rotate_left_right(node.parent,node)

                     else:

                         n = self.rorate_right(node.parent,node)

                 elif node.parent.bf > 0: #原来node.parent.bf == 1 (更新后变成0)

                     node.parent.bf = 0 #平衡,即可以不需要确认父亲节点

                     break

                 else: #原来node.parent.bf = 0,更新之后变成-1

                     node.parent.bf = -1

                     node = node.parent

                     continue

             else: #传递节点是在右子树,右子树更沉了

                 if node.parent.bf > 0:

                     head = node.parent.parent

                     tmp = node.parent

                     if node.bf < 0:

                         n = self.rotate_right_left(node.parent,node)

                     else:

                         n = self.rorate_left(node.parent,node)

                 elif node.parent.bf < 0:

                     node.parent.bf = 0

                     break

                 else:

                     node.parent.bf = 1

                     node = node.parent

                     continue

             #3.链接旋转后的子树(只有做了旋转之后才会到这一步)

             n.parent = head

             if head: #head不是空

                 if tmp == head.lchild:

                     head.lchild = n

                 else:

                     head.rchild = n

                 break

             else:

                 self.root = n

                 break