


'''simple docstring'''



from __future__ import annotations

import math
import random
from typing import Any



class 			a       :


     """simple docstring"""






     def __init__(       self  :	Optional[int]    )		->							None:
          __UpperCAmelCase			:				list[Any]													=    []
          __UpperCAmelCase			:				int													=    0
          __UpperCAmelCase			:				int													=    0

     def 				lowerCamelCase__				(       self  :	List[str]    )		->							bool:
          return self.head == self.tail

     def 				lowerCamelCase__				(       self  :	str							,				snake_case  :	Any    )		->							None:
          self.data.append(snake_case    )
          __UpperCAmelCase			:				Any													=    self.tail + 1

     def 				lowerCamelCase__				(       self  :	Optional[Any]    )		->							Any:
          __UpperCAmelCase			:				int													=    self.data[self.head]
          __UpperCAmelCase			:				int													=    self.head + 1
          return ret

     def 				lowerCamelCase__				(       self  :	Optional[int]    )		->							int:
          return self.tail - self.head






     def 				lowerCamelCase__				(       self  :	str    )		->							None:
          print(self.data    )
          print('''**************'''    )
          print(self.data[self.head : self.tail]    )



class 			a       :


     """simple docstring"""






     def __init__(       self  :	Optional[Any]							,				snake_case  :	Any    )		->							None:
          __UpperCAmelCase			:				int													=    data
          __UpperCAmelCase			:				MyNode | None													=    None
          __UpperCAmelCase			:				MyNode | None													=    None
          __UpperCAmelCase			:				int													=    1

     def 				lowerCamelCase__				(       self  :	str    )		->							Any:
          return self.data

     def 				lowerCamelCase__				(       self  :	Any    )		->							MyNode | None:
          return self.left

     def 				lowerCamelCase__				(       self  :	str    )		->							MyNode | None:
          return self.right

     def 				lowerCamelCase__				(       self  :	Optional[Any]    )		->							int:
          return self.height

     def 				lowerCamelCase__				(       self  :	Tuple							,				snake_case  :	Any    )		->							None:
          __UpperCAmelCase			:				List[str]													=    data

     def 				lowerCamelCase__				(       self  :	str							,				snake_case  :	MyNode | None    )		->							None:
          __UpperCAmelCase			:				int													=    node

     def 				lowerCamelCase__				(       self  :	Union[str, Any]							,				snake_case  :	MyNode | None    )		->							None:
          __UpperCAmelCase			:				str													=    node






     def 				lowerCamelCase__				(       self  :	Tuple							,				snake_case  :	int    )		->							None:
          __UpperCAmelCase			:				str													=    height




def 			_a			(		_lowercase      :			MyNode | None						):





     '''simple docstring'''






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




def 			_a			(		_lowercase      :			int    ,      _lowercase      :			int						):





     '''simple docstring'''






     if a > b:
          return a
     return b




def 			_a			(		_lowercase      :			MyNode						):





     '''simple docstring'''






     print('''left rotation node:'''    ,      node.get_data()						)
     __UpperCAmelCase			:				Any													=    node.get_left()
     assert ret is not None
     node.set_left(ret.get_right()						)
     ret.set_right(_lowercase						)
     __UpperCAmelCase			:				List[Any]													=    my_max(get_height(node.get_right()						)    ,      get_height(node.get_left()						)						) + 1
     node.set_height(_lowercase						)
     __UpperCAmelCase			:				Optional[Any]													=    my_max(get_height(ret.get_right()						)    ,      get_height(ret.get_left()						)						) + 1
     ret.set_height(_lowercase						)
     return ret




def 			_a			(		_lowercase      :			MyNode						):





     '''simple docstring'''






     print('''right rotation node:'''    ,      node.get_data()						)
     __UpperCAmelCase			:				List[Any]													=    node.get_right()
     assert ret is not None
     node.set_right(ret.get_left()						)
     ret.set_left(_lowercase						)
     __UpperCAmelCase			:				Any													=    my_max(get_height(node.get_right()						)    ,      get_height(node.get_left()						)						) + 1
     node.set_height(_lowercase						)
     __UpperCAmelCase			:				int													=    my_max(get_height(ret.get_right()						)    ,      get_height(ret.get_left()						)						) + 1
     ret.set_height(_lowercase						)
     return ret




def 			_a			(		_lowercase      :			MyNode						):





     '''simple docstring'''






     __UpperCAmelCase			:				List[str]													=    node.get_left()
     assert left_child is not None
     node.set_left(left_rotation(_lowercase						)						)
     return right_rotation(_lowercase						)




def 			_a			(		_lowercase      :			MyNode						):





     '''simple docstring'''






     __UpperCAmelCase			:				Dict													=    node.get_right()
     assert right_child is not None
     node.set_right(right_rotation(_lowercase						)						)
     return left_rotation(_lowercase						)




def 			_a			(		_lowercase      :			MyNode | None    ,      _lowercase      :			Any						):





     '''simple docstring'''






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




def 			_a			(		_lowercase      :			MyNode						):





     '''simple docstring'''






     while True:
          __UpperCAmelCase			:				List[Any]													=    root.get_right()
          if right_child is None:
               break
          __UpperCAmelCase			:				List[Any]													=    right_child
     return root.get_data()




def 			_a			(		_lowercase      :			MyNode						):





     '''simple docstring'''






     while True:
          __UpperCAmelCase			:				List[str]													=    root.get_left()
          if left_child is None:
               break
          __UpperCAmelCase			:				str													=    left_child
     return root.get_data()




def 			_a			(		_lowercase      :			MyNode    ,      _lowercase      :			Any						):





     '''simple docstring'''






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

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



class 			a       :


     """simple docstring"""






     def __init__(       self  :	Tuple    )		->							None:
          __UpperCAmelCase			:				MyNode | None													=    None

     def 				lowerCamelCase__				(       self  :	Optional[Any]    )		->							int:
          return get_height(self.root    )

     def 				lowerCamelCase__				(       self  :	Any							,				snake_case  :	Any    )		->							None:
          print('''insert:''' + str(snake_case    )    )
          __UpperCAmelCase			:				Optional[int]													=    insert_node(self.root							,				snake_case    )

     def 				lowerCamelCase__				(       self  :	Any							,				snake_case  :	Any    )		->							None:
          print('''delete:''' + str(snake_case    )    )
          if self.root is None:
               print('''Tree is empty!'''    )
               return
          __UpperCAmelCase			:				List[str]													=    del_node(self.root							,				snake_case    )






     def __str__(       self  :	str							,				)		->							str:  # a level traversale, gives a more intuitive look on the tree
          __UpperCAmelCase			:				List[Any]													=    ''''''
          __UpperCAmelCase			:				Tuple													=    MyQueue()
          q.push(self.root    )
          __UpperCAmelCase			:				Any													=    self.get_height()
          if layer == 0:
               return output
          __UpperCAmelCase			:				Optional[Any]													=    0
          while not q.is_empty():
               __UpperCAmelCase			:				Any													=    q.pop()
               __UpperCAmelCase			:				str													=    ''' ''' * 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
               __UpperCAmelCase			:				Optional[int]													=    cnt + 1
               for i in range(100    ):
                    if cnt == math.pow(2							,				snake_case    ) - 1:
                         __UpperCAmelCase			:				str													=    layer - 1
                         if layer == 0:
                              output += "\n*************************************"
                              return output
                         output += "\n"
                         break
          output += "\n*************************************"
          return output




def 			_a			(		):





     '''simple docstring'''






     import doctest

     doctest.testmod()


if __name__ == "__main__":
      _test()
      __UpperCAmelCase    :List[Any]				       =     AVLtree()
      __UpperCAmelCase    :int				       =     list(range(1_0))
      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 collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

__UpperCAmelCase    :Optional[int]				       =     TypeVar("KEY")
__UpperCAmelCase    :Tuple				       =     TypeVar("VAL")



@dataclass(frozen=_a			,						slots=_a )
class 			a       (	Generic[KEY, VAL] ):


     """simple docstring"""






     SCREAMING_SNAKE_CASE :				KEY
     SCREAMING_SNAKE_CASE :				VAL



class 			a       (	_Item ):


     """simple docstring"""






     def __init__(       self  :	Optional[int]    )		->							None:
          super().__init__(snake_case							,				snake_case    )






     def __bool__(       self  :	Dict    )		->							bool:
          return False



__UpperCAmelCase    :Optional[Any]				       =     _DeletedItem()



class 			a       (	MutableMapping[KEY, VAL] ):


     """simple docstring"""






     def __init__(       self  :	str							,				snake_case  :	int = 8							,				snake_case  :	float = 0.75    )		->							None:
          __UpperCAmelCase			:				Dict													=    initial_block_size
          __UpperCAmelCase			:				list[_Item | None]													=    [None] * initial_block_size
          assert 0.0 < capacity_factor < 1.0
          __UpperCAmelCase			:				str													=    capacity_factor
          __UpperCAmelCase			:				Optional[int]													=    0

     def 				lowerCamelCase__				(       self  :	Optional[Any]							,				snake_case  :	KEY    )		->							int:
          return hash(snake_case    ) % len(self._buckets    )

     def 				lowerCamelCase__				(       self  :	Union[str, Any]							,				snake_case  :	int    )		->							int:
          return (ind + 1) % len(self._buckets    )

     def 				lowerCamelCase__				(       self  :	List[str]							,				snake_case  :	int							,				snake_case  :	KEY							,				snake_case  :	VAL    )		->							bool:
          __UpperCAmelCase			:				int													=    self._buckets[ind]
          if not stored:
               __UpperCAmelCase			:				List[str]													=    _Item(snake_case							,				snake_case    )
               self._len += 1
               return True
          elif stored.key == key:
               __UpperCAmelCase			:				int													=    _Item(snake_case							,				snake_case    )
               return True
          else:
               return False

     def 				lowerCamelCase__				(       self  :	str    )		->							bool:
          __UpperCAmelCase			:				Union[str, Any]													=    len(self._buckets    ) * self._capacity_factor
          return len(self    ) >= int(snake_case    )

     def 				lowerCamelCase__				(       self  :	List[str]    )		->							bool:
          if len(self._buckets    ) <= self._initial_block_size:
               return False
          __UpperCAmelCase			:				List[str]													=    len(self._buckets    ) * self._capacity_factor / 2
          return len(self    ) < limit

     def 				lowerCamelCase__				(       self  :	Optional[int]							,				snake_case  :	int    )		->							None:
          __UpperCAmelCase			:				Union[str, Any]													=    self._buckets
          __UpperCAmelCase			:				Union[str, Any]													=    [None] * new_size
          __UpperCAmelCase			:				List[str]													=    0
          for item in old_buckets:
               if item:
                    self._add_item(item.key							,				item.val    )

     def 				lowerCamelCase__				(       self  :	Optional[int]    )		->							None:
          self._resize(len(self._buckets    ) * 2    )

     def 				lowerCamelCase__				(       self  :	List[str]    )		->							None:
          self._resize(len(self._buckets    ) // 2    )

     def 				lowerCamelCase__				(       self  :	Union[str, Any]							,				snake_case  :	KEY    )		->							Iterator[int]:
          __UpperCAmelCase			:				Tuple													=    self._get_bucket_index(snake_case    )
          for _ in range(len(self._buckets    )    ):
               yield ind
               __UpperCAmelCase			:				Dict													=    self._get_next_ind(snake_case    )

     def 				lowerCamelCase__				(       self  :	str							,				snake_case  :	KEY							,				snake_case  :	VAL    )		->							None:
          for ind in self._iterate_buckets(snake_case    ):
               if self._try_set(snake_case							,				snake_case							,				snake_case    ):
                    break

     def __setitem__(       self  :	List[str]							,				snake_case  :	KEY							,				snake_case  :	VAL    )		->							None:
          if self._is_full():
               self._size_up()

          self._add_item(snake_case							,				snake_case    )

     def __delitem__(       self  :	Any							,				snake_case  :	KEY    )		->							None:
          for ind in self._iterate_buckets(snake_case    ):
               __UpperCAmelCase			:				List[Any]													=    self._buckets[ind]
               if item is None:
                    raise KeyError(snake_case    )
               if item is _deleted:
                    continue
               if item.key == key:
                    __UpperCAmelCase			:				Optional[Any]													=    _deleted
                    self._len -= 1
                    break
          if self._is_sparse():
               self._size_down()

     def __getitem__(       self  :	List[str]							,				snake_case  :	KEY    )		->							VAL:
          for ind in self._iterate_buckets(snake_case    ):
               __UpperCAmelCase			:				Optional[int]													=    self._buckets[ind]
               if item is None:
                    break
               if item is _deleted:
                    continue
               if item.key == key:
                    return item.val
          raise KeyError(snake_case    )

     def __len__(       self  :	List[Any]    )		->							int:
          return self._len

     def __iter__(       self  :	str    )		->							Iterator[KEY]:
          yield from (item.key for item in self._buckets if item)






     def __repr__(       self  :	Optional[Any]    )		->							str:
          __UpperCAmelCase			:				str													=    ''' ,'''.join(
              f'{item.key}: {item.val}' for item in self._buckets if item    )
          return f'HashMap({val_string})'