

from __future__ import annotations

import math
import random
from typing import Any







class 						__magic_name__			:

   '''simple docstring'''




   def __init__(				self       )							->    None:






     """simple docstring"""






     a__  =[]
     a__  =0
     a__  =0



   def  _UpperCAmelCase (				self       )							->    bool:






     """simple docstring"""






     return self.head == self.tail



   def  _UpperCAmelCase (				self,    lowercase_       )							->    None:






     """simple docstring"""






     self.data.append(lowercase_       )
     a__  =self.tail + 1



   def  _UpperCAmelCase (				self       )							->    Any:






     """simple docstring"""






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



   def  _UpperCAmelCase (				self       )							->    int:






     """simple docstring"""






     return self.tail - self.head



   def  _UpperCAmelCase (				self       )							->    None:






     """simple docstring"""






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







class 						__magic_name__			:

   '''simple docstring'''




   def __init__(				self,    lowercase_       )							->    None:






     """simple docstring"""






     a__  =data
     a__  =None
     a__  =None
     a__  =1



   def  _UpperCAmelCase (				self       )							->    Any:






     """simple docstring"""






     return self.data



   def  _UpperCAmelCase (				self       )							->    MyNode | None:






     """simple docstring"""






     return self.left



   def  _UpperCAmelCase (				self       )							->    MyNode | None:






     """simple docstring"""






     return self.right



   def  _UpperCAmelCase (				self       )							->    int:






     """simple docstring"""






     return self.height



   def  _UpperCAmelCase (				self,    lowercase_       )							->    None:






     """simple docstring"""






     a__  =data



   def  _UpperCAmelCase (				self,    lowercase_       )							->    None:






     """simple docstring"""






     a__  =node



   def  _UpperCAmelCase (				self,    lowercase_       )							->    None:






     """simple docstring"""






     a__  =node



   def  _UpperCAmelCase (				self,    lowercase_       )							->    None:






     """simple docstring"""






     a__  =height





def 			UpperCAmelCase__				(			_A      : MyNode | None							):





  '''simple docstring'''







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




def 			UpperCAmelCase__				(			_A      : int	,      _A      : int							):





  '''simple docstring'''







  if a > b:
    return a
  return b




def 			UpperCAmelCase__				(			_A      : MyNode							):





  '''simple docstring'''







  print('''left rotation node:'''	,      node.get_data()							)
  a__  =node.get_left()
  assert ret is not None
  node.set_left(ret.get_right()							)
  ret.set_right(_A							)
  a__  =my_max(get_height(node.get_right()							)	,      get_height(node.get_left()							)							) + 1
  node.set_height(_A							)
  a__  =my_max(get_height(ret.get_right()							)	,      get_height(ret.get_left()							)							) + 1
  ret.set_height(_A							)
  return ret




def 			UpperCAmelCase__				(			_A      : MyNode							):





  '''simple docstring'''







  print('''right rotation node:'''	,      node.get_data()							)
  a__  =node.get_right()
  assert ret is not None
  node.set_right(ret.get_left()							)
  ret.set_left(_A							)
  a__  =my_max(get_height(node.get_right()							)	,      get_height(node.get_left()							)							) + 1
  node.set_height(_A							)
  a__  =my_max(get_height(ret.get_right()							)	,      get_height(ret.get_left()							)							) + 1
  ret.set_height(_A							)
  return ret




def 			UpperCAmelCase__				(			_A      : MyNode							):





  '''simple docstring'''







  a__  =node.get_left()
  assert left_child is not None
  node.set_left(left_rotation(_A							)							)
  return right_rotation(_A							)




def 			UpperCAmelCase__				(			_A      : MyNode							):





  '''simple docstring'''







  a__  =node.get_right()
  assert right_child is not None
  node.set_right(right_rotation(_A							)							)
  return left_rotation(_A							)




def 			UpperCAmelCase__				(			_A      : MyNode | None	,      _A      : Any							):





  '''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
      a__  =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__  =right_rotation(_A							)
      else:
        a__  =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:
      a__  =node.get_right()
      assert right_child is not None
      if data < right_child.get_data():
        a__  =rl_rotation(_A							)
      else:
        a__  =left_rotation(_A							)
  a__  =my_max(get_height(node.get_right()							)	,      get_height(node.get_left()							)							) + 1
  node.set_height(_A							)
  return node




def 			UpperCAmelCase__				(			_A      : MyNode							):





  '''simple docstring'''







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




def 			UpperCAmelCase__				(			_A      : MyNode							):





  '''simple docstring'''







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




def 			UpperCAmelCase__				(			_A      : MyNode	,      _A      : Any							):





  '''simple docstring'''







  a__  =root.get_left()
  a__  =root.get_right()
  if root.get_data() == data:
    if left_child is not None and right_child is not None:
      a__  =get_left_most(_A							)
      root.set_data(_A							)
      root.set_right(del_node(_A	,      _A							)							)
    elif left_child is not None:
      a__  =left_child
    elif right_child is not None:
      a__  =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()							):
      a__  =left_rotation(_A							)
    else:
      a__  =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()							):
      a__  =right_rotation(_A							)
    else:
      a__  =lr_rotation(_A							)
  a__  =my_max(get_height(root.get_right()							)	,      get_height(root.get_left()							)							) + 1
  root.set_height(_A							)
  return root







class 						__magic_name__			:

   '''simple docstring'''




   def __init__(				self       )							->    None:






     """simple docstring"""






     a__  =None



   def  _UpperCAmelCase (				self       )							->    int:






     """simple docstring"""






     return get_height(self.root       )



   def  _UpperCAmelCase (				self,    lowercase_       )							->    None:






     """simple docstring"""






     print('''insert:''' + str(lowercase_       )       )
     a__  =insert_node(self.root,    lowercase_       )



   def  _UpperCAmelCase (				self,    lowercase_       )							->    None:






     """simple docstring"""






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



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






     """simple docstring"""






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





def 			UpperCAmelCase__				(			):





  '''simple docstring'''







  import doctest

  doctest.testmod()


if __name__ == "__main__":
       _test()
       lowerCamelCase           =					AVLtree()
       lowerCamelCase           =					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 			UpperCAmelCase__				(			_A      : dict							):





  '''simple docstring'''







  a__  =set()
  # To detect a back edge, keep track of vertices currently in the recursion stack
  a__  =set()
  return any(
      node not in visited and depth_first_search(_A	,      _A	,      _A	,      _A							)
      for node in graph							)




def 			UpperCAmelCase__				(			_A      : dict	,      _A      : int	,      _A      : set	,      _A      : set							):





  '''simple docstring'''







  visited.add(_A							)
  rec_stk.add(_A							)

  for node in graph[vertex]:
    if node not in visited:
      if depth_first_search(_A	,      _A	,      _A	,      _A							):
        return True
    elif node in rec_stk:
      return True

    # The node needs to be removed from recursion stack before function ends
  rec_stk.remove(_A							)
  return False


if __name__ == "__main__":
       from doctest import testmod

       testmod()
