OBST（Optimal Binary Tree最优二叉搜索树）

二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

一、什么是最优二叉查找树

最优二叉查找树：

给定n个互异的关键字组成的序列K=<k1,k2,...,kn>，且关键字有序（k1<k2<...<kn），我们想从这些关键字中构造一棵二叉查找树。对每个关键字ki，一次搜索搜索到的概率为pi。可能有一些搜索的值不在K内，因此还有n+1个“虚拟键”d0,d1,...,dn，他们代表不在K内的值。具体：d0代表所有小于k1的值，dn代表所有大于kn的值。而对于i = 1,2,...,n-1,虚拟键di代表所有位于ki和ki+1之间的值。对于每个虚拟键，一次搜索对应于di的概率为qi。要使得查找一个节点的期望代价（代价可以定义为：比如从根节点到目标节点的路径上节点数目）最小，就需要建立一棵最优二叉查找树。

图一显示了给定上面的概率分布pi、qi，生成的两个二叉查找树的例子。图二就是在这种情况下一棵最优二叉查找树。

概率分布：

已知每个关键字以及虚拟键被搜索到的概率，可以计算出一个给定二叉查找树内一次搜索的期望代价。假设一次搜索的实际代价为检查的节点的个数，即所发现的节点的深度加1.计算一次搜索的期望代价等式为：

建立一棵二叉查找树，如果是的上式最小，那么这棵二叉查找树就是最优二叉查找树。

而且有下式成立：

二、最优二叉查找树的最优子结构

最优子结构：

如果一棵最优二叉查找树T有一棵包含关键字ki,..,kj的子树T‘，那么这可子树T‘对于关键字Ki,...,kj和虚拟键di-1,...dj的子问题也必定是最优的。可以应用剪贴法证明。

根据最优子结构，寻找最优解：

给定关键字ki,...,kj，假设kr(i<=r<=j)是包含这些键的一棵最优子树的根。其左子树包含关键字ki,...,kr-1和虚拟键di-1,...,dr-1，右子树包含关键字kr+1,...,kj和虚拟键dr,...dj。我们检查所有的候选根kr,就保证可以找到一棵最优二叉查找树。

递归解：

定义e[i,j]为包含关键字ki,...,kj的最优二叉查找树的期望代价，最终要计算的是e[1,n]。

当j = i - 1时，此时子树中只有虚拟键，期望搜索代价为e[i,i - 1] = qi-1.

当j >= i时，需要从ki,...,kj中选择一个根kr，然后分别构造其左子树和右子树。下面需要计算以kr为根的树的期望搜索代价。然后选择导致最小期望搜索代价的kr做根。

现在需要考虑的是，当一棵树成为一个节点的子树时，期望搜索代价怎么变化？子树中每个节点深度都增加1.期望搜索代价增加量为子树中所有概率的总和。

对一棵关键字ki,...,kj的子树，定义其概率总和为：

因此，以kr为根的子树的期望搜索代价为：

而

因此e[i,j]可以进一步写为：

这样推导出最终的递归公式为：

#include <iostream>
#include <cstdio>
#define INF 0xFFFFF
using namespace std;
double p[21], q[21];
int root[21][21];//记录最优子树的根节点位置
double w[21][21];//w[i][j]:最优子树概率总和
double e[21][21];//e[i][j]: （最优）子树期望代价

void optimalBST(int n)
{
    for(int i = 1; i<=n+1; i++)
    {
        w[i][i-1] = q[i-1];
        e[i][i-1] = q[i-1];
    }

    for(int len = 1; len<=n; len++)
    {
        for(int i = 1; i<=n-len+1; i++)
        {
            int j  = i+len-1;
            e[i][j] = INF;
            w[i][j] = w[i][j-1] + p[j] + q[j];
            for(int r = i; r<=j; r++)
            {
                double t = e[i][r-1] + e[r+1][j] + w[i][j];
                if(t<e[i][j])
                {
                    e[i][j]=t;
                    root[i][j] = r;
                }
            }
        }
    }
}

int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        getchar();
        for(int i = 1; i<=n; i++)
            scanf("%lf", &p[i]);
        getchar();
        for(int i =0; i<=n; i++)
            scanf("%lf", &q[i]);
        getchar();
        optimalBST(n);
        printf("%.3lf\n", e[1][n]);
    }
}

View Code

OBST（Optimal Binary Tree最优二叉搜索树）

原文：http://www.cnblogs.com/zpfbuaa/p/4953898.html