




'''simple docstring'''



from __future__ import annotations

import math
import random
from typing import Any







class 		lowercase_   :


   """simple docstring"""

   def __init__(   self :     List[str]   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				[]
      _SCREAMING_SNAKE_CASE	=				0
      _SCREAMING_SNAKE_CASE	=				0



   def 							lowerCAmelCase_      (   self :     Any   ):

      """simple docstring"""
      return self.head == self.tail



   def 							lowerCAmelCase_      (   self :     Tuple  ,				__lowerCamelCase :     Any   ):

      """simple docstring"""
      self.data.append(__lowerCamelCase   )
      _SCREAMING_SNAKE_CASE	=				self.tail + 1



   def 							lowerCAmelCase_      (   self :     Optional[Any]   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				self.data[self.head]
      _SCREAMING_SNAKE_CASE	=				self.head + 1
      return ret



   def 							lowerCAmelCase_      (   self :     Any   ):

      """simple docstring"""
      return self.tail - self.head



   def 							lowerCAmelCase_      (   self :     Any   ):

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







class 		lowercase_   :


   """simple docstring"""

   def __init__(   self :     Optional[int]  ,				__lowerCamelCase :     Any   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				data
      _SCREAMING_SNAKE_CASE	=				None
      _SCREAMING_SNAKE_CASE	=				None
      _SCREAMING_SNAKE_CASE	=				1



   def 							lowerCAmelCase_      (   self :     List[Any]   ):

      """simple docstring"""
      return self.data



   def 							lowerCAmelCase_      (   self :     List[str]   ):

      """simple docstring"""
      return self.left



   def 							lowerCAmelCase_      (   self :     int   ):

      """simple docstring"""
      return self.right



   def 							lowerCAmelCase_      (   self :     Tuple   ):

      """simple docstring"""
      return self.height



   def 							lowerCAmelCase_      (   self :     Any  ,				__lowerCamelCase :     Any   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				data



   def 							lowerCAmelCase_      (   self :     Union[str, Any]  ,				__lowerCamelCase :     MyNode | None   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				node



   def 							lowerCAmelCase_      (   self :     Optional[int]  ,				__lowerCamelCase :     MyNode | None   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				node



   def 							lowerCAmelCase_      (   self :     Optional[Any]  ,				__lowerCamelCase :     int   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				height


def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode | None  )			->			int:
   if node is None:
      return 0
   return node.get_height()
def 			SCREAMING_SNAKE_CASE_			(							__A    :			int	,					__A    :			int  )			->			int:
   if a > b:
      return a
   return b
def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode  )			->			MyNode:
   print("left rotation node:"	,					node.get_data()  )
   _SCREAMING_SNAKE_CASE	=				node.get_left()
   assert ret is not None
   node.set_left(ret.get_right()  )
   ret.set_right(__A  )
   _SCREAMING_SNAKE_CASE	=				my_max(get_height(node.get_right()  )	,					get_height(node.get_left()  )  ) + 1
   node.set_height(__A  )
   _SCREAMING_SNAKE_CASE	=				my_max(get_height(ret.get_right()  )	,					get_height(ret.get_left()  )  ) + 1
   ret.set_height(__A  )
   return ret
def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode  )			->			MyNode:
   print("right rotation node:"	,					node.get_data()  )
   _SCREAMING_SNAKE_CASE	=				node.get_right()
   assert ret is not None
   node.set_right(ret.get_left()  )
   ret.set_left(__A  )
   _SCREAMING_SNAKE_CASE	=				my_max(get_height(node.get_right()  )	,					get_height(node.get_left()  )  ) + 1
   node.set_height(__A  )
   _SCREAMING_SNAKE_CASE	=				my_max(get_height(ret.get_right()  )	,					get_height(ret.get_left()  )  ) + 1
   ret.set_height(__A  )
   return ret
def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode  )			->			MyNode:
   _SCREAMING_SNAKE_CASE	=				node.get_left()
   assert left_child is not None
   node.set_left(left_rotation(__A  )  )
   return right_rotation(__A  )
def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode  )			->			MyNode:
   _SCREAMING_SNAKE_CASE	=				node.get_right()
   assert right_child is not None
   node.set_right(right_rotation(__A  )  )
   return left_rotation(__A  )
def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode | None	,					__A    :			Any  )			->			MyNode | None:
   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
         _SCREAMING_SNAKE_CASE	=				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
            _SCREAMING_SNAKE_CASE	=				right_rotation(__A  )
         else:
            _SCREAMING_SNAKE_CASE	=				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:
         _SCREAMING_SNAKE_CASE	=				node.get_right()
         assert right_child is not None
         if data < right_child.get_data():
            _SCREAMING_SNAKE_CASE	=				rl_rotation(__A  )
         else:
            _SCREAMING_SNAKE_CASE	=				left_rotation(__A  )
   _SCREAMING_SNAKE_CASE	=				my_max(get_height(node.get_right()  )	,					get_height(node.get_left()  )  ) + 1
   node.set_height(__A  )
   return node
def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode  )			->			Any:
   while True:
      _SCREAMING_SNAKE_CASE	=				root.get_right()
      if right_child is None:
         break
      _SCREAMING_SNAKE_CASE	=				right_child
   return root.get_data()
def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode  )			->			Any:
   while True:
      _SCREAMING_SNAKE_CASE	=				root.get_left()
      if left_child is None:
         break
      _SCREAMING_SNAKE_CASE	=				left_child
   return root.get_data()
def 			SCREAMING_SNAKE_CASE_			(							__A    :			MyNode	,					__A    :			Any  )			->			MyNode | None:
   _SCREAMING_SNAKE_CASE	=				root.get_left()
   _SCREAMING_SNAKE_CASE	=				root.get_right()
   if root.get_data() == data:
      if left_child is not None and right_child is not None:
         _SCREAMING_SNAKE_CASE	=				get_left_most(__A  )
         root.set_data(__A  )
         root.set_right(del_node(__A	,					__A  )  )
      elif left_child is not None:
         _SCREAMING_SNAKE_CASE	=				left_child
      elif right_child is not None:
         _SCREAMING_SNAKE_CASE	=				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()  ):
         _SCREAMING_SNAKE_CASE	=				left_rotation(__A  )
      else:
         _SCREAMING_SNAKE_CASE	=				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()  ):
         _SCREAMING_SNAKE_CASE	=				right_rotation(__A  )
      else:
         _SCREAMING_SNAKE_CASE	=				lr_rotation(__A  )
   _SCREAMING_SNAKE_CASE	=				my_max(get_height(root.get_right()  )	,					get_height(root.get_left()  )  ) + 1
   root.set_height(__A  )
   return root







class 		lowercase_   :


   """simple docstring"""

   def __init__(   self :     str   ):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE	=				None



   def 							lowerCAmelCase_      (   self :     int   ):

      """simple docstring"""
      return get_height(self.root   )



   def 							lowerCAmelCase_      (   self :     Tuple  ,				__lowerCamelCase :     Any   ):

      """simple docstring"""
      print("insert:" + str(__lowerCamelCase   )   )
      _SCREAMING_SNAKE_CASE	=				insert_node(self.root  ,				__lowerCamelCase   )



   def 							lowerCAmelCase_      (   self :     Dict  ,				__lowerCamelCase :     Any   ):

      """simple docstring"""
      print("delete:" + str(__lowerCamelCase   )   )
      if self.root is None:
         print("Tree is empty!"   )
         return
      _SCREAMING_SNAKE_CASE	=				del_node(self.root  ,				__lowerCamelCase   )



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

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


def 			SCREAMING_SNAKE_CASE_			(							)			->			None:
   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))







'''simple docstring'''



from __future__ import annotations
def 			SCREAMING_SNAKE_CASE_			(							__A    :			float	,					__A    :			float	,					__A    :			float	,					)			->			tuple:
   if (electron_conc, hole_conc, intrinsic_conc).count(0  ) != 1:
      raise ValueError("You cannot supply more or less than 2 values"  )
   elif electron_conc < 0:
      raise ValueError("Electron concentration cannot be negative in a semiconductor"  )
   elif hole_conc < 0:
      raise ValueError("Hole concentration cannot be negative in a semiconductor"  )
   elif intrinsic_conc < 0:
      raise ValueError(
          "Intrinsic concentration cannot be negative in a semiconductor"  )
   elif electron_conc == 0:
      return (
          "electron_conc",
          intrinsic_conc**2 / hole_conc,
      )
   elif hole_conc == 0:
      return (
          "hole_conc",
          intrinsic_conc**2 / electron_conc,
      )
   elif intrinsic_conc == 0:
      return (
          "intrinsic_conc",
          (electron_conc * hole_conc) ** 0.5,
      )
   else:
      return (-1, -1)


if __name__ == "__main__":
 import doctest

 doctest.testmod()

