





from __future__ import annotations

import math
import random
from typing import Any

class  __A:

     def __init__(      self      ):





            """simple docstring"""

            _UpperCamelCase              =						[]
            _UpperCamelCase              =						0
            _UpperCamelCase              =						0

     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            return self.head == self.tail

     def 	_UpperCamelCase     (      self,       A      ):





            """simple docstring"""

            self.data.append(UpperCamelCase__      )
            _UpperCamelCase              =						self.tail + 1

     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            _UpperCamelCase              =						self.data[self.head]
            _UpperCamelCase              =						self.head + 1
            return ret

     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            return self.tail - self.head



     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            print(self.data      )
            print('''**************'''      )
            print(self.data[self.head : self.tail]      )






class  __A:

     def __init__(      self,       A      ):





            """simple docstring"""

            _UpperCamelCase              =						data
            _UpperCamelCase              =						None
            _UpperCamelCase              =						None
            _UpperCamelCase              =						1

     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            return self.data

     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            return self.left

     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            return self.right

     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            return self.height

     def 	_UpperCamelCase     (      self,       A      ):





            """simple docstring"""

            _UpperCamelCase              =						data

     def 	_UpperCamelCase     (      self,       A      ):





            """simple docstring"""

            _UpperCamelCase              =						node

     def 	_UpperCamelCase     (      self,       A      ):





            """simple docstring"""

            _UpperCamelCase              =						node



     def 	_UpperCamelCase     (      self,       A      ):





            """simple docstring"""

            _UpperCamelCase              =						height






def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):







       if node is None:
              return 0
       return node.get_height()


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase    ,       lowerCAmelCase					):







       if a > b:
              return a
       return b


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):
       print('''left rotation node:'''    ,       node.get_data()					)
       _UpperCamelCase              =						node.get_left()
       assert ret is not None
       node.set_left(ret.get_right()					)
       ret.set_right(__UpperCamelCase					)
       _UpperCamelCase              =						my_max(get_height(node.get_right()					)    ,       get_height(node.get_left()					)					) + 1
       node.set_height(__UpperCamelCase					)
       _UpperCamelCase              =						my_max(get_height(ret.get_right()					)    ,       get_height(ret.get_left()					)					) + 1
       ret.set_height(__UpperCamelCase					)
       return ret


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):
       print('''right rotation node:'''    ,       node.get_data()					)
       _UpperCamelCase              =						node.get_right()
       assert ret is not None
       node.set_right(ret.get_left()					)
       ret.set_left(__UpperCamelCase					)
       _UpperCamelCase              =						my_max(get_height(node.get_right()					)    ,       get_height(node.get_left()					)					) + 1
       node.set_height(__UpperCamelCase					)
       _UpperCamelCase              =						my_max(get_height(ret.get_right()					)    ,       get_height(ret.get_left()					)					) + 1
       ret.set_height(__UpperCamelCase					)
       return ret


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):
       _UpperCamelCase              =						node.get_left()
       assert left_child is not None
       node.set_left(left_rotation(__UpperCamelCase					)					)
       return right_rotation(__UpperCamelCase					)


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):
       _UpperCamelCase              =						node.get_right()
       assert right_child is not None
       node.set_right(right_rotation(__UpperCamelCase					)					)
       return left_rotation(__UpperCamelCase					)


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase    ,       lowerCAmelCase					):







       if node is None:
              return MyNode(__UpperCamelCase					)
       if data < node.get_data():
              node.set_left(insert_node(node.get_left()    ,       __UpperCamelCase					)					)
              if (
                  get_height(node.get_left()					) - get_height(node.get_right()					) == 2
              ):  # an unbalance detected
                     _UpperCamelCase              =						node.get_left()
                     assert left_child is not None
                     if (
                         data < left_child.get_data()
                     ):  # new node is the left child of the left child
                            _UpperCamelCase              =						right_rotation(__UpperCamelCase					)
                     else:
                            _UpperCamelCase              =						lr_rotation(__UpperCamelCase					)
       else:
              node.set_right(insert_node(node.get_right()    ,       __UpperCamelCase					)					)
              if get_height(node.get_right()					) - get_height(node.get_left()					) == 2:
                     _UpperCamelCase              =						node.get_right()
                     assert right_child is not None
                     if data < right_child.get_data():
                            _UpperCamelCase              =						rl_rotation(__UpperCamelCase					)
                     else:
                            _UpperCamelCase              =						left_rotation(__UpperCamelCase					)
       _UpperCamelCase              =						my_max(get_height(node.get_right()					)    ,       get_height(node.get_left()					)					) + 1
       node.set_height(__UpperCamelCase					)
       return node


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):







       while True:
              _UpperCamelCase              =						root.get_right()
              if right_child is None:
                     break
              _UpperCamelCase              =						right_child
       return root.get_data()


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):







       while True:
              _UpperCamelCase              =						root.get_left()
              if left_child is None:
                     break
              _UpperCamelCase              =						left_child
       return root.get_data()


def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase    ,       lowerCAmelCase					):
       _UpperCamelCase              =						root.get_left()
       _UpperCamelCase              =						root.get_right()
       if root.get_data() == data:
              if left_child is not None and right_child is not None:
                     _UpperCamelCase              =						get_left_most(__UpperCamelCase					)
                     root.set_data(__UpperCamelCase					)
                     root.set_right(del_node(__UpperCamelCase    ,       __UpperCamelCase					)					)
              elif left_child is not None:
                     _UpperCamelCase              =						left_child
              elif right_child is not None:
                     _UpperCamelCase              =						right_child
              else:
                     return None
       elif root.get_data() > data:
              if left_child is None:
                     print('''No such data'''					)
                     return root
              else:
                     root.set_left(del_node(__UpperCamelCase    ,       __UpperCamelCase					)					)
       else:  # root.get_data() < data
              if right_child is None:
                     return root
              else:
                     root.set_right(del_node(__UpperCamelCase    ,       __UpperCamelCase					)					)

       if get_height(__UpperCamelCase					) - get_height(__UpperCamelCase					) == 2:
              assert right_child is not None
              if get_height(right_child.get_right()					) > get_height(right_child.get_left()					):
                     _UpperCamelCase              =						left_rotation(__UpperCamelCase					)
              else:
                     _UpperCamelCase              =						rl_rotation(__UpperCamelCase					)
       elif get_height(__UpperCamelCase					) - get_height(__UpperCamelCase					) == -2:
              assert left_child is not None
              if get_height(left_child.get_left()					) > get_height(left_child.get_right()					):
                     _UpperCamelCase              =						right_rotation(__UpperCamelCase					)
              else:
                     _UpperCamelCase              =						lr_rotation(__UpperCamelCase					)
       _UpperCamelCase              =						my_max(get_height(root.get_right()					)    ,       get_height(root.get_left()					)					) + 1
       root.set_height(__UpperCamelCase					)
       return root

class  __A:

     def __init__(      self      ):





            """simple docstring"""

            _UpperCamelCase              =						None

     def 	_UpperCamelCase     (      self      ):





            """simple docstring"""

            return get_height(self.root      )

     def 	_UpperCamelCase     (      self,       A      ):





            """simple docstring"""

            print('''insert:''' + str(UpperCamelCase__      )      )
            _UpperCamelCase              =						insert_node(self.root,       UpperCamelCase__      )

     def 	_UpperCamelCase     (      self,       A      ):





            """simple docstring"""

            print('''delete:''' + str(UpperCamelCase__      )      )
            if self.root is None:
                   print('''Tree is empty!'''      )
                   return
            _UpperCamelCase              =						del_node(self.root,       UpperCamelCase__      )



     def __str__(      self,       ):  # a level traversale, gives a more intuitive look on the tree





            """simple docstring"""

            _UpperCamelCase              =						''''''
            _UpperCamelCase              =						MyQueue()
            q.push(self.root      )
            _UpperCamelCase              =						self.get_height()
            if layer == 0:
                   return output
            _UpperCamelCase              =						0
            while not q.is_empty():
                   _UpperCamelCase              =						q.pop()
                   _UpperCamelCase              =						''' ''' * int(math.pow(2,       layer - 1      )      )
                   output += space
                   if node is None:
                          output += "*"
                          q.push(UpperCamelCase__      )
                          q.push(UpperCamelCase__      )
                   else:
                          output += str(node.get_data()      )
                          q.push(node.get_left()      )
                          q.push(node.get_right()      )
                   output += space
                   _UpperCamelCase              =						cnt + 1
                   for i in range(100      ):
                          if cnt == math.pow(2,       UpperCamelCase__      ) - 1:
                                 _UpperCamelCase              =						layer - 1
                                 if layer == 0:
                                        output += "\n*************************************"
                                        return output
                                 output += "\n"
                                 break
            output += "\n*************************************"
            return output






def     SCREAMING_SNAKE_CASE			(      ):
       import doctest

       doctest.testmod()


if __name__ == "__main__":
   _test()
   lowercase    : List[str]    	=  AVLtree()
   lowercase    : Optional[Any]    	=  list(range(10))
   random.shuffle(lst)
   for i in lst:
      t.insert(i)
      print(str(t))
   random.shuffle(lst)
   for i in lst:
      t.del_node(i)
      print(str(t))













def     SCREAMING_SNAKE_CASE			(      lowerCAmelCase					):
       _UpperCamelCase              =						0
       for ch in input_str:
              _UpperCamelCase              =						ord(lowerCAmelCase					)
              _UpperCamelCase              =						pow(2    ,       lowerCAmelCase					)

              # If we already turned on bit for current character's unicode
              if bitmap >> ch_unicode & 1 == 1:
                     return False
              bitmap |= ch_bit_index_on
       return True


if __name__ == "__main__":
       import doctest

       doctest.testmod()






