通用算法-最优二叉树

一、环境

• 系统：win10
• 语言：python3.7
• 算法基础：动态规划

二、原理说明

2.1 算法目的

根据不同数据被索引的次数，对数据构建二叉树。比如在输入法中，有些常用词汇就应该放在树的前面，可以更快的被索引到。数据存放的位置根据每个数据被索引的概率放置，要求平均查找次数最小。例如：

对于以下数据：

arr = [4,2,5,1,7,3]

其被对应被索引的概率为：

p = [0.1, 0.05, 0.2, 0.25, 0.35, 0.05]

构建如下二叉图：

其平均搜索次数为：

$$p = 0.1 + 0.05*2 + 0.2 *3+0.25*4+0.35*5+0.05*6 = 3.85次$$

如果构建如下二叉图：

其平均搜索次数为：

$$p = 0.35 + (0.2+0.25)*2 +(0.1+0.05+0.05)*3 = 1.85次$$

所以，合理的摆放数据位置，可以大大的提高搜索效率

2.2 公式表达

符号说明：

• $k$：第$k$个位置的数据索引
• $p_k$：表示第$k$个数据被索引到的概率
• $T(i,j)$：是由$\{r_i,…,r_j\}$构成的二叉树，其中$i<j$。
• $C(i,j)$：是由$\{r_i,…,r_j\}$构成的二叉树的平均搜索次数。

假设在$\{r_i,…,r_j\}$中，选择$r_k$作为二叉查找树的根节点：则其平均搜索次数可以表示为:

$$\begin{align} C(i,j) = &min\{ p_k + \\ & \sum_{s=i}^{k-1}p_s \times(r_s在T(i,k-1)中的层数 + 1) \\ & \sum_{s=k+1}^{j}p_s(r_s在T(k+1,n)中的层数 + 1)\} \end{align}$$

对上式进行化简：

$$\begin{align} C(i,j) = &min\{ \sum_{s=i}^{k-1}p_s \times（r_s在T(i,k-1)中的层数） +\\ &\sum_{s=k+1}^j p_s \times(r_s在T(k+1,j)中的层数) + \sum_{s=i}^j p_s \}\\ =&min\{C(i,k-1) + C(k+1,j) + \sum_{s=i}^j p_s \} \end{align}$$

通过以上推导，已经得到了函数递推式（动态规划算法必备），接下来需要初始化（使用别人的图）：

初始化之后，对每个位置的书进行推导：

$$\begin{equation} C(1,2) = \left\{ \begin{array}{} min\{k=1:C(1,0) + C(2,2) + \sum_{s=1}^2 p_s = 0+0.2+0.3 = 0.5\} \\ min\{k=2:C(1,1) + C(3,2) + \sum_{s=1}^2 p_s = 0+0.2+0.3 = 0.4\} \end{array} \right\} = 0.4 \end{equation}$$

以此为例子，一直推导计算到$C(1,4)$最优计算次数。结果为（别人的图）：

观察这个表，可知可知左边的表的第一行的第四列就是我们要求的最优平均比较次数，而右边的表我们可以知道在c（i ,j）得到最优解，即平均查找次数最小的根节点，比如一共四个节点，则我们从右边的R(1,4)的值即3是这四个节点构成的树的根节点。则树的左子树变为c(1,2),他的根节点是r(1,2)=2，然后2又有左节点1，而4则是3的右节点。则树的样子便出来了。

2.3 代码实现

（当然也是别人的）

#include<bits/stdc++.h>
using namespace std;
double BST(int n,double p[],double c[][100],int r[][100])
{
    for(int i=1;i<=n;i++){//按式1和式2初始化
        c[i][i-1]=0;
        c[i][i]=p[i];
        r[i][i]=i;
    }
    c[n+1][n]=0;
    for(int d=1;d<n;d++){//安对角线计算，此时是n-1个对角线
        for(int i=1;i<=n-d;i++){//行的取值范围
            int j=i+d;//求出在对角线上的i对应的j
            double minnum=99999.0;//出是一个较大的值
            int mink=i;
            double sum=0;
            for(int k=i;k<=j;k++)
            {
                sum=sum+p[k];
                if(c[i][k-1]+c[k+1][j]<minnum){//不断比较，获取最小的值
                    minnum=c[i][k-1]+c[k+1][j];
                    mink=k;
                }
            }
            c[i][j]=minnum+sum;//得到了最小值
            r[i][j]=mink;//记录取得最小值时的根节点
        }

    }
    return c[1][n];
}
int main()
{
    cout << "请输入树的节点的个数" << endl;
    int n;
    cin >> n;
    cout << "请输入每个节点的被查找概率" << endl;
    double p[n];
    memset(p,0,sizeof(p));
    for(int i=1;i<=n;i++)
    {
        cin >> p[i];
    }
    double c[n+2][100];
    int r[n+2][100];
    memset(r,0,sizeof(r));
    memset(c,0,sizeof(c));
     double s=BST(n,p,c,r);
     cout << "最小平均比较次数为" << s<<endl;
     cout << "平均最小概率矩阵如下:" << endl;
     for(int i=1;i<=n+1;i++){
        for(int j=0;j<=n;j++){
            cout << c[i][j] << "   ";
        }
        cout << endl;
     }

     cout << "最优二叉查找树对应的根节点 " << endl;
for(int i=1;i<=n+1;i++){
        for(int j=0;j<=n;j++){
            cout << r[i][j] << "   ";
        }
        cout << endl;
     }

    return 0;
}

参考文献

¹. 最优二叉查找树_动态规划 ↩