


'''simple docstring'''
from __future__ import annotations

import math
import random
from typing import Any




class 			lowerCamelCase_   :






      def __init__(					self				:    List[Any] ):


          '''simple docstring'''


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






      def lowercase_							(					self				:    Union[str, Any] ):


          '''simple docstring'''


          return self.head == self.tail






      def lowercase_							(					self				:    Dict						,						_A				:    Any ):


          '''simple docstring'''


          self.data.append(_A )
          UpperCAmelCase__			:		Optional[int]													=				self.tail + 1






      def lowercase_							(					self				:    List[str] ):


          '''simple docstring'''


          UpperCAmelCase__			:		Tuple													=				self.data[self.head]
          UpperCAmelCase__			:		Optional[Any]													=				self.head + 1
          return ret






      def lowercase_							(					self				:    List[str] ):


          '''simple docstring'''


          return self.tail - self.head






      def lowercase_							(					self				:    Optional[int] ):


          '''simple docstring'''


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




class 			lowerCamelCase_   :






      def __init__(					self				:    Any						,						_A				:    Any ):


          '''simple docstring'''


          UpperCAmelCase__			:		str													=				data
          UpperCAmelCase__			:		MyNode | None													=				None
          UpperCAmelCase__			:		MyNode | None													=				None
          UpperCAmelCase__			:		int													=				1






      def lowercase_							(					self				:    List[str] ):


          '''simple docstring'''


          return self.data






      def lowercase_							(					self				:    Tuple ):


          '''simple docstring'''


          return self.left






      def lowercase_							(					self				:    Optional[int] ):


          '''simple docstring'''


          return self.right






      def lowercase_							(					self				:    List[Any] ):


          '''simple docstring'''


          return self.height






      def lowercase_							(					self				:    Any						,						_A				:    Any ):


          '''simple docstring'''


          UpperCAmelCase__			:		Any													=				data






      def lowercase_							(					self				:    List[str]						,						_A				:    MyNode | None ):


          '''simple docstring'''


          UpperCAmelCase__			:		Optional[Any]													=				node






      def lowercase_							(					self				:    str						,						_A				:    MyNode | None ):


          '''simple docstring'''


          UpperCAmelCase__			:		int													=				node






      def lowercase_							(					self				:    Optional[int]						,						_A				:    int ):


          '''simple docstring'''


          UpperCAmelCase__			:		List[str]													=				height





def 					a__       (					lowerCAmelCase__						)    ->	int:
    if node is None:
        return 0
    return node.get_height()





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





def 					a__       (					lowerCAmelCase__						)    ->	MyNode:
    print('''left rotation node:'''  ,					node.get_data()						)
    UpperCAmelCase__			:		Optional[Any]													=				node.get_left()
    assert ret is not None
    node.set_left(ret.get_right()						)
    ret.set_right(lowerCAmelCase__						)
    UpperCAmelCase__			:		Optional[Any]													=				my_max(get_height(node.get_right()						)  ,					get_height(node.get_left()						)						) + 1
    node.set_height(lowerCAmelCase__						)
    UpperCAmelCase__			:		List[Any]													=				my_max(get_height(ret.get_right()						)  ,					get_height(ret.get_left()						)						) + 1
    ret.set_height(lowerCAmelCase__						)
    return ret





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





def 					a__       (					lowerCAmelCase__						)    ->	MyNode:
    UpperCAmelCase__			:		int													=				node.get_left()
    assert left_child is not None
    node.set_left(left_rotation(lowerCAmelCase__						)						)
    return right_rotation(lowerCAmelCase__						)





def 					a__       (					lowerCAmelCase__						)    ->	MyNode:
    UpperCAmelCase__			:		Union[str, Any]													=				node.get_right()
    assert right_child is not None
    node.set_right(right_rotation(lowerCAmelCase__						)						)
    return left_rotation(lowerCAmelCase__						)





def 					a__       (					lowerCAmelCase__  ,					lowerCAmelCase__						)    ->	MyNode | None:
    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
            UpperCAmelCase__			:		Union[str, Any]													=				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__			:		Tuple													=				right_rotation(lowerCAmelCase__						)
            else:
                UpperCAmelCase__			:		Any													=				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:
            UpperCAmelCase__			:		str													=				node.get_right()
            assert right_child is not None
            if data < right_child.get_data():
                UpperCAmelCase__			:		Optional[Any]													=				rl_rotation(lowerCAmelCase__						)
            else:
                UpperCAmelCase__			:		str													=				left_rotation(lowerCAmelCase__						)
    UpperCAmelCase__			:		str													=				my_max(get_height(node.get_right()						)  ,					get_height(node.get_left()						)						) + 1
    node.set_height(lowerCAmelCase__						)
    return node





def 					a__       (					lowerCAmelCase__						)    ->	Any:
    while True:
        UpperCAmelCase__			:		Optional[int]													=				root.get_right()
        if right_child is None:
            break
        UpperCAmelCase__			:		str													=				right_child
    return root.get_data()





def 					a__       (					lowerCAmelCase__						)    ->	Any:
    while True:
        UpperCAmelCase__			:		List[str]													=				root.get_left()
        if left_child is None:
            break
        UpperCAmelCase__			:		int													=				left_child
    return root.get_data()





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




class 			lowerCamelCase_   :






      def __init__(					self				:    Union[str, Any] ):


          '''simple docstring'''


          UpperCAmelCase__			:		MyNode | None													=				None






      def lowercase_							(					self				:    Optional[Any] ):


          '''simple docstring'''


          return get_height(self.root )






      def lowercase_							(					self				:    Optional[Any]						,						_A				:    Any ):


          '''simple docstring'''


          print('''insert:''' + str(_A ) )
          UpperCAmelCase__			:		Dict													=				insert_node(self.root						,						_A )






      def lowercase_							(					self				:    Optional[Any]						,						_A				:    Any ):


          '''simple docstring'''


          print('''delete:''' + str(_A ) )
          if self.root is None:
              print('''Tree is empty!''' )
              return
          UpperCAmelCase__			:		Optional[Any]													=				del_node(self.root						,						_A )






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


          '''simple docstring'''


          UpperCAmelCase__			:		Dict													=				''''''
          UpperCAmelCase__			:		Any													=				MyQueue()
          q.push(self.root )
          UpperCAmelCase__			:		str													=				self.get_height()
          if layer == 0:
              return output
          UpperCAmelCase__			:		Optional[int]													=				0
          while not q.is_empty():
              UpperCAmelCase__			:		Optional[int]													=				q.pop()
              UpperCAmelCase__			:		Optional[Any]													=				''' ''' * int(math.pow(2						,						layer - 1 ) )
              output += space
              if node is None:
                  output += "*"
                  q.push(_A )
                  q.push(_A )
              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						,						_A ) - 1:
                      UpperCAmelCase__			:		Union[str, Any]													=				layer - 1
                      if layer == 0:
                          output += "\n*************************************"
                          return output
                      output += "\n"
                      break
          output += "\n*************************************"
          return output





def 					a__       (					)    ->	None:
    import doctest

    doctest.testmod()


if __name__ == "__main__":
  _test()
  UpperCamelCase__    					=      AVLtree()
  UpperCamelCase__    					=      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'''
# Algorithm for the pigeonhole sorting







def 					a__       (					lowerCAmelCase__						)    ->	Optional[Any]:
    UpperCAmelCase__			:		Any													=				min(lowerCAmelCase__						)  # min() finds the minimum value
    UpperCAmelCase__			:		Optional[int]													=				max(lowerCAmelCase__						)  # max() finds the maximum value

    UpperCAmelCase__			:		int													=				max_val - min_val + 1  # size is difference of max and min values plus one

    # list of pigeonholes of size equal to the variable size
    UpperCAmelCase__			:		Any													=				[0] * size

    # Populate the pigeonholes.
    for x in a:
        assert isinstance(lowerCAmelCase__  ,					lowerCAmelCase__						), "integers only please"
        holes[x - min_val] += 1

    # Putting the elements back into the array in an order.
    UpperCAmelCase__			:		Optional[int]													=				0
    for count in range(lowerCAmelCase__						):
        while holes[count] > 0:
            holes[count] -= 1
            UpperCAmelCase__			:		Dict													=				count + min_val
            i += 1





def 					a__       (					)    ->	Union[str, Any]:
    UpperCAmelCase__			:		List[str]													=				[8, 3, 2, 7, 4, 6, 8]
    pigeonhole_sort(lowerCAmelCase__						)
    print('''Sorted order is:'''  ,					''' '''.join(lowerCAmelCase__						)						)


if __name__ == "__main__":
  main()
