usrbinenv python3 this python program implements an optimal binary search tree abbreviated bst building dynamic programming algorithm that delivers on2 performance the goal of the optimal bst problem is to build a lowcost 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 cost1 n sumi 1 to ndepthnodei 1 nodeifreq where n is number of nodes in the bst the characteristic of lowcost 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 binary search tree node def initself key freq self key key self freq freq def strself return fnodekeyself key freqself freq def printbinarysearchtreeroot key i j parent isleft if i j or i 0 or j lenroot 1 return node rootij if parent 1 root does not have a parent printfkeynode is the root of the binary search tree elif isleft printfkeynode is the left child of key parent else printfkeynode is the right child of key parent printbinarysearchtreeroot key i node 1 keynode true printbinarysearchtreeroot key node 1 j keynode false def findoptimalbinarysearchtreenodes tree nodes must be sorted first the code below sorts the keys in increasing order and rearrange its frequencies accordingly nodes sortkeylambda node node key n lennodes keys nodesi key for i in rangen freqs nodesi freq for i in rangen 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 dp freqsi if i j else 0 for j in rangen for i in rangen sumij stores the sum of key frequencies between i and j inclusive in nodes array total freqsi if i j else 0 for j in rangen for i in rangen stores tree roots that will be used later for constructing binary search tree root i if i j else 0 for j in rangen for i in rangen for intervallength in range2 n 1 for i in rangen intervallength 1 j i intervallength 1 dpij sys maxsize set the value to infinity totalij totalij 1 freqsj apply knuth s optimization loop without optimization for r in rangei j 1 for r in rangerootij 1 rooti 1j 1 r is a temporal root left dpir 1 if r i else 0 optimal cost for left subtree right dpr 1j if r j else 0 optimal cost for right subtree cost left totalij right if dpij cost dpij cost rootij r printbinary search tree nodes for node in nodes printnode printfnthe cost of optimal bst for given tree nodes is dp0n 1 printbinarysearchtreeroot keys 0 n 1 1 false def main a sample binary search tree nodes nodei randint1 50 for i in range10 0 1 findoptimalbinarysearchtreenodes if name main main usr bin env python3 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 binary search tree node str node 1 2 node key 1 freq 2 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 root does not have a parent 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 blankline 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 tree nodes must be sorted first the code below sorts the keys in increasing order and rearrange its frequencies accordingly 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 sum i j stores the sum of key frequencies between i and j inclusive in nodes array stores tree roots that will be used later for constructing binary search tree set the value to infinity apply knuth s optimization loop without optimization for r in range i j 1 r is a temporal root optimal cost for left subtree optimal cost for right subtree a sample binary search tree
import sys
from random import randint


class Node:
    

    def __init__(self, key, freq):
        self.key = key
        self.freq = freq

    def __str__(self):
        
        return f"Node(key={self.key}, freq={self.freq})"


def print_binary_search_tree(root, key, i, j, parent, is_left):
    
    if i > j or i < 0 or j > len(root) - 1:
        return

    node = root[i][j]
    if parent == -1:  
        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(root, key, i, node - 1, key[node], True)
    print_binary_search_tree(root, key, node + 1, j, key[node], False)


def find_optimal_binary_search_tree(nodes):
    
    
    
    nodes.sort(key=lambda node: node.key)

    n = len(nodes)

    keys = [nodes[i].key for i in range(n)]
    freqs = [nodes[i].freq for i in range(n)]

    
    
    dp = [[freqs[i] if i == j else 0 for j in range(n)] for i in range(n)]
    
    
    total = [[freqs[i] if i == j else 0 for j in range(n)] for i in range(n)]
    
    root = [[i if i == j else 0 for j in range(n)] for i in range(n)]

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

            dp[i][j] = sys.maxsize  
            total[i][j] = total[i][j - 1] + freqs[j]

            
            
            for r in range(root[i][j - 1], root[i + 1][j] + 1):  
                left = dp[i][r - 1] if r != i else 0  
                right = dp[r + 1][j] if r != j else 0  
                cost = left + total[i][j] + right

                if dp[i][j] > cost:
                    dp[i][j] = cost
                    root[i][j] = r

    print("Binary search tree nodes:")
    for node in nodes:
        print(node)

    print(f"\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}.")
    print_binary_search_tree(root, keys, 0, n - 1, -1, False)


def main():
    
    nodes = [Node(i, randint(1, 50)) for i in range(10, 0, -1)]
    find_optimal_binary_search_tree(nodes)


if __name__ == "__main__":
    main()