"""simple docstring"""


from __future__ import annotations

import math
import random
from typing import Any






class   __UpperCAmelCase		:

				def __init__( self ):
										lowerCamelCase__   =[]
										lowerCamelCase__   =0
										lowerCamelCase__   =0

				def 						_a      ( self ):
										return self.head == self.tail

				def 						_a      ( self      ,					_lowerCamelCase ):
										self.data.append(_lowerCamelCase )
										lowerCamelCase__   =self.tail + 1

				def 						_a      ( self ):
										lowerCamelCase__   =self.data[self.head]
										lowerCamelCase__   =self.head + 1
										return ret

				def 						_a      ( self ):
										return self.tail - self.head






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






class   __UpperCAmelCase		:

				def __init__( self      ,					_lowerCamelCase ):
										lowerCamelCase__   =data
										lowerCamelCase__   =None
										lowerCamelCase__   =None
										lowerCamelCase__   =1

				def 						_a      ( self ):
										return self.data

				def 						_a      ( self ):
										return self.left

				def 						_a      ( self ):
										return self.right

				def 						_a      ( self ):
										return self.height

				def 						_a      ( self      ,					_lowerCamelCase ):
										lowerCamelCase__   =data

				def 						_a      ( self      ,					_lowerCamelCase ):
										lowerCamelCase__   =node

				def 						_a      ( self      ,					_lowerCamelCase ):
										lowerCamelCase__   =node






				def 						_a      ( self      ,					_lowerCamelCase ):
										lowerCamelCase__   =height





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   int:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   int:




						'''simple docstring'''



						if a > b:
												return a
						return b





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   MyNode:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   MyNode:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   MyNode:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   MyNode:




						'''simple docstring'''



						lowerCamelCase__   =node.get_right()
						assert right_child is not None
						node.set_right(right_rotation(__lowerCAmelCase							)							)
						return left_rotation(__lowerCAmelCase							)





def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   MyNode | None:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   Any:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase							)				->   Any:




						'''simple docstring'''



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





def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   MyNode | None:




						'''simple docstring'''



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






class   __UpperCAmelCase		:

				def __init__( self ):
										lowerCamelCase__   =None

				def 						_a      ( self ):
										return get_height(self.root )

				def 						_a      ( self      ,					_lowerCamelCase ):
										print("insert:" + str(_lowerCamelCase ) )
										lowerCamelCase__   =insert_node(self.root      ,					_lowerCamelCase )

				def 						_a      ( self      ,					_lowerCamelCase ):
										print("delete:" + str(_lowerCamelCase ) )
										if self.root is None:
																print("Tree is empty!" )
																return
										lowerCamelCase__   =del_node(self.root      ,					_lowerCamelCase )






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





def      lowerCamelCase_					(   )				->   None:




						'''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))



"""simple docstring"""


def      lowerCamelCase_					(   __lowerCAmelCase  ,       __lowerCAmelCase							)				->   float:




						'''simple docstring'''



						return price * (1 + tax_rate)


if __name__ == "__main__":
	print(F'''{price_plus_tax(100, 0.25) = }''')
	print(F'''{price_plus_tax(125.50, 0.05) = }''')


