精华内容
下载资源
问答
  • 最优二叉搜索树

    2015-06-03 14:34:18
    这是算法中的最优二叉搜索树。 二叉搜索树节省了搜索时间,提高了效率
  • 算法思想:动态规划实际问题:最优二叉搜索树编写语言:Java问题描述二叉搜索树的定义:满足以下任意两个条件的一个,就可称这棵树为二叉搜索树:它是一棵空树该树是一颗二叉树,非空,且满足下列两个条件:若它的左...

    算法思想:动态规划

    实际问题:最优二叉搜索树

    编写语言:Java

    问题描述

    二叉搜索树的定义:

    满足以下任意两个条件的一个,就可称这棵树为二叉搜索树:

    它是一棵空树

    该树是一颗二叉树,非空,且满足下列两个条件:

    若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值

    若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值

    即当该二叉树非空时,使用中序遍历可以得到一个递增的有序序列

    值得注意的是:

    二叉搜索树的左右子树也是二叉搜索树,我们因此可以使用递归手段来构造二叉搜索树

    一个有序序列的二叉搜索树不只一棵,这就为我们寻找最优二叉搜索树提供了可能

    最优二叉搜索树指的是在一个序列的所有二叉搜索树中花费代价最小的那棵。

    递归结构

    用C[i , j]表示从 i 到 j 的最优二叉查找树的代价,假设有n个顶点,那么我们的目标是要求C[1 , n]从 i 到 j 的一个最优二叉查找树是怎么得到的?它是从 i 到 j 之间的顶点中选出一个顶点来做root,假设选出的这个做root的顶点是 k (i <= k <= j), 那么显然有:

    C[i , j] = min(C[i, k - 1] + C[k + 1, j]) + Sum(pi, pj),其中:1 <= i <= j <= n,i <= k <= j,pi表示遍历第i个结点的代价,Sum(pi, pj)表示求第i个结点到第j个结点的代价总和

    上述求和公式最后为什么还要加一个求和结果呢?因为可以理解为公式前半部分只是找出最短路径,最后求和才是加上权重(网上有更详细更严谨的推导过程,可自行百度)

    Java代码

    public class OptBST

    {

    public static void main(String[] args)

    {

    double[] p = new double[]{0.1, 0.15, 0.2, 0.35, 0.2};

    Result r = getOptBST(p);

    for(int i = 0; i < r.result.length; i++)

    {

    for(int j = 0; j < r.result.length; j++)

    System.out.print(r.root[i][j] + " ");

    System.out.println();

    }

    }

    /**

    * 构造最优二叉搜索树的方法

    * param p: 中序序列的点的查找概率数组,返回最优的二叉查找树的代价

    */

    public static Result getOptBST(double[] p)

    {

    int n = p.length; //序列长度

    Result r = new Result(n);

    for(int i = 0; i < n; i++)

    {

    //从i到i的最小代价(找到的概率)就是找到i的代价(概率)

    r.result[i][i] = p[i];

    r.root[i][i] = i; //只有一个结点时,最优二叉搜索树就是它本身

    }

    for(int m = 1; m < n; m++) //m代表二叉树的长度(所有结点的个数)

    {

    for(int i = 0; i < n - m; i++) //i为二叉树左起点

    {

    int j = i + m; //j为二叉树的右终点

    double min = 1000000; //该变量存储最小代价

    int tr = 0; //tr: temp root,临时变量,表示根节点

    //求取最小值并记录根所在位置

    for(int k = i; k <= j; k++)

    {

    //用r1表示result[i,k-1],r2表示result[k+1,j]

    double r1 = 0, r2 = 0;

    if(i < k)

    r1 = r.result[i][k - 1];

    if(k < j)

    r2 = r.result[k + 1][j];

    if(min > r1 + r2)

    {

    min = r1 + r2;

    tr = k;

    }

    }

    r.root[i][j] = tr;

    double sum = 0;

    for(int s = i; s <= j; s++)

    sum += p[s];

    r.result[i][j] = min + sum; //递推公式体现在这里

    }

    }

    return r;

    }

    }

    class Result //存储结果的类

    {

    public double[][] result; //存储代价

    public int[][] root; //存储构造路径

    public Result(int n)

    {

    result = new double[n][n];

    root = new int[n][n];

    }

    }

    运行结果

    62c5b5d115760084992861216576ded8.png

    展开全文
  • 最优二叉搜索树 最优二叉搜索树的定义 输入:有序数的集合{x1,x2…xn} 输出:最优二叉搜索树 搜索树的代价: 设树中xi节点的深度为ci,叶节点(xi,xi+1)的深度为di,数字落在节点的概率用pi表示,落在叶子节点的...

    最优二叉搜索树

    最优二叉搜索树的定义

    输入:有序数的集合{x1,x2…xn}

    输出:最优二叉搜索树

    搜索树的代价:

    1. 设树中xi节点的深度为ci,叶节点(xi,xi+1)的深度为di,数字落在节点的概率用pi表示,落在叶子节点的间隙的概率用qi表示。
      在这里插入图片描述
      上图中椭圆为节点,方框为间隙。
    2. 代价为
      在这里插入图片描述
      优化目标:最小代价函数

    优化子结构

    在这里插入图片描述

    重叠子问题

    在这里插入图片描述

    展开全文
  • 0020 算法笔记动态规划最优二叉搜索树问题 1问题描速 设 S={x 1, x2, ,xn} 是一个有序集合且 x1, x2, ,xn 表示有序集 合的二叉搜索 利用二叉 的 点存 有序集中的元素而且具有性 存 于每个 点中的元素 x 大于其左子 ...
  • 算法设计与分析(fft,平面上最接近两点对,最优二叉搜索树构造)这三个实验的代码和报告,报告是写在一起的,
  • 动态规划——最优二叉搜索树 问题: 给定数据集合S与存取概率分布P,求一颗平均查找次数(平均查找长度)最小的二叉搜索树,即最优二叉搜索树。 分析: 对于一个给定的升序序列,如何构造其二叉搜索树呢?只要不断...

    动态规划——最优二叉搜索树

    问题:

    给定数据集合S与存取概率分布P,求一颗平均查找次数(平均查找长度)最小的二叉搜索树,即最优二叉搜索树。

    分析:

    对于一个给定的升序序列,如何构造其二叉搜索树呢?只要不断“断开”即可,换句话说,还是一个加括号问题。

    m[i][j]为i到j构成的一棵子树的平均查找长度

    w[i][j]为i倒j的所有节点的概率总和

    假设从k处断开,那么假设其被分为左子树、右子树和根节点。如果将左右子树放在其父树中,则其所有节点的深度都会增加1,换算过来,在树中的子树平均查找长度要在子树单独存在的基础上加w。再加上根节点的平均查找长度为根节点的概率,故递推公式如下:

    m[i][j] =min_i<=k<=j{m[i][k-1]+m[k+1][j]+w[i][j]}

    代码和时间复杂度自然和加括号问题一样。

    展开全文
  • 最优二叉搜索树是建立在搜索树的基础上的一种最优解,一开始我也很纠结为什么会有查找不成功和查找成功的概念,后来才开始明白后来懂了如何去做,如果这点还没有明白那很难去懂什么是最优二叉搜索树,下面按照题目...

    最优二叉搜索树是建立在搜索树的基础上的一种最优解,一开始我也很纠结为什么会有查找不成功和查找成功的概念,后来才开始明白后来懂了如何去做,如果这点还没有明白那很难去懂什么是最优二叉搜索树,下面按照题目讲解主要内容:
    我们先来声明一下如何求二叉搜索树的权重
    在这里插入图片描述
    形状1的平均查找次数
    在这里插入图片描述
    形状2的平均查找次数
    在这里插入图片描述
    计算的方程
    在这里插入图片描述
    知道了如何计算平均查找次数,我们下面求解一下如何求解最优二叉搜索树问题
    在这里插入图片描述
    将四个合起来
    在这里插入图片描述
    拼成一个个基本的子树暂时命名为a1,a2,a3
    在这里插入图片描述
    a1和a2合并有两种情况
    在这里插入图片描述
    计算得出第一种权重较小,故选择第一种形状为T[1][2]在这里插入图片描述
    同理计算出T[2][3]应该为第一种模型
    在这里插入图片描述
    这是最终有a1和a2以及a2和a3形成的最小二叉搜索树的子树
    在这里插入图片描述
    当我们求解T[1][3]时,实际上我们求解的是由T[1][2]与a3构成的,以及a1与T[2][3]构成的其中找到最优解
    在这里插入图片描述
    得出最优解由形状一取得

    这是动态规划的动态矩阵以及状态转移方程
    在这里插入图片描述

    展开全文
  • 关于最优二叉搜索树的动态规划算法描述
  • 写完矩阵链相乘问题接着写最优二叉搜索树问题,感觉在动态规划方程的结构上二者并没有太多的本质区别,但是最优二叉搜索树问题难在方程的推导过程,并且还有辅助数组。 输入 第一行为一个数n,表示有n个关键字 第二...
  • 利用最优二叉搜索树来实现树的搜索代价最小。树上的每一个节点都有一个被搜索到的概率值pi,搜索一个节点的花费为pi∗(depth(ki)+1),如何构造一个二叉查找树使搜索树上的 所有节点的花费最小即为实现最优二叉查找...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 494
精华内容 197
关键字:

最优二叉搜索树