






import numpy

# List of input, output pairs
SCREAMING_SNAKE_CASE__				     =			(
    ((5, 2, 3), 15),
    ((6, 5, 9), 25),
    ((11, 12, 13), 41),
    ((1, 1, 1), 8),
    ((11, 12, 13), 41),
)
SCREAMING_SNAKE_CASE__				     =			(((515, 22, 13), 555), ((61, 35, 49), 150))
SCREAMING_SNAKE_CASE__				     =			[2, 4, 1, 5]
SCREAMING_SNAKE_CASE__				     =			len(train_data)
SCREAMING_SNAKE_CASE__				     =			0.0_0_9

def        UpperCAmelCase__		(						lowerCamelCase_       :       Union[str, Any]   ,  lowerCamelCase_       :       Dict="train"				):
			return calculate_hypothesis_value(lowerCamelCase_   ,  lowerCamelCase_				) - output(
			    lowerCamelCase_   ,  lowerCamelCase_				)

def        UpperCAmelCase__		(						lowerCamelCase_       :       Optional[int]				):
			__a						:  List[Any]									=     0
			for i in range(len(lowerCamelCase_				) - 1				):
						hyp_val += data_input_tuple[i] * parameter_vector[i + 1]
			hyp_val += parameter_vector[0]
			return hyp_val

def        UpperCAmelCase__		(						lowerCamelCase_       :       Optional[Any]   ,  lowerCamelCase_       :       Optional[int]				):
			if data_set == "train":
						return train_data[example_no][1]
			elif data_set == "test":
						return test_data[example_no][1]
			return None

def        UpperCAmelCase__		(						lowerCamelCase_       :       List[Any]   ,  lowerCamelCase_       :       Optional[Any]				):
			if data_set == "train":
						return _hypothesis_value(train_data[example_no][0]				)
			elif data_set == "test":
						return _hypothesis_value(test_data[example_no][0]				)
			return None

def        UpperCAmelCase__		(						lowerCamelCase_       :       Optional[int]   ,  lowerCamelCase_       :       Optional[int]=m				):
			__a						:  Optional[Any]									=     0
			for i in range(lowerCamelCase_				):
						if index == -1:
									summation_value += _error(lowerCamelCase_				)
						else:
									summation_value += _error(lowerCamelCase_				) * train_data[i][0][index]
			return summation_value

def        UpperCAmelCase__		(						lowerCamelCase_       :       Optional[Any]				):
			__a						:  Union[str, Any]									=     summation_of_cost_derivative(lowerCamelCase_   ,  lowerCamelCase_				) / m
			return cost_derivative_value

def        UpperCAmelCase__		(						):
			global parameter_vector
			# Tune these values to set a tolerance value for predicted output
			__a						:  List[str]									=     0.000002
			__a						:  str									=     0
			__a						:  List[str]									=     0
			while True:
						j += 1
						__a						:  Dict									=     [0, 0, 0, 0]
						for i in range(0   ,  len(lowerCamelCase_				)				):
									__a						:  List[Any]									=     get_cost_derivative(i - 1				)
									__a						:  Dict									=     (
									    parameter_vector[i] - LEARNING_RATE * cost_derivative
									)
						if numpy.allclose(
						    lowerCamelCase_   ,  lowerCamelCase_   ,  atol=lowerCamelCase_   ,  rtol=lowerCamelCase_   ,  ):
									break
						__a						:  Dict									=     temp_parameter_vector
			print(('Number of iterations:', j)				)

def        UpperCAmelCase__		(						):
			for i in range(len(lowerCamelCase_				)				):
						print(('Actual output value:', output(lowerCamelCase_   ,  'test'				))				)
						print(('Hypothesis output:', calculate_hypothesis_value(lowerCamelCase_   ,  'test'				))				)


if __name__ == "__main__":
							run_gradient_descent()
							print('''\nTesting gradient descent for a linear hypothesis function.\n''')
							test_gradient_descent()












from __future__ import annotations

import math
import random
from typing import Any


class        __magic_name__	:





     """simple docstring"""



     def __init__(				self							:Tuple	):





        '''simple docstring'''




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



     def     SCREAMING_SNAKE_CASE		(				self							:List[Any]	):





        '''simple docstring'''




        return self.head == self.tail



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[Any]      ,   snake_case							:Any	):





        '''simple docstring'''




        self.data.append(snake_case	)
        A_       :					int        =      self.tail + 1



     def     SCREAMING_SNAKE_CASE		(				self							:str	):





        '''simple docstring'''




        A_       :					int        =      self.data[self.head]
        A_       :					Tuple        =      self.head + 1
        return ret



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[int]	):





        '''simple docstring'''




        return self.tail - self.head





     def     SCREAMING_SNAKE_CASE		(				self							:Any	):





        '''simple docstring'''




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




class        __magic_name__	:





     """simple docstring"""



     def __init__(				self							:Any      ,   snake_case							:Any	):





        '''simple docstring'''




        A_       :					Any        =      data
        A_       :					MyNode | None        =      None
        A_       :					MyNode | None        =      None
        A_       :					int        =      1



     def     SCREAMING_SNAKE_CASE		(				self							:List[str]	):





        '''simple docstring'''




        return self.data



     def     SCREAMING_SNAKE_CASE		(				self							:Dict	):





        '''simple docstring'''




        return self.left



     def     SCREAMING_SNAKE_CASE		(				self							:Any	):





        '''simple docstring'''




        return self.right



     def     SCREAMING_SNAKE_CASE		(				self							:List[Any]	):





        '''simple docstring'''




        return self.height



     def     SCREAMING_SNAKE_CASE		(				self							:List[str]      ,   snake_case							:Any	):





        '''simple docstring'''




        A_       :					Optional[int]        =      data



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[int]      ,   snake_case							:MyNode | None	):





        '''simple docstring'''




        A_       :					Tuple        =      node



     def     SCREAMING_SNAKE_CASE		(				self							:str      ,   snake_case							:MyNode | None	):





        '''simple docstring'''




        A_       :					str        =      node





     def     SCREAMING_SNAKE_CASE		(				self							:Tuple      ,   snake_case							:int	):





        '''simple docstring'''




        A_       :					Optional[int]        =      height




def   __snake_case    (       _lowerCAmelCase			:			MyNode | None						)			->    int:
   if node is None:
      return 0
   return node.get_height()

def   __snake_case    (       _lowerCAmelCase			:			int					,					_lowerCAmelCase			:			int						)			->    int:
   if a > b:
      return a
   return b

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

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    MyNode:
   print("right rotation node:"					,					node.get_data()						)
   A_       :					Union[str, Any]        =      node.get_right()
   assert ret is not None
   node.set_right(ret.get_left()						)
   ret.set_left(_lowerCAmelCase						)
   A_       :					int        =      my_max(get_height(node.get_right()						)					,					get_height(node.get_left()						)						) + 1
   node.set_height(_lowerCAmelCase						)
   A_       :					Dict        =      my_max(get_height(ret.get_right()						)					,					get_height(ret.get_left()						)						) + 1
   ret.set_height(_lowerCAmelCase						)
   return ret

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    MyNode:
   A_       :					List[Any]        =      node.get_left()
   assert left_child is not None
   node.set_left(left_rotation(_lowerCAmelCase						)						)
   return right_rotation(_lowerCAmelCase						)

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    MyNode:
   A_       :					List[Any]        =      node.get_right()
   assert right_child is not None
   node.set_right(right_rotation(_lowerCAmelCase						)						)
   return left_rotation(_lowerCAmelCase						)

def   __snake_case    (       _lowerCAmelCase			:			MyNode | None					,					_lowerCAmelCase			:			Any						)			->    MyNode | None:
   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_       :					Any        =      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_       :					Optional[int]        =      right_rotation(_lowerCAmelCase						)
         else:
            A_       :					int        =      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_       :					Dict        =      node.get_right()
         assert right_child is not None
         if data < right_child.get_data():
            A_       :					Optional[Any]        =      rl_rotation(_lowerCAmelCase						)
         else:
            A_       :					Dict        =      left_rotation(_lowerCAmelCase						)
   A_       :					Optional[int]        =      my_max(get_height(node.get_right()						)					,					get_height(node.get_left()						)						) + 1
   node.set_height(_lowerCAmelCase						)
   return node

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    Any:
   while True:
      A_       :					Any        =      root.get_right()
      if right_child is None:
         break
      A_       :					Optional[Any]        =      right_child
   return root.get_data()

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    Any:
   while True:
      A_       :					Optional[Any]        =      root.get_left()
      if left_child is None:
         break
      A_       :					int        =      left_child
   return root.get_data()

def   __snake_case    (       _lowerCAmelCase			:			MyNode					,					_lowerCAmelCase			:			Any						)			->    MyNode | None:
   A_       :					Optional[int]        =      root.get_left()
   A_       :					Dict        =      root.get_right()
   if root.get_data() == data:
      if left_child is not None and right_child is not None:
         A_       :					int        =      get_left_most(_lowerCAmelCase						)
         root.set_data(_lowerCAmelCase						)
         root.set_right(del_node(_lowerCAmelCase					,					_lowerCAmelCase						)						)
      elif left_child is not None:
         A_       :					Tuple        =      left_child
      elif right_child is not None:
         A_       :					Any        =      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_       :					Dict        =      left_rotation(_lowerCAmelCase						)
      else:
         A_       :					List[Any]        =      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_       :					Optional[Any]        =      right_rotation(_lowerCAmelCase						)
      else:
         A_       :					Tuple        =      lr_rotation(_lowerCAmelCase						)
   A_       :					List[str]        =      my_max(get_height(root.get_right()						)					,					get_height(root.get_left()						)						) + 1
   root.set_height(_lowerCAmelCase						)
   return root


class        __magic_name__	:





     """simple docstring"""



     def __init__(				self							:List[str]	):





        '''simple docstring'''




        A_       :					MyNode | None        =      None



     def     SCREAMING_SNAKE_CASE		(				self							:List[Any]	):





        '''simple docstring'''




        return get_height(self.root	)



     def     SCREAMING_SNAKE_CASE		(				self							:str      ,   snake_case							:Any	):





        '''simple docstring'''




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



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[Any]      ,   snake_case							:Any	):





        '''simple docstring'''




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





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





        '''simple docstring'''




        A_       :					Optional[Any]        =      ""
        A_       :					Optional[int]        =      MyQueue()
        q.push(self.root	)
        A_       :					Optional[int]        =      self.get_height()
        if layer == 0:
           return output
        A_       :					Dict        =      0
        while not q.is_empty():
           A_       :					Optional[int]        =      q.pop()
           A_       :					Union[str, Any]        =      " " * int(math.pow(2      ,   layer - 1	)	)
           output += space
           if node is None:
              output += "*"
              q.push(snake_case	)
              q.push(snake_case	)
           else:
              output += str(node.get_data()	)
              q.push(node.get_left()	)
              q.push(node.get_right()	)
           output += space
           A_       :					str        =      cnt + 1
           for i in range(100	):
              if cnt == math.pow(2      ,   snake_case	) - 1:
                 A_       :					int        =      layer - 1
                 if layer == 0:
                    output += "\n*************************************"
                    return output
                 output += "\n"
                 break
        output += "\n*************************************"
        return output




def   __snake_case    (       )			->    None:
   import doctest

   doctest.testmod()


if __name__ == "__main__":
 _test()
 _lowerCAmelCase				:   int						       =						AVLtree()
 _lowerCAmelCase				:   Optional[int]						       =						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))
