
from __future__ import annotations

import math
import random
from typing import Any



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  list[Any]						=  []
    __a :  int						=  0
    __a :  int						=  0
   def       lowerCAmelCase			(self :					Optional[int]   ):
    return self.head == self.tail
   def       lowerCAmelCase			(self :					List[Any]					,				snake_case_ :					Any   ):
    self.data.append(snake_case_   )
    __a :  str						=  self.tail + 1
   def       lowerCAmelCase			(self :					Optional[int]   ):
    __a :  int						=  self.data[self.head]
    __a :  Union[str, Any]						=  self.head + 1
    return ret
   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    return self.tail - self.head







   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    print(self.data   )
    print('''**************'''   )
    print(self.data[self.head : self.tail]   )





class 		UpperCamelCase__  :
   def __init__(self :					List[str]					,				snake_case_ :					Any   ):
    __a :  List[str]						=  data
    __a :  MyNode | None						=  None
    __a :  MyNode | None						=  None
    __a :  int						=  1
   def       lowerCAmelCase			(self :					int   ):
    return self.data
   def       lowerCAmelCase			(self :					Dict   ):
    return self.left
   def       lowerCAmelCase			(self :					int   ):
    return self.right
   def       lowerCAmelCase			(self :					int   ):
    return self.height
   def       lowerCAmelCase			(self :					Optional[Any]					,				snake_case_ :					Any   ):
    __a :  Tuple						=  data
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					MyNode | None   ):
    __a :  Any						=  node
   def       lowerCAmelCase			(self :					Union[str, Any]					,				snake_case_ :					MyNode | None   ):
    __a :  List[str]						=  node







   def       lowerCAmelCase			(self :					Optional[int]					,				snake_case_ :					int   ):
    __a :  Union[str, Any]						=  height





def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ):
 if node is None:
  return 0
 return node.get_height()




def    __UpperCamelCase     (				lowerCAmelCase__							:				int  ,   lowerCAmelCase__							:				int  ):
 if a > b:
  return a
 return b




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''left rotation node:'''  ,   node.get_data()  )
 __a :  str						=  node.get_left()
 assert ret is not None
 node.set_left(ret.get_right()  )
 ret.set_right(lowerCAmelCase__  )
 __a :  List[Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''right rotation node:'''  ,   node.get_data()  )
 __a :  List[Any]						=  node.get_right()
 assert ret is not None
 node.set_right(ret.get_left()  )
 ret.set_left(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  List[str]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Union[str, Any]						=  node.get_left()
 assert left_child is not None
 node.set_left(left_rotation(lowerCAmelCase__  )  )
 return right_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Optional[int]						=  node.get_right()
 assert right_child is not None
 node.set_right(right_rotation(lowerCAmelCase__  )  )
 return left_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ,   lowerCAmelCase__							:				Any  ):
 if node is None:
  return MyNode(lowerCAmelCase__  )
 if data < node.get_data():
  node.set_left(insert_node(node.get_left()  ,   lowerCAmelCase__  )  )
  if (
      get_height(node.get_left()  ) - get_height(node.get_right()  ) == 2
  ):  # an unbalance detected
   __a :  Tuple						=  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
    __a :  str						=  right_rotation(lowerCAmelCase__  )
   else:
    __a :  Dict						=  lr_rotation(lowerCAmelCase__  )
 else:
  node.set_right(insert_node(node.get_right()  ,   lowerCAmelCase__  )  )
  if get_height(node.get_right()  ) - get_height(node.get_left()  ) == 2:
   __a :  Dict						=  node.get_right()
   assert right_child is not None
   if data < right_child.get_data():
    __a :  str						=  rl_rotation(lowerCAmelCase__  )
   else:
    __a :  Tuple						=  left_rotation(lowerCAmelCase__  )
 __a :  Any						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 return node




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Union[str, Any]						=  root.get_right()
  if right_child is None:
   break
  __a :  str						=  right_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Optional[int]						=  root.get_left()
  if left_child is None:
   break
  __a :  int						=  left_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ,   lowerCAmelCase__							:				Any  ):
 __a :  Optional[Any]						=  root.get_left()
 __a :  List[str]						=  root.get_right()
 if root.get_data() == data:
  if left_child is not None and right_child is not None:
   __a :  str						=  get_left_most(lowerCAmelCase__  )
   root.set_data(lowerCAmelCase__  )
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
  elif left_child is not None:
   __a :  int						=  left_child
  elif right_child is not None:
   __a :  List[Any]						=  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(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
 else:  # root.get_data() < data
  if right_child is None:
   return root
  else:
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )

 if get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == 2:
  assert right_child is not None
  if get_height(right_child.get_right()  ) > get_height(right_child.get_left()  ):
   __a :  List[Any]						=  left_rotation(lowerCAmelCase__  )
  else:
   __a :  Union[str, Any]						=  rl_rotation(lowerCAmelCase__  )
 elif get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == -2:
  assert left_child is not None
  if get_height(left_child.get_left()  ) > get_height(left_child.get_right()  ):
   __a :  int						=  right_rotation(lowerCAmelCase__  )
  else:
   __a :  Tuple						=  lr_rotation(lowerCAmelCase__  )
 __a :  str						=  my_max(get_height(root.get_right()  )  ,   get_height(root.get_left()  )  ) + 1
 root.set_height(lowerCAmelCase__  )
 return root



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  MyNode | None						=  None
   def       lowerCAmelCase			(self :					List[Any]   ):
    return get_height(self.root   )
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					Any   ):
    print('''insert:''' + str(snake_case_   )   )
    __a :  List[Any]						=  insert_node(self.root					,				snake_case_   )
   def       lowerCAmelCase			(self :					Dict					,				snake_case_ :					Any   ):
    print('''delete:''' + str(snake_case_   )   )
    if self.root is None:
     print('''Tree is empty!'''   )
     return
    __a :  Union[str, Any]						=  del_node(self.root					,				snake_case_   )







   def __str__(self :					List[str]					,				):  # a level traversale, gives a more intuitive look on the tree
    __a :  Union[str, Any]						=  ''''''
    __a :  int						=  MyQueue()
    q.push(self.root   )
    __a :  List[str]						=  self.get_height()
    if layer == 0:
     return output
    __a :  List[Any]						=  0
    while not q.is_empty():
     __a :  List[str]						=  q.pop()
     __a :  Optional[int]						=  ''' ''' * int(math.pow(2					,				layer - 1   )   )
     output += space
     if node is None:
      output += "*"
      q.push(snake_case_   )
      q.push(snake_case_   )
     else:
      output += str(node.get_data()   )
      q.push(node.get_left()   )
      q.push(node.get_right()   )
     output += space
     __a :  int						=  cnt + 1
     for i in range(1_0_0   ):
      if cnt == math.pow(2					,				snake_case_   ) - 1:
       __a :  str						=  layer - 1
       if layer == 0:
        output += "\n*************************************"
        return output
       output += "\n"
       break
    output += "\n*************************************"
    return output





def    __UpperCamelCase     (				):
 import doctest

 doctest.testmod()


if __name__ == "__main__":
      _test()
      lowercase__       =AVLtree()
      lowercase__       =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))


from __future__ import annotations

import math
import random
from typing import Any



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  list[Any]						=  []
    __a :  int						=  0
    __a :  int						=  0
   def       lowerCAmelCase			(self :					Optional[int]   ):
    return self.head == self.tail
   def       lowerCAmelCase			(self :					List[Any]					,				snake_case_ :					Any   ):
    self.data.append(snake_case_   )
    __a :  str						=  self.tail + 1
   def       lowerCAmelCase			(self :					Optional[int]   ):
    __a :  int						=  self.data[self.head]
    __a :  Union[str, Any]						=  self.head + 1
    return ret
   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    return self.tail - self.head







   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    print(self.data   )
    print('''**************'''   )
    print(self.data[self.head : self.tail]   )





class 		UpperCamelCase__  :
   def __init__(self :					List[str]					,				snake_case_ :					Any   ):
    __a :  List[str]						=  data
    __a :  MyNode | None						=  None
    __a :  MyNode | None						=  None
    __a :  int						=  1
   def       lowerCAmelCase			(self :					int   ):
    return self.data
   def       lowerCAmelCase			(self :					Dict   ):
    return self.left
   def       lowerCAmelCase			(self :					int   ):
    return self.right
   def       lowerCAmelCase			(self :					int   ):
    return self.height
   def       lowerCAmelCase			(self :					Optional[Any]					,				snake_case_ :					Any   ):
    __a :  Tuple						=  data
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					MyNode | None   ):
    __a :  Any						=  node
   def       lowerCAmelCase			(self :					Union[str, Any]					,				snake_case_ :					MyNode | None   ):
    __a :  List[str]						=  node







   def       lowerCAmelCase			(self :					Optional[int]					,				snake_case_ :					int   ):
    __a :  Union[str, Any]						=  height





def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ):
 if node is None:
  return 0
 return node.get_height()




def    __UpperCamelCase     (				lowerCAmelCase__							:				int  ,   lowerCAmelCase__							:				int  ):
 if a > b:
  return a
 return b




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''left rotation node:'''  ,   node.get_data()  )
 __a :  str						=  node.get_left()
 assert ret is not None
 node.set_left(ret.get_right()  )
 ret.set_right(lowerCAmelCase__  )
 __a :  List[Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''right rotation node:'''  ,   node.get_data()  )
 __a :  List[Any]						=  node.get_right()
 assert ret is not None
 node.set_right(ret.get_left()  )
 ret.set_left(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  List[str]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Union[str, Any]						=  node.get_left()
 assert left_child is not None
 node.set_left(left_rotation(lowerCAmelCase__  )  )
 return right_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Optional[int]						=  node.get_right()
 assert right_child is not None
 node.set_right(right_rotation(lowerCAmelCase__  )  )
 return left_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ,   lowerCAmelCase__							:				Any  ):
 if node is None:
  return MyNode(lowerCAmelCase__  )
 if data < node.get_data():
  node.set_left(insert_node(node.get_left()  ,   lowerCAmelCase__  )  )
  if (
      get_height(node.get_left()  ) - get_height(node.get_right()  ) == 2
  ):  # an unbalance detected
   __a :  Tuple						=  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
    __a :  str						=  right_rotation(lowerCAmelCase__  )
   else:
    __a :  Dict						=  lr_rotation(lowerCAmelCase__  )
 else:
  node.set_right(insert_node(node.get_right()  ,   lowerCAmelCase__  )  )
  if get_height(node.get_right()  ) - get_height(node.get_left()  ) == 2:
   __a :  Dict						=  node.get_right()
   assert right_child is not None
   if data < right_child.get_data():
    __a :  str						=  rl_rotation(lowerCAmelCase__  )
   else:
    __a :  Tuple						=  left_rotation(lowerCAmelCase__  )
 __a :  Any						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 return node




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Union[str, Any]						=  root.get_right()
  if right_child is None:
   break
  __a :  str						=  right_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Optional[int]						=  root.get_left()
  if left_child is None:
   break
  __a :  int						=  left_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ,   lowerCAmelCase__							:				Any  ):
 __a :  Optional[Any]						=  root.get_left()
 __a :  List[str]						=  root.get_right()
 if root.get_data() == data:
  if left_child is not None and right_child is not None:
   __a :  str						=  get_left_most(lowerCAmelCase__  )
   root.set_data(lowerCAmelCase__  )
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
  elif left_child is not None:
   __a :  int						=  left_child
  elif right_child is not None:
   __a :  List[Any]						=  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(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
 else:  # root.get_data() < data
  if right_child is None:
   return root
  else:
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )

 if get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == 2:
  assert right_child is not None
  if get_height(right_child.get_right()  ) > get_height(right_child.get_left()  ):
   __a :  List[Any]						=  left_rotation(lowerCAmelCase__  )
  else:
   __a :  Union[str, Any]						=  rl_rotation(lowerCAmelCase__  )
 elif get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == -2:
  assert left_child is not None
  if get_height(left_child.get_left()  ) > get_height(left_child.get_right()  ):
   __a :  int						=  right_rotation(lowerCAmelCase__  )
  else:
   __a :  Tuple						=  lr_rotation(lowerCAmelCase__  )
 __a :  str						=  my_max(get_height(root.get_right()  )  ,   get_height(root.get_left()  )  ) + 1
 root.set_height(lowerCAmelCase__  )
 return root



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  MyNode | None						=  None
   def       lowerCAmelCase			(self :					List[Any]   ):
    return get_height(self.root   )
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					Any   ):
    print('''insert:''' + str(snake_case_   )   )
    __a :  List[Any]						=  insert_node(self.root					,				snake_case_   )
   def       lowerCAmelCase			(self :					Dict					,				snake_case_ :					Any   ):
    print('''delete:''' + str(snake_case_   )   )
    if self.root is None:
     print('''Tree is empty!'''   )
     return
    __a :  Union[str, Any]						=  del_node(self.root					,				snake_case_   )







   def __str__(self :					List[str]					,				):  # a level traversale, gives a more intuitive look on the tree
    __a :  Union[str, Any]						=  ''''''
    __a :  int						=  MyQueue()
    q.push(self.root   )
    __a :  List[str]						=  self.get_height()
    if layer == 0:
     return output
    __a :  List[Any]						=  0
    while not q.is_empty():
     __a :  List[str]						=  q.pop()
     __a :  Optional[int]						=  ''' ''' * int(math.pow(2					,				layer - 1   )   )
     output += space
     if node is None:
      output += "*"
      q.push(snake_case_   )
      q.push(snake_case_   )
     else:
      output += str(node.get_data()   )
      q.push(node.get_left()   )
      q.push(node.get_right()   )
     output += space
     __a :  int						=  cnt + 1
     for i in range(1_0_0   ):
      if cnt == math.pow(2					,				snake_case_   ) - 1:
       __a :  str						=  layer - 1
       if layer == 0:
        output += "\n*************************************"
        return output
       output += "\n"
       break
    output += "\n*************************************"
    return output





def    __UpperCamelCase     (				):
 import doctest

 doctest.testmod()


if __name__ == "__main__":
      _test()
      lowercase__       =AVLtree()
      lowercase__       =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))
