






from __future__ import annotations

import math
import random
from typing import Any




class  UpperCamelCase_      :



	'''simple docstring'''




	def __init__(       self					)       ->    None:
								snake_case_				=							[]
								snake_case_				=							0
								snake_case_				=							0




	def 							_UpperCamelCase			(       self					)       ->    bool:
								return self.head == self.tail




	def 							_UpperCamelCase			(       self       ,			a					)       ->    None:
								self.data.append(a					)
								snake_case_				=							self.tail + 1




	def 							_UpperCamelCase			(       self					)       ->    Any:
								snake_case_				=							self.data[self.head]
								snake_case_				=							self.head + 1
								return ret




	def 							_UpperCamelCase			(       self					)       ->    int:
								return self.tail - self.head






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






class  UpperCamelCase_      :



	'''simple docstring'''




	def __init__(       self       ,			a					)       ->    None:
								snake_case_				=							data
								snake_case_				=							None
								snake_case_				=							None
								snake_case_				=							1




	def 							_UpperCamelCase			(       self					)       ->    Any:
								return self.data




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




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




	def 							_UpperCamelCase			(       self					)       ->    int:
								return self.height




	def 							_UpperCamelCase			(       self       ,			a					)       ->    None:
								snake_case_				=							data




	def 							_UpperCamelCase			(       self       ,			a					)       ->    None:
								snake_case_				=							node




	def 							_UpperCamelCase			(       self       ,			a					)       ->    None:
								snake_case_				=							node






	def 							_UpperCamelCase			(       self       ,			a					)       ->    None:
								snake_case_				=							height






def 						__UpperCAmelCase			(     a_):
							if node is None:
														return 0
							return node.get_height()





def 						__UpperCAmelCase			(     a_							,     a_):
							if a > b:
														return a
							return b





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





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





def 						__UpperCAmelCase			(     a_):
							snake_case_				=							node.get_left()
							assert left_child is not None
							node.set_left(left_rotation(a_))
							return right_rotation(a_)





def 						__UpperCAmelCase			(     a_):
							snake_case_				=							node.get_right()
							assert right_child is not None
							node.set_right(right_rotation(a_))
							return left_rotation(a_)





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





def 						__UpperCAmelCase			(     a_):
							while True:
														snake_case_				=							root.get_right()
														if right_child is None:
																					break
														snake_case_				=							right_child
							return root.get_data()





def 						__UpperCAmelCase			(     a_):
							while True:
														snake_case_				=							root.get_left()
														if left_child is None:
																					break
														snake_case_				=							left_child
							return root.get_data()





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




class  UpperCamelCase_      :



	'''simple docstring'''




	def __init__(       self					)       ->    None:
								snake_case_				=							None




	def 							_UpperCamelCase			(       self					)       ->    int:
								return get_height(self.root					)




	def 							_UpperCamelCase			(       self       ,			a					)       ->    None:
								print('insert:' + str(a					)					)
								snake_case_				=							insert_node(self.root       ,			a					)




	def 							_UpperCamelCase			(       self       ,			a					)       ->    None:
								print('delete:' + str(a					)					)
								if self.root is None:
															print('Tree is empty!'					)
															return
								snake_case_				=							del_node(self.root       ,			a					)






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






def 						__UpperCAmelCase			(     ):
							import doctest

							doctest.testmod()


if __name__ == "__main__":
	_test()
	lowercase  							=					AVLtree()
	lowercase  							=					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))













from __future__ import annotations





def 						__UpperCAmelCase			(     a_							,     a_							,     a_							,     a_):  # noqa: E741
							while r - l > 1:
														snake_case_				=							(l + r) // 2
														if v[m] >= key:
																					snake_case_				=							m
														else:
																					snake_case_				=							m  # noqa: E741
							return r





def 						__UpperCAmelCase			(     a_):
							if len(a_) == 0:
														return 0

							snake_case_				=							[0] * len(a_)
							snake_case_				=							1

							snake_case_				=							v[0]

							for i in range(1							,     len(a_)):
														if v[i] < tail[0]:
																					snake_case_				=							v[i]
														elif v[i] > tail[length - 1]:
																					snake_case_				=							v[i]
																					length += 1
														else:
																					snake_case_				=							v[i]

							return length


if __name__ == "__main__":
	import doctest

	doctest.testmod()





