


from __future__ import annotations

import math
import random
from typing import Any



class 			lowerCamelCase__						:







						def __init__(							self   :    Any		):
								A					       = []
								A					       = 0
								A					       = 0







						def __a						(							self   :    List[str]		):
								return self.head == self.tail







						def __a						(							self   :    Optional[int]			,			_lowercase   :    Any		):
								self.data.append(_lowercase		)
								A					       = self.tail + 1







						def __a						(							self   :    Union[str, Any]		):
								A					       = self.data[self.head]
								A					       = self.head + 1
								return ret







						def __a						(							self   :    Tuple		):
								return self.tail - self.head







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



class 			lowerCamelCase__						:







						def __init__(							self   :    List[Any]			,			_lowercase   :    Any		):
								A					       = data
								A					       = None
								A					       = None
								A					       = 1







						def __a						(							self   :    int		):
								return self.data







						def __a						(							self   :    Union[str, Any]		):
								return self.left







						def __a						(							self   :    List[Any]		):
								return self.right







						def __a						(							self   :    Dict		):
								return self.height







						def __a						(							self   :    Optional[Any]			,			_lowercase   :    Any		):
								A					       = data







						def __a						(							self   :    Any			,			_lowercase   :    MyNode | None		):
								A					       = node







						def __a						(							self   :    Any			,			_lowercase   :    MyNode | None		):
								A					       = node







						def __a						(							self   :    Tuple			,			_lowercase   :    int		):
								A					       = height







def  __snake_case       (   UpperCamelCase__	)      ->		str:







		"""simple docstring"""





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







def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		str:







		"""simple docstring"""





		if a > b:
				return a
		return b







def  __snake_case       (   UpperCamelCase__	)      ->		str:







		"""simple docstring"""





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







def  __snake_case       (   UpperCamelCase__	)      ->		Dict:







		"""simple docstring"""





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







def  __snake_case       (   UpperCamelCase__	)      ->		List[Any]:







		"""simple docstring"""





		A					       = node.get_left()
		assert left_child is not None
		node.set_left(left_rotation(_lowerCamelCase	)	)
		return right_rotation(_lowerCamelCase	)







def  __snake_case       (   UpperCamelCase__	)      ->		Tuple:







		"""simple docstring"""





		A					       = node.get_right()
		assert right_child is not None
		node.set_right(right_rotation(_lowerCamelCase	)	)
		return left_rotation(_lowerCamelCase	)







def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		List[Any]:







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







def  __snake_case       (   UpperCamelCase__	)      ->		Tuple:







		"""simple docstring"""





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







def  __snake_case       (   UpperCamelCase__	)      ->		List[Any]:







		"""simple docstring"""





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







def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__	)      ->		Any:







		"""simple docstring"""





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



class 			lowerCamelCase__						:







						def __init__(							self   :    List[Any]		):
								A					       = None







						def __a						(							self   :    Optional[Any]		):
								return get_height(self.root		)







						def __a						(							self   :    Optional[Any]			,			_lowercase   :    Any		):
								print('insert:' + str(_lowercase		)		)
								A					       = insert_node(self.root			,			_lowercase		)







						def __a						(							self   :    Any			,			_lowercase   :    Any		):
								print('delete:' + str(_lowercase		)		)
								if self.root is None:
										print('Tree is empty!'		)
										return
								A					       = del_node(self.root			,			_lowercase		)







						def __str__(							self   :    str			,			):  # a level traversale, gives a more intuitive look on the tree
								A					       = ""
								A					       = MyQueue()
								q.push(self.root		)
								A					       = self.get_height()
								if layer == 0:
										return output
								A					       = 0
								while not q.is_empty():
										A					       = q.pop()
										A					       = " " * int(math.pow(2			,			layer - 1		)		)
										output += space
										if node is None:
												output += "*"
												q.push(_lowercase		)
												q.push(_lowercase		)
										else:
												output += str(node.get_data()		)
												q.push(node.get_left()		)
												q.push(node.get_right()		)
										output += space
										A					       = cnt + 1
										for i in range(100		):
												if cnt == math.pow(2			,			_lowercase		) - 1:
														A					       = layer - 1
														if layer == 0:
																output += "\n*************************************"
																return output
														output += "\n"
														break
								output += "\n*************************************"
								return output







def  __snake_case       (   )      ->		List[Any]:







		"""simple docstring"""





		import doctest

		doctest.testmod()


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









"""simple docstring"""


from math import factorial







def  __snake_case       (   UpperCamelCase__ ,			UpperCamelCase__ ,			UpperCamelCase__	)      ->		float:







		"""simple docstring"""





		if successes > trials:
				raise ValueError('successes must be lower or equal to trials'	)
		if trials < 0 or successes < 0:
				raise ValueError('the function is defined for non-negative integers'	)
		if not isinstance(UpperCamelCase__ ,			UpperCamelCase__	) or not isinstance(UpperCamelCase__ ,			UpperCamelCase__	):
				raise ValueError('the function is defined for non-negative integers'	)
		if not 0 < prob < 1:
				raise ValueError('prob has to be in range of 1 - 0'	)
		A					       = (prob**successes) * ((1 - prob) ** (trials - successes))
		# Calculate the binomial coefficient: n! / k!(n-k)!
		A					       = float(factorial(UpperCamelCase__	)	)
		coefficient /= factorial(UpperCamelCase__	) * factorial(trials - successes	)
		return probability * coefficient


if __name__ == "__main__":
	from doctest import testmod

	testmod()
	print("Probability of 2 successes out of 4 trails")
	print("with probability of 0.75 is:", end=" ")
	print(binomial_distribution(2, 4, 0.75))





