Question

Please answer in C programming language.

Please remember that the words we store from the text file will have multiple instances and that we have to create only one node for it. i.e, if "hi" appears 10 times, we still only create one node for it. In the expected output picture. Make sure to print the minimum average number of comparisons of the subtree rooted at V. Question 1: BST Creation (70\%) File data A4 Q1.txt contains 2045 word instances. Develop two programs to read the file, create optimal binary search trees (BSTs) for the words, and search the trees. In a tree, create a node for a word, even the word may appear multiple times in the file, i.e. the word may have multiple instances. For example, undergraduate appears nine times in the file, but there should be only one node for it. It is assumed thaf the probability to search a word is proportional to the word's frequency in the text. 1.1 BST by dynamic programming (40\%) Develop a program to create an optimal BST by using the technique of dynamic programming (described in section 8.3 in the textbook). You are required to calculate the "average number table" and "root table". After creating the tree, the program prompts the user to enter a word (key) and searches the tree for the word. Whenever the program compares user input K with word W at node V, it displays word W, the minimum average number of comparisons of the subtree rooted at V (three digits after the decimal point), and the subtree to go (left or right). If the program fails to find the K in the tree, it displays "not found" after comparisons. Please see the guide for suggested output format. For Q1.1, your program output can be something like: Enter a key: undergraduate Compared with of (6.147), go right subtree. Compared with the (1.972), go right subtree. Compared with university (0.412), go left subtree Compared with to (0.156), go right subtree. Compared with undergraduate (0.053), found.

Answer 1

To implement an optimal binary search tree (BST) in C using dynamic programming, you need to develop a program that reads a text file, creates the optimal BST, and performs searches. The program should ensure that each word in the file is represented by a single node in the tree, regardless of its frequency. After constructing the tree, the program prompts the user to input a word and searches for it, displaying the comparisons made, the minimum average number of comparisons for the subtree rooted at the current node, and the direction to traverse in the subtree. If the word is not found, it indicates "not found" after the comparisons.

Step-by-step explanation:

To achieve this, your C program should follow the dynamic programming technique outlined in section 8.3 of the textbook. First, calculate the "average number table" and "root table" for constructing the optimal BST. When searching for a word, the program compares the user input with the words at each node, displaying the relevant information about comparisons and subtree traversal.

The minimum average number of comparisons for a subtree rooted at node V is a key metric. This value is calculated during the tree construction and helps optimize the search process by guiding the program to the most probable direction in the subtree.

In the output example, the program prompts the user to input a word and iteratively compares it with words in the tree. The displayed information includes the word being compared, the minimum average number of comparisons for the subtree rooted at the current node, and the direction (left or right) to traverse further.

This approach ensures efficient searching based on the probability of word occurrences in the text, contributing to the creation of an optimal binary search tree.