"""simple docstring"""
from collections.abc import Iterable
from typing import Any



class      lowerCAmelCase_			:



				"""simple docstring"""

				def __init__( self						,			lowerCAmelCase = None			):






										"""simple docstring"""

										snake_case	    =	value
										snake_case	    =	None  # Added in order to delete a node easier
										snake_case	    =	None
										snake_case	    =	None

				def __repr__( self			):






										"""simple docstring"""

										from pprint import pformat

										if self.left is None and self.right is None:
																return str(self.value			)
										return pformat({F"""{self.value}""": (self.left, self.right)}						,			indent=1			)





class      lowerCAmelCase_			:



				"""simple docstring"""

				def __init__( self						,			lowerCAmelCase = None			):






										"""simple docstring"""

										snake_case	    =	root

				def __str__( self			):






										"""simple docstring"""

										return str(self.root			)

				def 						snake_case       ( self						,			lowerCAmelCase						,			lowerCAmelCase			):






										"""simple docstring"""

										if new_children is not None:  # reset its kids
																snake_case	    =	node.parent
										if node.parent is not None:  # reset its parent
																if self.is_right(lowercase__			):  # If it is the right children
																						snake_case	    =	new_children
																else:
																						snake_case	    =	new_children
										else:
																snake_case	    =	new_children

				def 						snake_case       ( self						,			lowerCAmelCase			):






										"""simple docstring"""

										if node.parent and node.parent.right:
																return node == node.parent.right
										return False

				def 						snake_case       ( self			):






										"""simple docstring"""

										return self.root is None

				def 						snake_case       ( self						,			lowerCAmelCase			):






										"""simple docstring"""

										snake_case	    =	Node(lowercase__			)  # create a new Node
										if self.empty():  # if Tree is empty
																snake_case	    =	new_node  # set its root
										else:  # Tree is not empty
																snake_case	    =	self.root  # from root
																if parent_node is None:
																						return
																while True:  # While we don't get to a leaf
																						if value < parent_node.value:  # We go left
																												if parent_node.left is None:
																																		snake_case	    =	new_node  # We insert the new node in a leaf
																																		break
																												else:
																																		snake_case	    =	parent_node.left
																						else:
																												if parent_node.right is None:
																																		snake_case	    =	new_node
																																		break
																												else:
																																		snake_case	    =	parent_node.right
																snake_case	    =	parent_node

				def 						snake_case       ( self						,			*lowerCAmelCase			):






										"""simple docstring"""

										for value in values:
																self.__insert(lowercase__			)

				def 						snake_case       ( self						,			lowerCAmelCase			):






										"""simple docstring"""

										if self.empty():
																raise IndexError('Warning: Tree is empty! please use another.'			)
										else:
																snake_case	    =	self.root
																# use lazy evaluation here to avoid NoneType Attribute error
																while node is not None and node.value is not value:
																						snake_case	    =	node.left if value < node.value else node.right
																return node

				def 						snake_case       ( self						,			lowerCAmelCase = None			):






										"""simple docstring"""

										if node is None:
																if self.root is None:
																						return None
																snake_case	    =	self.root

										if not self.empty():
																while node.right is not None:
																						snake_case	    =	node.right
										return node

				def 						snake_case       ( self						,			lowerCAmelCase = None			):






										"""simple docstring"""

										if node is None:
																snake_case	    =	self.root
										if self.root is None:
																return None
										if not self.empty():
																snake_case	    =	self.root
																while node.left is not None:
																						snake_case	    =	node.left
										return node

				def 						snake_case       ( self						,			lowerCAmelCase			):






										"""simple docstring"""

										snake_case	    =	self.search(lowercase__			)  # Look for the node with that label
										if node is not None:
																if node.left is None and node.right is None:  # If it has no children
																						self.__reassign_nodes(lowercase__						,			lowercase__			)
																elif node.left is None:  # Has only right children
																						self.__reassign_nodes(lowercase__						,			node.right			)
																elif node.right is None:  # Has only left children
																						self.__reassign_nodes(lowercase__						,			node.left			)
																else:
																						snake_case	    =	self.get_max(
																						    node.left			)  # Gets the max value of the left branch
																						self.remove(tmp_node.value			)  # type: ignore
																						snake_case	    =	(
																						    tmp_node.value  # type: ignore
																						)  # Assigns the value to the node to delete and keep tree structure

				def 						snake_case       ( self						,			lowerCAmelCase			):






										"""simple docstring"""

										if node is not None:
																yield node  # Preorder Traversal
																yield from self.preorder_traverse(node.left			)
																yield from self.preorder_traverse(node.right			)

				def 						snake_case       ( self						,			lowerCAmelCase=None			):






										"""simple docstring"""

										if traversal_function is None:
																return self.preorder_traverse(self.root			)
										else:
																return traversal_function(self.root			)

				def 						snake_case       ( self						,			lowerCAmelCase						,			lowerCAmelCase			):






										"""simple docstring"""

										if node:
																self.inorder(lowercase__						,			node.left			)
																arr.append(node.value			)
																self.inorder(lowercase__						,			node.right			)

				def 						snake_case       ( self						,			lowerCAmelCase						,			lowerCAmelCase			):






										"""simple docstring"""

										snake_case	    =	[]
										self.inorder(lowercase__						,			lowercase__			)  # append all values to list using inorder traversal
										return arr[k - 1]





def       lowerCAmelCase__			(	_UpperCamelCase				: Tuple    )    -> int:





						"""simple docstring"""






						snake_case	    =	[]
						if curr_node is not None:
												snake_case	    =	postorder(curr_node.left    ) + postorder(curr_node.right    ) + [curr_node]
						return node_list





def       lowerCAmelCase__			(	)    -> List[Any]:





						"""simple docstring"""






						snake_case	    =	(8, 3, 6, 1, 1_0, 1_4, 1_3, 4, 7)
						snake_case	    =	BinarySearchTree()
						for i in testlist:
												t.insert(A__    )

						# Prints all the elements of the list in order traversal
						print(A__    )

						if t.search(6    ) is not None:
												print('The value 6 exists'    )
						else:
												print('The value 6 doesn\'t exist'    )

						if t.search(-1    ) is not None:
												print('The value -1 exists'    )
						else:
												print('The value -1 doesn\'t exist'    )

						if not t.empty():
												print('Max Value: '       ,	t.get_max().value    )  # type: ignore
												print('Min Value: '       ,	t.get_min().value    )  # type: ignore

						for i in testlist:
												t.remove(A__    )
												print(A__    )


if __name__ == "__main__":
					import doctest

					doctest.testmod(verbose=True)





'''simple docstring'''






from __future__ import annotations

from random import random
from typing import Generic, TypeVar

lowerCAmelCase__											=	TypeVar('''KT''')
lowerCAmelCase__											=	TypeVar('''VT''')






class 			lowercase_	(Generic[KT, VT]      ):




  """simple docstring"""




  def __init__(      self   :     Optional[Any]					,lowercase__   :     KT | str = "root"					,lowercase__   :     VT | None = None			):
   __lowercase							  = key
   __lowercase							  = value
   __lowercase							  = []






  def __repr__(      self   :     Tuple			):
   return F"Node({self.key}: {self.value})"






  @property
  def 					SCREAMING_SNAKE_CASE      (      self   :     int			):
   return len(self.forward			)






class 			lowercase_	(Generic[KT, VT]      ):




  """simple docstring"""




  def __init__(      self   :     int					,lowercase__   :     float = 0.5					,lowercase__   :     int = 1_6			):
   __lowercase							  = Node[KT, VT]()
   __lowercase							  = 0
   __lowercase							  = p
   __lowercase							  = max_level






  def __str__(      self   :     List[str]			):
   __lowercase							  = list(self			)

   if len(lowercase__			) == 0:
    return F"SkipList(level={self.level})"

   __lowercase							  = max((len(str(lowercase__			)			) for item in items)					,default=4			)
   __lowercase							  = max(lowercase__					,4			) + 4

   __lowercase							  = self.head
   __lowercase							  = []

   __lowercase							  = node.forward.copy()
   lines.append(F"[{node.key}]".ljust(lowercase__					,'''-'''			) + '''* ''' * len(lowercase__			)			)
   lines.append(''' ''' * label_size + '''| ''' * len(lowercase__			)			)

   while len(node.forward			) != 0:
    __lowercase							  = node.forward[0]

    lines.append(
        F"[{node.key}]".ljust(lowercase__					,'''-'''			)
        + ''' '''.join(str(n.key			) if n.key == node.key else '''|''' for n in forwards			)			)
    lines.append(''' ''' * label_size + '''| ''' * len(lowercase__			)			)
    __lowercase							  = node.forward

   lines.append('''None'''.ljust(lowercase__			) + '''* ''' * len(lowercase__			)			)
   return F"SkipList(level={self.level})\n" + "\n".join(lowercase__			)






  def __iter__(      self   :     List[str]			):
   __lowercase							  = self.head

   while len(node.forward			) != 0:
    yield node.forward[0].key
    __lowercase							  = node.forward[0]






  def 					SCREAMING_SNAKE_CASE      (      self   :     Optional[Any]			):
   __lowercase							  = 1
   while random() < self.p and level < self.max_level:
    level += 1

   return level






  def 					SCREAMING_SNAKE_CASE      (      self   :     List[str]					,lowercase__   :     str			):
   __lowercase							  = []

   __lowercase							  = self.head

   for i in reversed(range(self.level			)			):
    # i < node.level - When node level is lesser than `i` decrement `i`.
    # node.forward[i].key < key - Jumping to node with key value higher
    #                             or equal to searched key would result
    #                             in skipping searched key.
    while i < node.level and node.forward[i].key < key:
     __lowercase							  = node.forward[i]
    # Each leftmost node (relative to searched node) will potentially have to
    # be updated.
    update_vector.append(lowercase__			)

   update_vector.reverse()  # Note that we were inserting values in reverse order.

   # len(node.forward) != 0 - If current node doesn't contain any further
   #                          references then searched key is not present.
   # node.forward[0].key == key - Next node key should be equal to search key
   #                              if key is present.
   if len(node.forward			) != 0 and node.forward[0].key == key:
    return node.forward[0], update_vector
   else:
    return None, update_vector






  def 					SCREAMING_SNAKE_CASE      (      self   :     List[str]					,lowercase__   :     KT			):
   __lowercase  ,	__lowercase							  = self._locate_node(lowercase__			)

   if node is not None:
    for i, update_node in enumerate(lowercase__			):
     # Remove or replace all references to removed node.
     if update_node.level > i and update_node.forward[i].key == key:
      if node.level > i:
       __lowercase							  = node.forward[i]
      else:
       __lowercase							  = update_node.forward[:i]






  def 					SCREAMING_SNAKE_CASE      (      self   :     List[str]					,lowercase__   :     KT					,lowercase__   :     VT			):
   __lowercase  ,	__lowercase							  = self._locate_node(lowercase__			)
   if node is not None:
    __lowercase							  = value
   else:
    __lowercase							  = self.random_level()

    if level > self.level:
     # After level increase we have to add additional nodes to head.
     for _ in range(self.level - 1					,lowercase__			):
      update_vector.append(self.head			)
     __lowercase							  = level

    __lowercase							  = Node(lowercase__					,lowercase__			)

    for i, update_node in enumerate(update_vector[:level]			):
     # Change references to pass through new node.
     if update_node.level > i:
      new_node.forward.append(update_node.forward[i]			)

     if update_node.level < i + 1:
      update_node.forward.append(lowercase__			)
     else:
      __lowercase							  = new_node






  def 					SCREAMING_SNAKE_CASE      (      self   :     List[Any]					,lowercase__   :     VT			):
   __lowercase  ,	__lowercase							  = self._locate_node(lowercase__			)

   if node is not None:
    return node.value

   return None


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()
 skip_list.insert('''Key1'''     ,				3      )
 skip_list.insert('''Key2'''     ,				12      )
 skip_list.insert('''Key3'''     ,				41      )
 skip_list.insert('''Key4'''     ,				-19      )

 __lowercase							  = skip_list.head
 __lowercase							  = {}
 while node.level != 0:
  __lowercase							  = node.forward[0]
  __lowercase							  = node.value

 assert len(A__      ) == 4
 assert all_values["Key1"] == 3
 assert all_values["Key2"] == 12
 assert all_values["Key3"] == 41
 assert all_values["Key4"] == -19


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()
 skip_list.insert('''Key1'''     ,				10      )
 skip_list.insert('''Key1'''     ,				12      )

 skip_list.insert('''Key5'''     ,				7      )
 skip_list.insert('''Key7'''     ,				10      )
 skip_list.insert('''Key10'''     ,				5      )

 skip_list.insert('''Key7'''     ,				7      )
 skip_list.insert('''Key5'''     ,				5      )
 skip_list.insert('''Key10'''     ,				10      )

 __lowercase							  = skip_list.head
 __lowercase							  = {}
 while node.level != 0:
  __lowercase							  = node.forward[0]
  __lowercase							  = node.value

 if len(A__      ) != 4:
  print()
 assert len(A__      ) == 4
 assert all_values["Key1"] == 12
 assert all_values["Key7"] == 7
 assert all_values["Key5"] == 5
 assert all_values["Key10"] == 10


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()
 assert skip_list.find('''Some key'''      ) is None


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()

 skip_list.insert('''Key2'''     ,				20      )
 assert skip_list.find('''Key2'''      ) == 20

 skip_list.insert('''Some Key'''     ,				10      )
 skip_list.insert('''Key2'''     ,				8      )
 skip_list.insert('''V'''     ,				13      )

 assert skip_list.find('''Y'''      ) is None
 assert skip_list.find('''Key2'''      ) == 8
 assert skip_list.find('''Some Key'''      ) == 10
 assert skip_list.find('''V'''      ) == 13


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()
 skip_list.delete('''Some key'''      )

 assert len(skip_list.head.forward      ) == 0


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()

 skip_list.insert('''Key1'''     ,				12      )
 skip_list.insert('''V'''     ,				13      )
 skip_list.insert('''X'''     ,				14      )
 skip_list.insert('''Key2'''     ,				15      )

 skip_list.delete('''V'''      )
 skip_list.delete('''Key2'''      )

 assert skip_list.find('''V'''      ) is None
 assert skip_list.find('''Key2'''      ) is None


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()

 skip_list.insert('''Key1'''     ,				12      )
 skip_list.insert('''V'''     ,				13      )
 skip_list.insert('''X'''     ,				14      )
 skip_list.insert('''Key2'''     ,				15      )

 skip_list.delete('''V'''      )
 assert skip_list.find('''V'''      ) is None
 assert skip_list.find('''X'''      ) == 14
 assert skip_list.find('''Key1'''      ) == 12
 assert skip_list.find('''Key2'''      ) == 15

 skip_list.delete('''X'''      )
 assert skip_list.find('''V'''      ) is None
 assert skip_list.find('''X'''      ) is None
 assert skip_list.find('''Key1'''      ) == 12
 assert skip_list.find('''Key2'''      ) == 15

 skip_list.delete('''Key1'''      )
 assert skip_list.find('''V'''      ) is None
 assert skip_list.find('''X'''      ) is None
 assert skip_list.find('''Key1'''      ) is None
 assert skip_list.find('''Key2'''      ) == 15

 skip_list.delete('''Key2'''      )
 assert skip_list.find('''V'''      ) is None
 assert skip_list.find('''X'''      ) is None
 assert skip_list.find('''Key1'''      ) is None
 assert skip_list.find('''Key2'''      ) is None


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()

 skip_list.insert('''Key1'''     ,				12      )
 skip_list.insert('''V'''     ,				13      )
 skip_list.insert('''X'''     ,				142      )
 skip_list.insert('''Key2'''     ,				15      )

 skip_list.delete('''X'''      )

 def traverse_keys(A__      ):
  yield node.key
  for forward_node in node.forward:
   yield from traverse_keys(A__      )

 assert len(set(traverse_keys(skip_list.head      )      )      ) == 4


def 		_A     (    ):






 """simple docstring"""



 def is_sorted(A__      ):
  return all(next_item >= item for item, next_item in zip(A__     ,				lst[1:]      )      )

 __lowercase							  = SkipList()
 for i in range(10      ):
  skip_list.insert(A__     ,				A__      )
 assert is_sorted(list(A__      )      )
 skip_list.delete(5      )
 skip_list.delete(8      )
 skip_list.delete(2      )
 assert is_sorted(list(A__      )      )
 skip_list.insert(-12     ,				-12      )
 skip_list.insert(77     ,				77      )
 assert is_sorted(list(A__      )      )


def 		_A     (    ):






 """simple docstring"""



 for _ in range(100      ):
  # Repeat test 100 times due to the probabilistic nature of skip list
  # random values == random bugs
  test_insert()
  test_insert_overrides_existing_value()

  test_searching_empty_list_returns_none()
  test_search()

  test_deleting_item_from_empty_list_do_nothing()
  test_deleted_items_are_not_founded_by_find_method()
  test_delete_removes_only_given_key()
  test_delete_doesnt_leave_dead_nodes()

  test_iter_always_yields_sorted_values()


def 		_A     (    ):






 """simple docstring"""



 __lowercase							  = SkipList()
 skip_list.insert(2     ,				'''2'''      )
 skip_list.insert(4     ,				'''4'''      )
 skip_list.insert(6     ,				'''4'''      )
 skip_list.insert(4     ,				'''5'''      )
 skip_list.insert(8     ,				'''4'''      )
 skip_list.insert(9     ,				'''4'''      )

 skip_list.delete(4      )

 print(A__      )


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 main()

