
'''simple docstring'''







# This Python program implements an optimal binary search tree (abbreviated BST)
# building dynamic programming algorithm that delivers O(n^2) performance.
#
# The goal of the optimal BST problem is to build a low-cost BST for a
# given set of nodes, each with its own key and frequency. The frequency
# of the node is defined as how many time the node is being searched.
# The search cost of binary search tree is given by this formula:
#
# cost(1, n) = sum{i = 1 to n}((depth(node_i) + 1) * node_i_freq)
#
# where n is number of nodes in the BST. The characteristic of low-cost
# BSTs is having a faster overall search time than other implementations.
# The reason for their fast search time is that the nodes with high
# frequencies will be placed near the root of the tree while the nodes
# with low frequencies will be placed near the leaves of the tree thus
# reducing search time in the most frequent instances.
import sys
from random import randint






class 				lowerCAmelCase__     :






					def __init__(     self       ,							__SCREAMING_SNAKE_CASE       ,							__SCREAMING_SNAKE_CASE	):


											"""simple docstring"""





											lowercase_			:  List[str]									= key
											lowercase_			:  List[Any]									= freq






					def __str__(     self	):


											"""simple docstring"""





											return F'''Node(key={self.key}, freq={self.freq})'''







def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				Any   ,   __SCREAMING_SNAKE_CASE      :				Any   ,   __SCREAMING_SNAKE_CASE      :				List[str]   ,   __SCREAMING_SNAKE_CASE      :				List[Any]   ,   __SCREAMING_SNAKE_CASE      :				Union[str, Any]   ,   __SCREAMING_SNAKE_CASE      :				List[Any]							):



						"""simple docstring"""





						if i > j or i < 0 or j > len(__SCREAMING_SNAKE_CASE							) - 1:
												return

						lowercase_			:  Optional[int]									= root[i][j]
						if parent == -1:  # root does not have a parent
												print(F'''{key[node]} is the root of the binary search tree.'''							)
						elif is_left:
												print(F'''{key[node]} is the left child of key {parent}.'''							)
						else:
												print(F'''{key[node]} is the right child of key {parent}.'''							)

						print_binary_search_tree(__SCREAMING_SNAKE_CASE   ,   __SCREAMING_SNAKE_CASE   ,   __SCREAMING_SNAKE_CASE   ,   node - 1   ,   key[node]   ,   __SCREAMING_SNAKE_CASE							)
						print_binary_search_tree(__SCREAMING_SNAKE_CASE   ,   __SCREAMING_SNAKE_CASE   ,   node + 1   ,   __SCREAMING_SNAKE_CASE   ,   key[node]   ,   __SCREAMING_SNAKE_CASE							)
def       snake_case_	(       __SCREAMING_SNAKE_CASE      :				int							):



						"""simple docstring"""





						nodes.sort(key=lambda __SCREAMING_SNAKE_CASE							: node.key							)

						lowercase_			:  Optional[int]									= len(__SCREAMING_SNAKE_CASE							)

						lowercase_			:  Any									= [nodes[i].key for i in range(__SCREAMING_SNAKE_CASE							)]
						lowercase_			:  Tuple									= [nodes[i].freq for i in range(__SCREAMING_SNAKE_CASE							)]

						# This 2D array stores the overall tree cost (which's as minimized as possible);
						# for a single key, cost is equal to frequency of the key.
						lowercase_			:  List[Any]									= [[freqs[i] if i == j else 0 for j in range(__SCREAMING_SNAKE_CASE							)] for i in range(__SCREAMING_SNAKE_CASE							)]
						# sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
						# array
						lowercase_			:  Dict									= [[freqs[i] if i == j else 0 for j in range(__SCREAMING_SNAKE_CASE							)] for i in range(__SCREAMING_SNAKE_CASE							)]
						# stores tree roots that will be used later for constructing binary search tree
						lowercase_			:  Dict									= [[i if i == j else 0 for j in range(__SCREAMING_SNAKE_CASE							)] for i in range(__SCREAMING_SNAKE_CASE							)]

						for interval_length in range(2   ,   n + 1							):
												for i in range(n - interval_length + 1							):
																		lowercase_			:  Dict									= i + interval_length - 1

																		lowercase_			:  Tuple									= sys.maxsize  # set the value to "infinity"
																		lowercase_			:  Dict									= total[i][j - 1] + freqs[j]

																		# Apply Knuth's optimization
																		# Loop without optimization: for r in range(i, j + 1):
																		for r in range(root[i][j - 1]   ,   root[i + 1][j] + 1							):  # r is a temporal root
																								lowercase_			:  Optional[int]									= dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
																								lowercase_			:  int									= dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
																								lowercase_			:  Any									= left + total[i][j] + right

																								if dp[i][j] > cost:
																														lowercase_			:  Optional[Any]									= cost
																														lowercase_			:  int									= r

						print('''Binary search tree nodes:'''							)
						for node in nodes:
												print(__SCREAMING_SNAKE_CASE							)

						print(F'''\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}.'''							)
						print_binary_search_tree(__SCREAMING_SNAKE_CASE   ,   __SCREAMING_SNAKE_CASE   ,   0   ,   n - 1   ,   -1   ,   __SCREAMING_SNAKE_CASE							)
def       snake_case_	(       ):



						"""simple docstring"""





						lowercase_			:  List[Any]									= [Node(__SCREAMING_SNAKE_CASE   ,   randint(1   ,   50							)							) for i in range(10   ,   0   ,   -1							)]
						find_optimal_binary_search_tree(__SCREAMING_SNAKE_CASE							)


if __name__ == "__main__":
							main()





'''simple docstring'''







from __future__ import annotations

from queue import Queue






class 				lowerCAmelCase__     :






					def __init__(     self	):


											"""simple docstring"""





											lowercase_			:  dict[int, list[int]]									= {}






					def 			_snake_case					(     self	):


											"""simple docstring"""





											for i in self.vertices:
																	print(__SCREAMING_SNAKE_CASE       ,							''' : '''       ,							''' -> '''.join([str(__SCREAMING_SNAKE_CASE	) for j in self.vertices[i]]	)	)






					def 			_snake_case					(     self       ,							__SCREAMING_SNAKE_CASE       ,							__SCREAMING_SNAKE_CASE	):


											"""simple docstring"""





											if from_vertex in self.vertices:
																	self.vertices[from_vertex].append(__SCREAMING_SNAKE_CASE	)
											else:
																	lowercase_			:  Optional[Any]									= [to_vertex]






					def 			_snake_case					(     self       ,							__SCREAMING_SNAKE_CASE	):


											"""simple docstring"""





											lowercase_			:  List[Any]									= set()

											# create a first in first out queue to store all the vertices for BFS
											lowercase_			:  Queue									= Queue()

											# mark the source node as visited and enqueue it
											visited.add(__SCREAMING_SNAKE_CASE	)
											queue.put(__SCREAMING_SNAKE_CASE	)

											while not queue.empty():
																	lowercase_			:  List[Any]									= queue.get()

																	# loop through all adjacent vertex and enqueue it if not yet visited
																	for adjacent_vertex in self.vertices[vertex]:
																							if adjacent_vertex not in visited:
																													queue.put(__SCREAMING_SNAKE_CASE	)
																													visited.add(__SCREAMING_SNAKE_CASE	)
											return visited


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

							testmod(verbose=True)

							_lowercase				:						Optional[int]												= Graph()
							g.add_edge(0, 1)
							g.add_edge(0, 2)
							g.add_edge(1, 2)
							g.add_edge(2, 0)
							g.add_edge(2, 3)
							g.add_edge(3, 3)

							g.print_graph()
							# 0  :  1 -> 2
							# 1  :  2
							# 2  :  0 -> 3
							# 3  :  3

							assert sorted(g.bfs(2)) == [0, 1, 2, 3]



