


"""simple docstring"""
from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

UpperCAmelCase				=						TypeVar("""T""")

def 				_snake_case      (   __snake_case							:      int   ):




   """simple docstring"""







   return (position - 1) // 2

def 				_snake_case      (   __snake_case							:      int   ):




   """simple docstring"""







   return (2 * position) + 1

def 				_snake_case      (   __snake_case							:      int   ):




   """simple docstring"""







   return (2 * position) + 2




class 	lowercase__				(					Generic[T]				):





   def __init__(							self)  ->  None:
      _lowerCamelCase	:					list[tuple[T, int]]   =		[]
      _lowerCamelCase	:					dict[T, int]   =		{}
      _lowerCamelCase	:					int   =		0





   def __len__(							self)  ->  int:
      return self.elements





   def __repr__(							self)  ->  str:
      return str(self.heap)





   def 		UpperCamelCase_  (							self)  ->  bool:
      # Check if the priority queue is empty
      return self.elements == 0





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)  ->  None:
      # Add an element with given priority to the queue
      self.heap.append((elem, weight))
      _lowerCamelCase	:					Any   =		self.elements
      self.elements += 1
      self._bubble_up(SCREAMING_SNAKE_CASE)





   def 		UpperCamelCase_  (							self)  ->  T:
      # Remove and return the element with lowest weight (highest priority)
      if self.elements > 1:
         self._swap_nodes(0      ,   self.elements - 1)
      _lowerCamelCase   ,    _lowerCamelCase	:					Dict   =		self.heap.pop()
      del self.position_map[elem]
      self.elements -= 1
      if self.elements > 0:
         _lowerCamelCase   ,    _lowerCamelCase	:					Tuple   =		self.heap[0]
         self._bubble_down(SCREAMING_SNAKE_CASE)
      return elem





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)  ->  None:
      # Update the weight of the given key
      _lowerCamelCase	:					List[Any]   =		self.position_map[elem]
      _lowerCamelCase	:					Tuple   =		(elem, weight)
      if position > 0:
         _lowerCamelCase	:					List[str]   =		get_parent_position(SCREAMING_SNAKE_CASE)
         _lowerCamelCase   ,    _lowerCamelCase	:					int   =		self.heap[parent_position]
         if parent_weight > weight:
            self._bubble_up(SCREAMING_SNAKE_CASE)
         else:
            self._bubble_down(SCREAMING_SNAKE_CASE)
      else:
         self._bubble_down(SCREAMING_SNAKE_CASE)





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE)  ->  None:
      # Place a node at the proper position (upward movement) [to be used internally
      # only]
      _lowerCamelCase	:					int   =		self.position_map[elem]
      if curr_pos == 0:
         return None
      _lowerCamelCase	:					List[Any]   =		get_parent_position(SCREAMING_SNAKE_CASE)
      _lowerCamelCase   ,    _lowerCamelCase	:					Dict   =		self.heap[curr_pos]
      _lowerCamelCase   ,    _lowerCamelCase	:					List[Any]   =		self.heap[parent_position]
      if parent_weight > weight:
         self._swap_nodes(SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)
         return self._bubble_up(SCREAMING_SNAKE_CASE)
      return None





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE)  ->  None:
      # Place a node at the proper position (downward movement) [to be used
      # internally only]
      _lowerCamelCase	:					int   =		self.position_map[elem]
      _lowerCamelCase   ,    _lowerCamelCase	:					Dict   =		self.heap[curr_pos]
      _lowerCamelCase	:					str   =		get_child_left_position(SCREAMING_SNAKE_CASE)
      _lowerCamelCase	:					int   =		get_child_right_position(SCREAMING_SNAKE_CASE)
      if child_left_position < self.elements and child_right_position < self.elements:
         _lowerCamelCase   ,    _lowerCamelCase	:					Optional[Any]   =		self.heap[child_left_position]
         _lowerCamelCase   ,    _lowerCamelCase	:					Dict   =		self.heap[child_right_position]
         if child_right_weight < child_left_weight and child_right_weight < weight:
            self._swap_nodes(SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)
            return self._bubble_down(SCREAMING_SNAKE_CASE)
      if child_left_position < self.elements:
         _lowerCamelCase   ,    _lowerCamelCase	:					Dict   =		self.heap[child_left_position]
         if child_left_weight < weight:
            self._swap_nodes(SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)
            return self._bubble_down(SCREAMING_SNAKE_CASE)
      else:
         return None
      if child_right_position < self.elements:
         _lowerCamelCase   ,    _lowerCamelCase	:					int   =		self.heap[child_right_position]
         if child_right_weight < weight:
            self._swap_nodes(SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)
            return self._bubble_down(SCREAMING_SNAKE_CASE)
      return None





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)  ->  None:
      # Swap the nodes at the given positions
      _lowerCamelCase	:					List[str]   =		self.heap[nodea_pos][0]
      _lowerCamelCase	:					Dict   =		self.heap[nodea_pos][0]
      _lowerCamelCase   ,    _lowerCamelCase	:					List[Any]   =		(
          self.heap[nodea_pos],
          self.heap[nodea_pos],
      )
      _lowerCamelCase	:					Optional[Any]   =		nodea_pos
      _lowerCamelCase	:					int   =		nodea_pos







class 	lowercase__				(					Generic[T]				):





   def __init__(							self)  ->  None:
      _lowerCamelCase	:					dict[T, dict[T, int]]   =		{}
      _lowerCamelCase	:					int   =		0





   def __repr__(							self)  ->  str:
      return str(self.connections)





   def __len__(							self)  ->  int:
      return self.nodes





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE)  ->  None:
      # Add a node in the graph if it is not in the graph
      if node not in self.connections:
         _lowerCamelCase	:					int   =		{}
         self.nodes += 1





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)  ->  None:
      # Add an edge between 2 nodes in the graph
      self.add_node(SCREAMING_SNAKE_CASE)
      self.add_node(SCREAMING_SNAKE_CASE)
      _lowerCamelCase	:					List[Any]   =		weight
      _lowerCamelCase	:					int   =		weight







def 				_snake_case      (   __snake_case							:      GraphUndirectedWeighted[T]						, ):




   """simple docstring"""







   _lowerCamelCase	:					dict[T, int]   =		{node: maxsize for node in graph.connections}
   _lowerCamelCase	:					dict[T, T | None]   =		{node: None for node in graph.connections}

   _lowerCamelCase	:					MinPriorityQueue[T]   =		MinPriorityQueue()
   for node, weight in dist.items():
      priority_queue.push(__snake_case						, __snake_case   )

   if priority_queue.is_empty():
      return dist, parent

   # initialization
   _lowerCamelCase	:					List[str]   =		priority_queue.extract_min()
   _lowerCamelCase	:					str   =		0
   for neighbour in graph.connections[node]:
      if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
         _lowerCamelCase	:					List[Any]   =		dist[node] + graph.connections[node][neighbour]
         priority_queue.update_key(__snake_case						, dist[neighbour]   )
         _lowerCamelCase	:					Tuple   =		node

    # running prim's algorithm
   while not priority_queue.is_empty():
      _lowerCamelCase	:					List[Any]   =		priority_queue.extract_min()
      for neighbour in graph.connections[node]:
         if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
            _lowerCamelCase	:					Tuple   =		dist[node] + graph.connections[node][neighbour]
            priority_queue.update_key(__snake_case						, dist[neighbour]   )
            _lowerCamelCase	:					List[str]   =		node
   return dist, parent








from __future__ import annotations

import math
import random
from typing import Any


class       __lowerCAmelCase					:


	'''simple docstring'''





	def __init__(						self:						Dict			):
			lowercase__					:      list[Any]      =		[]
			lowercase__					:      int      =		0
			lowercase__					:      int      =		0

	def    snake_case__(						self:						Optional[int]			):
			return self.head == self.tail

	def    snake_case__(						self:						Any,					lowerCamelCase_:						Any			):
			self.data.append(lowerCamelCase_			)
			lowercase__					:      int      =		self.tail + 1

	def    snake_case__(						self:						Tuple			):
			lowercase__					:      Optional[Any]      =		self.data[self.head]
			lowercase__					:      Optional[int]      =		self.head + 1
			return ret

	def    snake_case__(						self:						List[Any]			):
			return self.tail - self.head





	def    snake_case__(						self:						List[Any]			):
			print(self.data			)
			print('**************'			)
			print(self.data[self.head : self.tail]			)


class       __lowerCAmelCase					:


	'''simple docstring'''





	def __init__(						self:						Union[str, Any],					lowerCamelCase_:						Any			):
			lowercase__					:      List[Any]      =		data
			lowercase__					:      MyNode | None      =		None
			lowercase__					:      MyNode | None      =		None
			lowercase__					:      int      =		1

	def    snake_case__(						self:						Optional[Any]			):
			return self.data

	def    snake_case__(						self:						List[str]			):
			return self.left

	def    snake_case__(						self:						Optional[int]			):
			return self.right

	def    snake_case__(						self:						Optional[Any]			):
			return self.height

	def    snake_case__(						self:						Optional[int],					lowerCamelCase_:						Any			):
			lowercase__					:      Tuple      =		data

	def    snake_case__(						self:						Optional[int],					lowerCamelCase_:						MyNode | None			):
			lowercase__					:      Dict      =		node

	def    snake_case__(						self:						Union[str, Any],					lowerCamelCase_:						MyNode | None			):
			lowercase__					:      Optional[Any]      =		node





	def    snake_case__(						self:						List[Any],					lowerCamelCase_:						int			):
			lowercase__					:      Union[str, Any]      =		height


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode | None			)   ->							int:




		'''simple docstring'''
		if node is None:
				return 0
		return node.get_height()


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : int   ,    _lowercase     : int			)   ->							int:




		'''simple docstring'''
		if a > b:
				return a
		return b


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode			)   ->							MyNode:




		'''simple docstring'''
		print('left rotation node:'   ,    node.get_data()			)
		lowercase__					:      Optional[int]      =		node.get_left()
		assert ret is not None
		node.set_left(ret.get_right()			)
		ret.set_right(_lowercase			)
		lowercase__					:      List[str]      =		my_max(get_height(node.get_right()			)   ,    get_height(node.get_left()			)			) + 1
		node.set_height(_lowercase			)
		lowercase__					:      Optional[Any]      =		my_max(get_height(ret.get_right()			)   ,    get_height(ret.get_left()			)			) + 1
		ret.set_height(_lowercase			)
		return ret


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode			)   ->							MyNode:




		'''simple docstring'''
		print('right rotation node:'   ,    node.get_data()			)
		lowercase__					:      Union[str, Any]      =		node.get_right()
		assert ret is not None
		node.set_right(ret.get_left()			)
		ret.set_left(_lowercase			)
		lowercase__					:      str      =		my_max(get_height(node.get_right()			)   ,    get_height(node.get_left()			)			) + 1
		node.set_height(_lowercase			)
		lowercase__					:      List[str]      =		my_max(get_height(ret.get_right()			)   ,    get_height(ret.get_left()			)			) + 1
		ret.set_height(_lowercase			)
		return ret


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode			)   ->							MyNode:




		'''simple docstring'''
		lowercase__					:      str      =		node.get_left()
		assert left_child is not None
		node.set_left(left_rotation(_lowercase			)			)
		return right_rotation(_lowercase			)


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode			)   ->							MyNode:




		'''simple docstring'''
		lowercase__					:      Optional[Any]      =		node.get_right()
		assert right_child is not None
		node.set_right(right_rotation(_lowercase			)			)
		return left_rotation(_lowercase			)


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode | None   ,    _lowercase     : Any			)   ->							MyNode | None:




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


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode			)   ->							Any:




		'''simple docstring'''
		while True:
				lowercase__					:      List[Any]      =		root.get_right()
				if right_child is None:
						break
				lowercase__					:      List[str]      =		right_child
		return root.get_data()


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode			)   ->							Any:




		'''simple docstring'''
		while True:
				lowercase__					:      Any      =		root.get_left()
				if left_child is None:
						break
				lowercase__					:      List[str]      =		left_child
		return root.get_data()


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : MyNode   ,    _lowercase     : Any			)   ->							MyNode | None:




		'''simple docstring'''
		lowercase__					:      List[Any]      =		root.get_left()
		lowercase__					:      List[Any]      =		root.get_right()
		if root.get_data() == data:
				if left_child is not None and right_child is not None:
						lowercase__					:      Dict      =		get_left_most(_lowercase			)
						root.set_data(_lowercase			)
						root.set_right(del_node(_lowercase   ,    _lowercase			)			)
				elif left_child is not None:
						lowercase__					:      List[Any]      =		left_child
				elif right_child is not None:
						lowercase__					:      Dict      =		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(_lowercase   ,    _lowercase			)			)
		else:  # root.get_data() < data
				if right_child is None:
						return root
				else:
						root.set_right(del_node(_lowercase   ,    _lowercase			)			)

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


class       __lowerCAmelCase					:


	'''simple docstring'''





	def __init__(						self:						str			):
			lowercase__					:      MyNode | None      =		None

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

	def    snake_case__(						self:						List[Any],					lowerCamelCase_:						Any			):
			print('insert:' + str(lowerCamelCase_			)			)
			lowercase__					:      int      =		insert_node(self.root,					lowerCamelCase_			)

	def    snake_case__(						self:						Tuple,					lowerCamelCase_:						Any			):
			print('delete:' + str(lowerCamelCase_			)			)
			if self.root is None:
					print('Tree is empty!'			)
					return
			lowercase__					:      int      =		del_node(self.root,					lowerCamelCase_			)





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


def       SCREAMING_SNAKE_CASE__  (       )   ->							None:




		'''simple docstring'''
		import doctest

		doctest.testmod()


if __name__ == "__main__":
			_test()
			__UpperCamelCase:	int = AVLtree()
			__UpperCamelCase:	int = list(range(1_0))
			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))


