首页 > 其他分享 >最优二叉搜索树

最优二叉搜索树

时间:2022-11-15 23:34:35浏览次数:44  
标签:检索 结点 二叉 关键字 搜索 二叉树 最优

二叉搜索树

是一棵空树或者满足以下的性质:

每个结点作为搜索对象,它的关键字是互不相同的。
对于树上的所有结点,如果它有左子树,那么左子树上所有结点的关键字都小于该结点的关键字。
对于树上的所有结点,如果它有右子树,那么右子树上所有结点的关键字都大于该结点的关键字。

搜索过程:

从根结点开始,如果根为空,则搜索不成功;否则使用待搜索值与根结点比较,如果待搜索值等于根结点关键字,则搜索成功返回,如果小于根结点,则向左子树搜索;如果大于根结点,则向右子树搜索。
对于一个给定的关键字集合,可能有若干不同的二分检索树
如对保留字的子集
Name: 1 2 3 4 5
for if loop repeat while
的两棵二分检索树为

 

 

 

考虑a图和b图中最坏比较次数和平均比较次数
构造不同的二叉搜索树就有不同的性能特征。
二叉搜索树a在最坏情况下找一个标识符需要4次比较,而b表示的二分检索树最坏情况下只需3次比较。
假设只作成功的检索并且检索每个标识符的概率相同,则两棵二分检索树在平均情况下各需要12/5和11/5次比较。

最优二叉搜索树

存在的两个问题
1 在实际中也会遇到不成功检索的情况。
2 在实际中,不同标识符会有不同的检索概率。
对给定的标识符集合,希望给出构造二分搜索树的方法,使得所构造的二分搜索树具有最优的性能。

在实际中也会遇到不成功检索的情况

扩充二叉树:当二叉树里出现空的子树时,就增加新的、特殊的结点——空树叶。

对于原来二叉树里度数为1的分支结点,在它下面增加一个空树叶;

对于原来二叉树的树叶,在它下面增加两个空树叶。

扩充二叉树是满二叉树,新增加的空树叶(以下称外部结点)的个数等于原来二叉树的结点(以下称内部结点)个数加1。

问题描述

设 S={x1, x2, ···, xn} 是一个有序集合,且x1, x2, ···, xn表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素,

而且具有性质:
存储于每个顶点中的元素x 大于其左子树中任一个顶点中存储的元素,小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如(xi, xi+1) 的开区间。
(1) 在二叉树的内部顶点处找到: x = xi
(2) 在二叉树的叶顶点中确定: x∈ (xi , xi+1)

 

 

 图例

代码

#include<bits/stdc++.h>
using namespace std;
const int M = 100;
double C[M][M], W[M][M], p[M], q[M];
int S[M][M];
int n, i, j, k;
void Optimal_BST()
{
    for (i=1;i<=n;i++)
    {
        C[i][i - 1] = 0.0;
        W[i][i - 1] = q[i - 1];
    }
    for (int t=1;t<=n;t++)
    {
        for (i = 1; i <= n - t + 1; i++)
        {
            j = i + t - 1;
            W[i][j] = W[i][j - 1] + p[j] + q[j];
            C[i][j] = C[i][i - 1] + C[i + 1][j];
            S[i][j] = i;
            // 选取i+1到j之间的某个下标的关键字作为i到j的根,如果组成的期望值最小
            // 则k为i到j的根结点
            for (k = i + 1; k < j; k++)
            {
                double tmp = C[i][k - 1] + C[k + 1][j];
                if (tmp<C[i][j] && fabs(tmp - C[i][j])>1E-6)
                {
                    C[i][j] = tmp;
                    S[i][j] = k;        // 记录i到j结点的树根
                }
            }
            C[i][j] += W[i][j];
        }
    }
}
void Construct_Optimal_BST(int i,int j,bool flag)
{
    if (flag == 0)
    {
        cout << "S" << S[i][j] << "是根" << endl;
        flag = 1;
    }
    int k = S[i][j];
    // 如果左子树是叶子
    if (k - 1 < i)
    {
        cout << "e" << k - 1 << "is the left child of " << "S" << k << endl;
    }
    else
    {
        cout << "S" << S[i][k - 1] << " is the left child of" << "S" << k << endl;
        Construct_Optimal_BST(i, k - 1, 1);
    }
    // 如果右子树是叶子
    if (k>=j)
    {
        cout << "e" << j << " is the right child of " << "S" << k << endl;
    }
    else
    {
        cout << "S" << S[k + 1][j] << " is the right child of " << "S" << k << endl;
        Construct_Optimal_BST(k + 1, j, 1);
    }
}
int main()
{
    cout << "请输入关键字的个数:" << endl;
    cin >> n;
    cout << "请依次输入关键字的频率:" << endl;
    for (i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
    cout << "请依次输入每个虚结点的搜索频率:" << endl;
    for (i = 0; i <= n; i++)
    {
        cin >> q[i];
    }
    Optimal_BST();
    cout << "最小的搜索成本是" << C[1][n] << endl;
    cout << "最优二叉搜索树为:" << endl;
    Construct_Optimal_BST(1, n, 0);
    system("pause");
    return 0;
}

 

标签:检索,结点,二叉,关键字,搜索,二叉树,最优
From: https://www.cnblogs.com/kuailest/p/16894453.html

相关文章

  • 分布式搜索引擎01-- elasticsearch基础
    分布式搜索引擎01--elasticsearch基础0.学习目标1.初识elasticsearch1.1.了解ES1.1.1.elasticsearch的作用elasticsearch是一款非常强大的开源搜索引擎,具备非常多强......
  • 分布式搜索引擎02-elasticsearch的数据搜索功能-DSL和RestClient实现搜索
    分布式搜索引擎02在昨天的学习中,我们已经导入了大量数据到elasticsearch中,实现了elasticsearch的数据存储功能。但elasticsearch最擅长的还是搜索和数据分析。所以今天,我......
  • 分布式搜索引擎03-数据聚合
    分布式搜索引擎030.学习目标1.数据聚合聚合(aggregations)可以让我们极其方便的实现对数据的统计、分析、运算。例如:什么品牌的手机最受欢迎?这些手机的平均价格、最高......
  • 剑指offer——Day06搜索与回溯算法(简单)
    Day62022.11.12搜索与回溯算法(简单)32.Ⅰ.从上到下打印二叉树自己实现用队列来实现。将当前节点的值打印后向queue中push它的左右非NULL儿子节点,并将该节点pop出去代......
  • 剑指offer——Day07搜索与回溯算法(简单)
    Day72022.11.13树的子结构26.树的子结构自己实现应该是用递归,具体没有思路,直接看题解了题解用两个函数isSubStructure()和recur()来解决。就不断去递归比较A的子树......
  • AI 智能搜索 开源hanlp实现
     AI智能搜索通过网络资源可知有很多种开源方式实现智能搜索,其中hanlp在GitHub中响应居高参考链接:https://www.hanlp.com/Java版:https://github.com/hankcs/HanLPPyth......
  • 20221115_T4B_折半搜索双指针
    题意市面上共有\(n\)张门票,方便起见,我们把它们从\(1\)至\(n\)编号。其中,\(i\)号门票对应的场次为第\(b_i,1\leqb_i\leqk)\)场,价格为\(c_i\)元,且座位的排数为......
  • 直播平台源码,vue 写搜索效果
    直播平台源码,vue写搜索效果代码如下 <!DOCTYPEhtml><html><head><metacharset="utf-8"><title></title></head><body><divid="app"><h1>搜索水果</h1><inputtype=......
  • 最优秀的一批程序员,在用最蠢的方式写代码
    善战者,无赫赫之功。这句话的字面意思是说,总是轻松打胜仗的将军,别人就会觉得他没有多少功劳。那对于一个程序员来说,按部就班的完成需求,算不算一种成绩?悲观地说,可能并不算。不......
  • 立创商城封装搜索载入插件 AD-LCSC 转载
    AD-LCSC脚本地址:Releases·TimonPeng/AD-LCSC-Addons(github.com)立创商城封装搜索载入插件开源AltiumDesigner立创商城封装搜索载入插件-立创社区(szlcsc.co......