即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

最优二叉查找树详细解析(算法导论学习与进阶学习与进阶笔记)

编程语言 say_c_box 82℃ 0评论
本文目录
[隐藏]

代码均未经过严格测试,仅供参考

1.最优二叉查找树

1.1.动态规划原理

动态规划与分治法相似,都是通过组合子问题的解来求解原问题。

动态规划通常是用来求解最优化问题(optimization problem).这类问题可以有很多个可行解,每个解都有一个值,我们希望寻找最优值(最大值或者最小值)的解。我们称这样的解为问题的一个最优解(oneoptimization solution)而不是最优解(theoptimization solution),因为可能有多个解都达到最优值。

通常按照如下四个步骤来设计一个动态规划算法:

  1. 刻画一个最优解的结构特征;
  2. 递归地定义最优解的值;
  3. 计算最优解的值,通常采用自底向上的方法;
  4. 利用计算出的线性构造一个最优解。

1.2.基本概念

  • 平均查找长度ASL——查找方法时效的度量:为确定记录在查找表中的位置,需将关键字和给定值比较次数的期望值。

  • 查找成功时的ASL计算方法:ASL=ni=0PiCi

    n:记录的个数


    pi:查找第i个记录的概率


    ( 不特别声明时认为等概率 pi =1/n )


    ci:找到第i个记录所需的比较次数


    约定:无特殊说明,一般默认关键字的类型为整型

  • ASLs:(查找成功的的平均查找长度)

  • ASLf:(查找失败的平均查找长度)

1.3.关于静态最优查找树

定义:查找性能最佳的判定树。

性质:带权内路径长度之和PH为最小值。

PH=ni=1(WiHi) 与ASLs成正比


其中n:二叉树上结点的个数(有序表长度)


Hi:第i个结点在二叉树上的层次数


Wi=c*pi:c为某个常量;


pi:第i个结点的查找概率

1.4.问题描述

给定n个不同关键字的已经排序的序列k1,k2,k3...kn我们希望用这些关键字构造一颗二叉搜索树,对每个关键字都有一个概率p表示其搜索频率。有些要搜索的值可能不在K中,因此我们还有n+1个”伪关键字”d0,d1,d2...dn其中d0表示所有小于k1的值,dn表示所有大于kn的值,对于i=1,2,3,4…n1,dikiki+1。对每个伪关键字di也都一个概率qi表示对应的搜索频率。每个关键字ki是一个内部节点,每一个关键字di表示一个叶节点。有ni=1pi+ni1qi=1

1.4.1.最优查找体现的原则:

1)最先访问的结点应是访问概率最大的结点;


2)每次访问应使结点两边尚未访问的结点的被访概率之和尽可能相等。

1.5.关于次优查找树

PH值近似为最小


比静态最优查找树易于构造,时间开销少

首先按照权值升序排列,每一次选择一个,右边所有节点权值相加和减去左边节点权值相加和 最小的节点作为根节点,然后以左边节点作为左子树,右边节点作为右子树,分别构造其次优查找树。

1.6.复杂度分析以及可能的优化

很显然由于需要枚举区间长度,区间端点以及根节点。所以算法复杂度为O(n3)

递推式的形式为dp[i][j]=min(dp[i][r1]+dp[r+1][j]+sum[i][j])

可以考虑用四边形不等式优化。

2.算法实现

次优查找树的实现非常简单,一个数组存储每个节点的权值。计算前缀和,找到差值最大的点作为根节点后。递归构造左子树和右子树的次优查找树。

我们来尝试使用动态规划算法构造最优查找树

double p[MAXN];//用来记录每一个节点的查找概率
double q[MAXN];//用来记录伪关键字的搜索概率
double dp[MAXN][MAXN];//dp[i][j]表示从节点i到节点j构成的最优查找树的PH值的最小值
int root[MAXN][MAXN];//root[i][j]表示从节点i到节点j构成的最优查找树的根节点
double sum[MAXN][MAXN];//sum[i][j]表示区间i到j的的区间概率和

//伪代码如下
for(int 子树大小 len=1;len<=n;len++){
    for(int 子树起点 i=1;i
        int 子树的终点则为j=i+len-1
        然后试图用每个节点作为根节点,找到使得总代价最小的一个
        总代价为左右子树的代价相加+区间的概率和。因为每一个节点都往下移了一层
        for(int r=i;r<=j;r++){
            dp[i][j]=min(dp[i][r-1]+dp[r+1][j]+sum[i][j]);
            并更新对应的根节点的值
        }
    }
}

记录了每个区间的PH值和根节点之后,再递归还原出整课最优查找树即可。

代码如下:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define _ sync_with_stdio(false)
typedef long long ll;
const int MAXN=1000+10;
const double INF=1e9+7;


int n;//节点总个数
double p[MAXN];//用来记录每一个节点的查找概率
double q[MAXN];//用来记录伪关键字的搜索概率
double dp[MAXN][MAXN];//dp[i][j]表示从节点i到节点j构成的最优查找树的PH值的最小值
int root[MAXN][MAXN];//root[i][j]表示从节点i到节点j构成的最优查找树的根节点
double sum[MAXN][MAXN];//sum[i][j]表示区间i到j的的区间概率和

void solve(){
    for(int len=1;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;
            dp[i][j]=INF;
            for(int r=i;r<=j;r++){
                double temp;
                temp=dp[i][r-1]+dp[r+1][j]+sum[i][j];
                if(tempvoid init(){
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(j==i-1){
                sum[i][j]=q[i-1];
                dp[i][j]=q[i-1];
            }
            else if(j>=i){
                sum[i][j]=sum[i][j-1]+p[j]+q[j];
                if(i==j){
                    //dp[i][j]=p[i]+q[i-1]+q[i];
                    root[i][j]=i;
                }
                dp[i][j]=0;
            }else{
                sum[i][j]=0;
                dp[i][j]=0;
            }
        }
    }
    sum[n+1][n]=dp[n+1][n]=q[n];

}

void dfs(int l,int r){
    if(l>r){
        cout<<"{}";
        return;
    }
    cout<int Root=root[l][r];
    cout<<"{";
    dfs(l,Root-1);
    cout<<",";
    dfs(Root+1,r);
    cout<<"}";
    return;
}

int main(){
    freopen("in.txt", "r", stdin);
    cout<<"请输入待查找关键字的数量:"<cin>>n;
    cout<<"请输入"<"个待查找关键字的搜索频率:"<for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    cout<<"请输入"<1<<"个伪关键字的搜索频率:"<for(int i=0;i<=n;i++){
        cin>>q[i];
    }
    init();
    solve();
    cout<<"最小PH值为:"<1][n]<"最优查找树构造如下:"<1,n);
    return 0;
}

转载请注明:CodingBlog » 最优二叉查找树详细解析(算法导论学习与进阶学习与进阶笔记)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情