最优二叉查找树

2013-02-14 15:16:14   最后更新: 2015-08-06 23:35:31   访问数量:653




如果我们要把一篇文章由英文翻译为法文,那么我们首先需要的是一个字典数据,在这个字典中,每一个英文单词与一个法语单词相对应,但是,在文章中,每个单词出现的概率都是互不相同的,同时也有可能存在需要查找的单词并不在这个字典中的情况,而且每个单词是有字典顺序的,因此我们要在有序遍历的同时优先查找出现概率高的元素,所以我们需要构造一个最优二叉查找树,使得查找的次数尽量降低,也就是说,概率高的单词尽量位于接近根的位置

 

 

这个项目的首要问题是要解决用数学的方法来描述这个项目:

我们预先知道每个“单词”即每个节点的出现概率,所有节点概率之和为1,如下表:

 

表中 pi 为上图中节点 ki 的出现概率,qi 为上图中 di 的出现概率

 

整个树的期望搜索代价为:

E=∑深度i * 概率i

 

对于某个子树,如果他是最优的,那么他的左子树和右子树分别都是最优的,否则就会矛盾,这样,这个问题可以转化为两个子树分别寻找最优的子问题,因此我们可以使用动态规划策略求解

 

对这个问题的进一步分析我们可以知道,当一个树变成一个节点的子树以后,每个节点的深度都加1,因此,新的(包含新的根节点的)子树的期望搜索代价为原子树的期望搜索代价+原子树中所有节点的概率和+根节点概率

因此,我们需要一个矩阵w记录每个子树的所有节点的概率和,以及另一个矩阵e记录每个子树的期望搜索代价,并且我们还需要一个矩阵d来记录得到最优子树时的根节点

 

这样,根据前面的分析,我们可以得到下面的递归式(节点 r 为子树根节点):

w[i, j] = ∑pl + ∑ql = w[i, r-1] + pr + w[r+1, j] = w[i, j-1] + w[i+1, j] - w[i+1, j-1]

e[i, j] = ∑深度l * pl = e[i, r-1] + e[r+1, j] +w[i, j]

当 j == i-1 时,e[i, j] = w[i, j] = qj

 

/* * file: main.c * author: 龙泉居士 * date: 2013-02-14 15:16 */ #include <stdio.h> #include <malloc.h> double p[] = {0.15, 0.1, 0.05, 0.1, 0.2}; double q[] = {0.05, 0.1, 0.05, 0.05, 0.05, 0.1}; void get_w (double *w, int size) { int i, j, k; for (i=0; i<size; ++i) for (j=0; j<size; ++j) w[i*size+j] = 0; i = j = k = 0; while (1) { if (i == j) w[i*size+j] = q[j]; else w[i*size+j] = w[(i+1)*size+j] + w[i*size+j-1] - w[(i+1)*size+j-1]; if (i == j-1) w[i*size+j] += p[i]; ++i; ++j; if (j >= size) { ++k; if (k>=size) break; j=k; i=0; } } } void get_ed (double *w, double *e, int *d, int size) { int i, j, k, r; for (i=0; i<size; ++i) for (j=0; j<size; ++j) e[i*size+j] = d[i*size+j] = 0; i = j = k = 0; while (1) { if (i == j) e[i*size+j] = q[j]; else for (r=i; r<j; ++r) { double tmp = e[i*size+r] + e[(r+1)*size+j] + w[i*size+j]; if (tmp < e[i*size+j] || e[i*size+j] == 0) { e[i*size+j] = tmp; d[i*size+j] = r; } } ++i; ++j; if (j >= size) { ++k; if (k>=size) break; j=k; i=0; } } } void optimal_Btree (int size) { double *w = (double *)malloc(sizeof(double)*size*size); double *e = (double *)malloc(sizeof(double)*size*size); int *d = (int *)malloc(sizeof(int)*size*size); get_w(w, size); get_ed(w, e, d, size); int i, j; printf ("w: \n"); for (i=0; i<size; ++i) { for (j=0; j<size; ++j) printf ("%.2lf ", w[i*size+j]); printf ("\n"); } printf ("e: \n"); for (i=0; i<size; ++i) { for (j=0; j<size; ++j) printf ("%.2lf ", e[i*size+j]); printf ("\n"); } printf ("d: \n"); for (i=0; i<size; ++i) { for (j=0; j<size; ++j) printf ("%d ", d[i*size+j]); printf ("\n"); } free(w); free(e); free(d); } int main () { optimal_Btree (6); return 0; }

 

 






读书笔记      技术帖      算法      算法导论      龙潭书斋      排序            tree      二叉树      查找      二叉查找树      二叉排序树      优化     


京ICP备15018585号