





from __future__ import annotations

import math
import random
from typing import Any



class      _SCREAMING_SNAKE_CASE		:







 '''simple docstring'''

 def __init__(self       :     int) ->None:



   '''simple docstring'''



   lowerCamelCase__:   list[Any]    						=[]
   lowerCamelCase__:   int    						=0
   lowerCamelCase__:   int    						=0

 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[Any]) ->bool:



   '''simple docstring'''



   return self.head == self.tail

 def 							SCREAMING_SNAKE_CASE_      (self       :     Any ,				UpperCAmelCase_       :     Any) ->None:



   '''simple docstring'''



   self.data.append(UpperCAmelCase_)
   lowerCamelCase__:   Tuple    						=self.tail + 1

 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[int]) ->Any:



   '''simple docstring'''



   lowerCamelCase__:   List[Any]    						=self.data[self.head]
   lowerCamelCase__:   Union[str, Any]    						=self.head + 1
   return ret

 def 							SCREAMING_SNAKE_CASE_      (self       :     Union[str, Any]) ->int:



   '''simple docstring'''



   return self.tail - self.head







 def 							SCREAMING_SNAKE_CASE_      (self       :     Union[str, Any]) ->None:



   '''simple docstring'''



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



class      _SCREAMING_SNAKE_CASE		:







 '''simple docstring'''

 def __init__(self       :     str ,				UpperCAmelCase_       :     Any) ->None:



   '''simple docstring'''



   lowerCamelCase__:   List[str]    						=data
   lowerCamelCase__:   MyNode | None    						=None
   lowerCamelCase__:   MyNode | None    						=None
   lowerCamelCase__:   int    						=1

 def 							SCREAMING_SNAKE_CASE_      (self       :     Union[str, Any]) ->Any:



   '''simple docstring'''



   return self.data

 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[int]) ->MyNode | None:



   '''simple docstring'''



   return self.left

 def 							SCREAMING_SNAKE_CASE_      (self       :     Tuple) ->MyNode | None:



   '''simple docstring'''



   return self.right

 def 							SCREAMING_SNAKE_CASE_      (self       :     int) ->int:



   '''simple docstring'''



   return self.height

 def 							SCREAMING_SNAKE_CASE_      (self       :     Tuple ,				UpperCAmelCase_       :     Any) ->None:



   '''simple docstring'''



   lowerCamelCase__:   Union[str, Any]    						=data

 def 							SCREAMING_SNAKE_CASE_      (self       :     Any ,				UpperCAmelCase_       :     MyNode | None) ->None:



   '''simple docstring'''



   lowerCamelCase__:   List[Any]    						=node

 def 							SCREAMING_SNAKE_CASE_      (self       :     Union[str, Any] ,				UpperCAmelCase_       :     MyNode | None) ->None:



   '''simple docstring'''



   lowerCamelCase__:   str    						=node







 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[int] ,				UpperCAmelCase_       :     int) ->None:



   '''simple docstring'''



   lowerCamelCase__:   Optional[int]    						=height





def   lowerCAmelCase_				( __a	):







  """simple docstring"""





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





def   lowerCAmelCase_				( __a			,					__a	):







  """simple docstring"""





  if a > b:
    return a
  return b





def   lowerCAmelCase_				( __a	):







  """simple docstring"""





  print("left rotation node:"			,					node.get_data()	)
  lowerCamelCase__:   Tuple    						=node.get_left()
  assert ret is not None
  node.set_left(ret.get_right()	)
  ret.set_right(__a	)
  lowerCamelCase__:   Dict    						=my_max(get_height(node.get_right()	)			,					get_height(node.get_left()	)	) + 1
  node.set_height(__a	)
  lowerCamelCase__:   List[Any]    						=my_max(get_height(ret.get_right()	)			,					get_height(ret.get_left()	)	) + 1
  ret.set_height(__a	)
  return ret





def   lowerCAmelCase_				( __a	):







  """simple docstring"""





  print("right rotation node:"			,					node.get_data()	)
  lowerCamelCase__:   int    						=node.get_right()
  assert ret is not None
  node.set_right(ret.get_left()	)
  ret.set_left(__a	)
  lowerCamelCase__:   str    						=my_max(get_height(node.get_right()	)			,					get_height(node.get_left()	)	) + 1
  node.set_height(__a	)
  lowerCamelCase__:   int    						=my_max(get_height(ret.get_right()	)			,					get_height(ret.get_left()	)	) + 1
  ret.set_height(__a	)
  return ret





def   lowerCAmelCase_				( __a	):







  """simple docstring"""





  lowerCamelCase__:   int    						=node.get_left()
  assert left_child is not None
  node.set_left(left_rotation(__a	)	)
  return right_rotation(__a	)





def   lowerCAmelCase_				( __a	):







  """simple docstring"""





  lowerCamelCase__:   List[Any]    						=node.get_right()
  assert right_child is not None
  node.set_right(right_rotation(__a	)	)
  return left_rotation(__a	)





def   lowerCAmelCase_				( __a			,					__a	):







  """simple docstring"""





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





def   lowerCAmelCase_				( __a	):







  """simple docstring"""





  while True:
    lowerCamelCase__:   Optional[int]    						=root.get_right()
    if right_child is None:
      break
    lowerCamelCase__:   int    						=right_child
  return root.get_data()





def   lowerCAmelCase_				( __a	):







  """simple docstring"""





  while True:
    lowerCamelCase__:   List[Any]    						=root.get_left()
    if left_child is None:
      break
    lowerCamelCase__:   Optional[int]    						=left_child
  return root.get_data()





def   lowerCAmelCase_				( __a			,					__a	):







  """simple docstring"""





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

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



class      _SCREAMING_SNAKE_CASE		:







 '''simple docstring'''

 def __init__(self       :     str) ->None:



   '''simple docstring'''



   lowerCamelCase__:   MyNode | None    						=None

 def 							SCREAMING_SNAKE_CASE_      (self       :     Any) ->int:



   '''simple docstring'''



   return get_height(self.root)

 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[Any] ,				UpperCAmelCase_       :     Any) ->None:



   '''simple docstring'''



   print("insert:" + str(UpperCAmelCase_))
   lowerCamelCase__:   List[Any]    						=insert_node(self.root ,				UpperCAmelCase_)

 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[int] ,				UpperCAmelCase_       :     Any) ->None:



   '''simple docstring'''



   print("delete:" + str(UpperCAmelCase_))
   if self.root is None:
     print("Tree is empty!")
     return
   lowerCamelCase__:   List[str]    						=del_node(self.root ,				UpperCAmelCase_)







 def __str__(self       :     Optional[Any] ,				) ->str:  # a level traversale, gives a more intuitive look on the tree



   '''simple docstring'''



   lowerCamelCase__:   Union[str, Any]    						=""
   lowerCamelCase__:   Any    						=MyQueue()
   q.push(self.root)
   lowerCamelCase__:   Optional[int]    						=self.get_height()
   if layer == 0:
     return output
   lowerCamelCase__:   Optional[int]    						=0
   while not q.is_empty():
     lowerCamelCase__:   Dict    						=q.pop()
     lowerCamelCase__:   List[Any]    						=" " * 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
     lowerCamelCase__:   Union[str, Any]    						=cnt + 1
     for i in range(100):
       if cnt == math.pow(2 ,				UpperCAmelCase_) - 1:
         lowerCamelCase__:   Any    						=layer - 1
         if layer == 0:
           output += "\n*************************************"
           return output
         output += "\n"
         break
   output += "\n*************************************"
   return output





def   lowerCAmelCase_				( ):







  """simple docstring"""





  import doctest

  doctest.testmod()


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








# Lint as: python3
import dataclasses
import re
from dataclasses import dataclass
from functools import total_ordering
from typing import Optional, Union


__A             =       re.compile(R"^(?P<major>\d+)" R"\.(?P<minor>\d+)" R"\.(?P<patch>\d+)$")



@total_ordering
@dataclass
class      _SCREAMING_SNAKE_CASE		:







 '''simple docstring'''
 lowercase_	=    42
 lowercase_	=    None
 lowercase_	=    None
 lowercase_	=    None
 lowercase_	=    None

 def 							SCREAMING_SNAKE_CASE_      (self       :     List[Any]) ->Tuple:



   '''simple docstring'''



   lowerCamelCase__						,      lowerCamelCase__						,      lowerCamelCase__:   List[str]    						=_str_to_version_tuple(self.version_str)

 def __repr__(self       :     Union[str, Any]) ->Union[str, Any]:



   '''simple docstring'''



   return F"""{self.tuple[0]}.{self.tuple[1]}.{self.tuple[2]}"""

 @property
 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[Any]) ->Optional[Any]:



   '''simple docstring'''



   return self.major, self.minor, self.patch

 def 							SCREAMING_SNAKE_CASE_      (self       :     Dict ,				UpperCAmelCase_       :     Tuple) ->Any:



   '''simple docstring'''



   if isinstance(UpperCAmelCase_ ,				UpperCAmelCase_):
     return Version(UpperCAmelCase_)
   elif isinstance(UpperCAmelCase_ ,				UpperCAmelCase_):
     return other
   raise TypeError(F"""{other} (type {type(UpperCAmelCase_)}) cannot be compared to version.""")

 def __eq__(self       :     Optional[Any] ,				UpperCAmelCase_       :     Tuple) ->List[str]:



   '''simple docstring'''



   try:
     lowerCamelCase__:   List[Any]    						=self._validate_operand(UpperCAmelCase_)
   except (TypeError, ValueError):
     return False
   else:
     return self.tuple == other.tuple

 def __lt__(self       :     Dict ,				UpperCAmelCase_       :     List[str]) ->Union[str, Any]:



   '''simple docstring'''



   lowerCamelCase__:   Tuple    						=self._validate_operand(UpperCAmelCase_)
   return self.tuple < other.tuple

 def __hash__(self       :     Any) ->Dict:



   '''simple docstring'''



   return hash(_version_tuple_to_str(self.tuple))

 @classmethod
 def 							SCREAMING_SNAKE_CASE_      (cls       :     Union[str, Any] ,				UpperCAmelCase_       :     Optional[Any]) ->Union[str, Any]:



   '''simple docstring'''



   lowerCamelCase__:   str    						={f.name for f in dataclasses.fields(cls)}
   return cls(**{k: v for k, v in dic.items() if k in field_names})







 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[int]) ->str:



   '''simple docstring'''



   return self.version_str





def   lowerCAmelCase_				( __a	)  ->	List[Any]:







  """simple docstring"""





  lowerCamelCase__:   Optional[int]    						=_VERSION_REG.match(__a	)
  if not res:
    raise ValueError(F"""Invalid version '{version_str}'. Format should be x.y.z with {{x,y,z}} being digits."""	)
  return tuple(int(__a	) for v in [res.group("major"	), res.group("minor"	), res.group("patch"	)]	)






def   lowerCAmelCase_				( __a	)  ->	Dict:







  """simple docstring"""





  return ".".join(str(__a	) for v in version_tuple	)

