/Optimal-BST

Reads a file of words, creates an optimal binary search tree (BST) for the words, and searches the trees.

Primary LanguageC

Optimal-BST

Reads in a file of words, creates an optimal binary search tree (BST) for the words, and searches the trees. For each word, the program generates a probability of occurence based on the number of repetitions in the file.

Compilation Instructions

  • navigate to the directory that contains the makefile
  • run make
  • This will create ./q1

Runtime Instructions

The filename is hardcoded as data_A4_Q1.txt
Please insure that the filename for testing is the same.

For Q1:

  • Run ./q1 1 for optimal BST using dynamic programming
  • Run ./q1 2 for optimal BST using a greedy technique

Algorithms

Dynamic Programming

Greedy Technique