optimalBinarySeachTree.rar_binary search_build binary tree_searc

******************************************************************************************** compiler: g++ programing language:c++ ******************************************************************************************** our design: --------read the file Dictionary.txt,get the words and the frequency. --------calculate the probability of every word,using the frequency. --------compute q[i] correspond to the dummy key d[i]. q[i] is inversely proportional to the number of common prefix characters of k[i] and k[i+1],where A is a constant.we choose A=0.001 because we find that when A is smaller, the expected search cost is smaller too.But if A is too small,A^n will save as 0,we can't get the right result. --------using dynamic programming according section 15.5,we get the optimal binary search tree. --------using the result get from Optimal-BSD,we get heights of every node in the OBST.using the heights of every node multiply the probability corresponding to it,we get the cost of searching every phrase in the OBSD.e[1,n] is just the average search cost,get from Optimal-BSD. --------save the information get above in the file named "output.out"******************************************************************************************** some notes: -------The program is encoded by the programing language C++, and its compiler is g++. -------The program have been compiled successfuly. -------Because the words are too many,we just use the previous 10000 words to build an optimal binary search tree,and we get the average search cost is 8.87763. ******************************************************************************************** thanks for your reading and checking! ********************************************************************************************