dynamic_programming.optimal_binary_search_tree

Classes

Node

Binary Search Tree Node

Functions

find_optimal_binary_search_tree(nodes)

This function calculates and prints the optimal binary search tree.

main()

print_binary_search_tree(root, key, i, j, parent, is_left)

Recursive function to print a BST from a root table.

Module Contents

class dynamic_programming.optimal_binary_search_tree.Node(key, freq)

Binary Search Tree Node

__str__()
>>> str(Node(1, 2))
'Node(key=1, freq=2)'
freq
key
dynamic_programming.optimal_binary_search_tree.find_optimal_binary_search_tree(nodes)

This function calculates and prints the optimal binary search tree. The dynamic programming algorithm below runs in O(n^2) time. Implemented from CLRS (Introduction to Algorithms) book. https://en.wikipedia.org/wiki/Introduction_to_Algorithms

>>> find_optimal_binary_search_tree([Node(12, 8), Node(10, 34), Node(20, 50),                                          Node(42, 3), Node(25, 40), Node(37, 30)])
Binary search tree nodes:
Node(key=10, freq=34)
Node(key=12, freq=8)
Node(key=20, freq=50)
Node(key=25, freq=40)
Node(key=37, freq=30)
Node(key=42, freq=3)

The cost of optimal BST for given tree nodes is 324.
20 is the root of the binary search tree.
10 is the left child of key 20.
12 is the right child of key 10.
25 is the right child of key 20.
37 is the right child of key 25.
42 is the right child of key 37.
dynamic_programming.optimal_binary_search_tree.main()
dynamic_programming.optimal_binary_search_tree.print_binary_search_tree(root, key, i, j, parent, is_left)

Recursive function to print a BST from a root table.

>>> key = [3, 8, 9, 10, 17, 21]
>>> root = [[0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 3], [0, 0, 2, 3, 3, 3],                 [0, 0, 0, 3, 3, 3], [0, 0, 0, 0, 4, 5], [0, 0, 0, 0, 0, 5]]
>>> print_binary_search_tree(root, key, 0, 5, -1, False)
8 is the root of the binary search tree.
3 is the left child of key 8.
10 is the right child of key 8.
9 is the left child of key 10.
21 is the right child of key 10.
17 is the left child of key 21.