



from __future__ import annotations

import math
import random
from typing import Any


class 				_a						:





							'''simple docstring'''

							def __init__(							self				):







											"""simple docstring"""



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



							def 		_A	(							self				):







											"""simple docstring"""



											return self.head == self.tail



							def 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											self.data.append(__UpperCAmelCase				)
											a__	:							Optional[int]      						= self.tail + 1



							def 		_A	(							self				):







											"""simple docstring"""



											a__	:							Union[str, Any]      						= self.data[self.head]
											a__	:							List[str]      						= self.head + 1
											return ret



							def 		_A	(							self				):







											"""simple docstring"""



											return self.tail - self.head




							def 		_A	(							self				):







											"""simple docstring"""



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





class 				_a						:





							'''simple docstring'''

							def __init__(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											a__	:							int      						= data
											a__	:							MyNode | None      						= None
											a__	:							MyNode | None      						= None
											a__	:							int      						= 1



							def 		_A	(							self				):







											"""simple docstring"""



											return self.data



							def 		_A	(							self				):







											"""simple docstring"""



											return self.left



							def 		_A	(							self				):







											"""simple docstring"""



											return self.right



							def 		_A	(							self				):







											"""simple docstring"""



											return self.height



							def 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											a__	:							str      						= data



							def 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											a__	:							Any      						= node



							def 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											a__	:							Union[str, Any]      						= node




							def 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											a__	:							Tuple      						= height






def     SCREAMING_SNAKE_CASE(      __UpperCamelCase )	->						int:
				if node is None:
								return 0
				return node.get_height()






def     SCREAMING_SNAKE_CASE(      __UpperCamelCase	,				__UpperCamelCase )	->						int:
				if a > b:
								return a
				return b






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






def     SCREAMING_SNAKE_CASE(      __UpperCamelCase )	->						MyNode:
				print("right rotation node:"	,				node.get_data() )
				a__	:							Tuple      						= node.get_right()
				assert ret is not None
				node.set_right(ret.get_left() )
				ret.set_left(__UpperCamelCase )
				a__	:							Optional[int]      						= my_max(get_height(node.get_right() )	,				get_height(node.get_left() ) ) + 1
				node.set_height(__UpperCamelCase )
				a__	:							Dict      						= my_max(get_height(ret.get_right() )	,				get_height(ret.get_left() ) ) + 1
				ret.set_height(__UpperCamelCase )
				return ret






def     SCREAMING_SNAKE_CASE(      __UpperCamelCase )	->						MyNode:
				a__	:							str      						= node.get_left()
				assert left_child is not None
				node.set_left(left_rotation(__UpperCamelCase ) )
				return right_rotation(__UpperCamelCase )






def     SCREAMING_SNAKE_CASE(      __UpperCamelCase )	->						MyNode:
				a__	:							str      						= node.get_right()
				assert right_child is not None
				node.set_right(right_rotation(__UpperCamelCase ) )
				return left_rotation(__UpperCamelCase )






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






def     SCREAMING_SNAKE_CASE(      __UpperCamelCase )	->						Any:
				while True:
								a__	:							Tuple      						= root.get_right()
								if right_child is None:
												break
								a__	:							Optional[Any]      						= right_child
				return root.get_data()






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






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

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


class 				_a						:





							'''simple docstring'''

							def __init__(							self				):







											"""simple docstring"""



											a__	:							MyNode | None      						= None



							def 		_A	(							self				):







											"""simple docstring"""



											return get_height(self.root				)



							def 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											print("insert:" + str(__UpperCAmelCase				)				)
											a__	:							List[Any]      						= insert_node(self.root ,					__UpperCAmelCase				)



							def 		_A	(							self ,					__UpperCAmelCase				):







											"""simple docstring"""



											print("delete:" + str(__UpperCAmelCase				)				)
											if self.root is None:
															print("Tree is empty!"				)
															return
											a__	:							Union[str, Any]      						= del_node(self.root ,					__UpperCAmelCase				)




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







											"""simple docstring"""



											a__	:							str      						= ""
											a__	:							int      						= MyQueue()
											q.push(self.root				)
											a__	:							List[Any]      						= self.get_height()
											if layer == 0:
															return output
											a__	:							int      						= 0
											while not q.is_empty():
															a__	:							str      						= q.pop()
															a__	:							Dict      						= " " * int(math.pow(2 ,					layer - 1				)				)
															output += space
															if node is None:
																			output += "*"
																			q.push(__UpperCAmelCase				)
																			q.push(__UpperCAmelCase				)
															else:
																			output += str(node.get_data()				)
																			q.push(node.get_left()				)
																			q.push(node.get_right()				)
															output += space
															a__	:							Optional[int]      						= cnt + 1
															for i in range(100				):
																			if cnt == math.pow(2 ,					__UpperCAmelCase				) - 1:
																							a__	:							List[Any]      						= 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))







import unittest

from knapsack import knapsack as k


class 				_a						(       unittest.TestCase			):





							'''simple docstring'''

							def 		_A	(							self				):







											"""simple docstring"""



											a__	:							List[str]      						= 0
											a__	:							Union[str, Any]      						= [0]
											a__	:							Optional[Any]      						= [0]
											a__	:							Tuple      						= len(__UpperCAmelCase				)
											self.assertEqual(k.knapsack(__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase				) ,					0				)

											a__	:							Optional[Any]      						= [60]
											a__	:							Tuple      						= [10]
											a__	:							Optional[Any]      						= len(__UpperCAmelCase				)
											self.assertEqual(k.knapsack(__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase				) ,					0				)



							def 		_A	(							self				):







											"""simple docstring"""



											a__	:							Dict      						= 3
											a__	:							Optional[int]      						= [1, 2, 3]
											a__	:							List[Any]      						= [3, 2, 1]
											a__	:							List[Any]      						= len(__UpperCAmelCase				)
											self.assertEqual(k.knapsack(__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase				) ,					5				)




							def 		_A	(							self				):







											"""simple docstring"""



											a__	:							List[Any]      						= 50
											a__	:							Union[str, Any]      						= [60, 100, 120]
											a__	:							str      						= [10, 20, 30]
											a__	:							Union[str, Any]      						= len(__UpperCAmelCase				)
											self.assertEqual(k.knapsack(__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase ,					__UpperCAmelCase				) ,					220				)


if __name__ == "__main__":
						unittest.main()


