


from __future__ import annotations

import math
import random
from typing import Any






class     UpperCamelCase:


					def __init__(						self	:		Dict						)			->	Optional[Any]:




											'''simple docstring'''

											__snake_case				=		[]
											__snake_case				=		0
											__snake_case				=		0


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Union[str, Any]						)			->	int:




											'''simple docstring'''

											return self.head == self.tail


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		str						)			->	str:




											'''simple docstring'''

											self.data.append(SCREAMING_SNAKE_CASE						)
											__snake_case				=		self.tail + 1


					def 							SCREAMING_SNAKE_CASE_  (						self	:		str						)			->	str:




											'''simple docstring'''

											__snake_case				=		self.data[self.head]
											__snake_case				=		self.head + 1
											return ret


					def 							SCREAMING_SNAKE_CASE_  (						self	:		str						)			->	Dict:




											'''simple docstring'''

											return self.tail - self.head






					def 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple						)			->	List[str]:




											'''simple docstring'''

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






class     UpperCamelCase:


					def __init__(						self	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Optional[int]						)			->	str:




											'''simple docstring'''

											__snake_case				=		data
											__snake_case				=		None
											__snake_case				=		None
											__snake_case				=		1


					def 							SCREAMING_SNAKE_CASE_  (						self	:		int						)			->	Tuple:




											'''simple docstring'''

											return self.data


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any						)			->	Optional[int]:




											'''simple docstring'''

											return self.left


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[int]						)			->	str:




											'''simple docstring'''

											return self.right


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]						)			->	str:




											'''simple docstring'''

											return self.height


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple     ,    SCREAMING_SNAKE_CASE	:		Tuple						)			->	Tuple:




											'''simple docstring'''

											__snake_case				=		data


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Any						)			->	Optional[int]:




											'''simple docstring'''

											__snake_case				=		node


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any     ,    SCREAMING_SNAKE_CASE	:		List[Any]						)			->	Tuple:




											'''simple docstring'''

											__snake_case				=		node






					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict     ,    SCREAMING_SNAKE_CASE	:		Optional[int]						)			->	Optional[int]:




											'''simple docstring'''

											__snake_case				=		height





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	int:


						'''simple docstring'''






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





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	Union[str, Any]:


						'''simple docstring'''






						if a > b:
												return a
						return b





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	Union[str, Any]:


						'''simple docstring'''






						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(_snake_case )
						__snake_case				=		my_max(get_height(node.get_right() )      ,	get_height(node.get_left() ) ) + 1
						node.set_height(_snake_case )
						__snake_case				=		my_max(get_height(ret.get_right() )      ,	get_height(ret.get_left() ) ) + 1
						ret.set_height(_snake_case )
						return ret





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	Union[str, Any]:


						'''simple docstring'''






						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(_snake_case )
						__snake_case				=		my_max(get_height(node.get_right() )      ,	get_height(node.get_left() ) ) + 1
						node.set_height(_snake_case )
						__snake_case				=		my_max(get_height(ret.get_right() )      ,	get_height(ret.get_left() ) ) + 1
						ret.set_height(_snake_case )
						return ret





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	int:


						'''simple docstring'''






						__snake_case				=		node.get_left()
						assert left_child is not None
						node.set_left(left_rotation(_snake_case ) )
						return right_rotation(_snake_case )





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	List[Any]:


						'''simple docstring'''






						__snake_case				=		node.get_right()
						assert right_child is not None
						node.set_right(right_rotation(_snake_case ) )
						return left_rotation(_snake_case )





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	Tuple:


						'''simple docstring'''






						if node is None:
												return MyNode(_snake_case )
						if data < node.get_data():
												node.set_left(insert_node(node.get_left()      ,	_snake_case ) )
												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(_snake_case )
																		else:
																								__snake_case				=		lr_rotation(_snake_case )
						else:
												node.set_right(insert_node(node.get_right()      ,	_snake_case ) )
												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(_snake_case )
																		else:
																								__snake_case				=		left_rotation(_snake_case )
						__snake_case				=		my_max(get_height(node.get_right() )      ,	get_height(node.get_left() ) ) + 1
						node.set_height(_snake_case )
						return node





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	List[Any]:


						'''simple docstring'''






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





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	Optional[Any]:


						'''simple docstring'''






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





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	str:


						'''simple docstring'''






						__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(_snake_case )
																		root.set_data(_snake_case )
																		root.set_right(del_node(_snake_case      ,	_snake_case ) )
												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(_snake_case      ,	_snake_case ) )
						else:  # root.get_data() < data
												if right_child is None:
																		return root
												else:
																		root.set_right(del_node(_snake_case      ,	_snake_case ) )

						if get_height(_snake_case ) - get_height(_snake_case ) == 2:
												assert right_child is not None
												if get_height(right_child.get_right() ) > get_height(right_child.get_left() ):
																		__snake_case				=		left_rotation(_snake_case )
												else:
																		__snake_case				=		rl_rotation(_snake_case )
						elif get_height(_snake_case ) - get_height(_snake_case ) == -2:
												assert left_child is not None
												if get_height(left_child.get_left() ) > get_height(left_child.get_right() ):
																		__snake_case				=		right_rotation(_snake_case )
												else:
																		__snake_case				=		lr_rotation(_snake_case )
						__snake_case				=		my_max(get_height(root.get_right() )      ,	get_height(root.get_left() ) ) + 1
						root.set_height(_snake_case )
						return root






class     UpperCamelCase:


					def __init__(						self	:		Optional[int]						)			->	List[Any]:




											'''simple docstring'''

											__snake_case				=		None


					def 							SCREAMING_SNAKE_CASE_  (						self	:		str						)			->	Union[str, Any]:




											'''simple docstring'''

											return get_height(self.root						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Union[str, Any]     ,    SCREAMING_SNAKE_CASE	:		Optional[int]						)			->	Optional[int]:




											'''simple docstring'''

											print("insert:" + str(SCREAMING_SNAKE_CASE						)						)
											__snake_case				=		insert_node(self.root     ,    SCREAMING_SNAKE_CASE						)


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any     ,    SCREAMING_SNAKE_CASE	:		List[Any]						)			->	Any:




											'''simple docstring'''

											print("delete:" + str(SCREAMING_SNAKE_CASE						)						)
											if self.root is None:
																	print("Tree is empty!"						)
																	return
											__snake_case				=		del_node(self.root     ,    SCREAMING_SNAKE_CASE						)






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




											'''simple docstring'''

											__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(SCREAMING_SNAKE_CASE						)
																							q.push(SCREAMING_SNAKE_CASE						)
																	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_0_0						):
																							if cnt == math.pow(2     ,    SCREAMING_SNAKE_CASE						) - 1:
																													__snake_case				=		layer - 1
																													if layer == 0:
																																			output += "\n*************************************"
																																			return output
																													output += "\n"
																													break
											output += "\n*************************************"
											return output





def 	_lowerCAmelCase       (    )						->	Optional[Any]:


						'''simple docstring'''






						import doctest

						doctest.testmod()


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

from decimal import Decimal
from math import *  # noqa: F403

from sympy import diff





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase      ,	_lowerCAmelCase = 10**-10 )						->	float:


						'''simple docstring'''






						__snake_case				=		a
						while True:
												__snake_case				=		Decimal(_lowerCAmelCase ) - (
												    Decimal(eval(_lowerCAmelCase ) ) / Decimal(eval(str(diff(_lowerCAmelCase ) ) ) )  # noqa: S307
												)
												# This number dictates the accuracy of the answer
												if abs(eval(_lowerCAmelCase ) ) < precision:  # noqa: S307
																		return float(_lowerCAmelCase )


# Let's Execute
if __name__ == "__main__":
	# Find root of trigonometric function
	# Find value of pi
	print(f'''The root of sin(x) = 0 is {newton_raphson("sin(x)", 2)}''')
	# Find root of polynomial
	print(f'''The root of x**2 - 5*x + 2 = 0 is {newton_raphson("x**2 - 5*x + 2", 0.4)}''')
	# Find Square Root of 5
	print(f'''The root of log(x) - 1 = 0 is {newton_raphson("log(x) - 1", 2)}''')
	# Exponential Roots
	print(f'''The root of exp(x) - 1 = 0 is {newton_raphson("exp(x) - 1", 0)}''')





