最优二分检索树

2018-05-08 17:18:51

/*************************

程序名称：   最优二分检索树
作成日期：   2018/5/8
作者：     飞翔的女武神
其中树图绘制程序来源于网络

*************************/

#include<iostream>
#include<cstdio>
#include<conio.h>
#include<string>
#include<fstream>

using namespace std;

#define ForMyLove return 0

const int maxn = 2000;

double  chn[maxn];          //某元素的查找代价
double  pref[maxn];         //某段元素的查找代价之和
double  C[maxn][maxn];      //某段元素的平均查找代价
int     R[maxn][maxn];      //某段元素的根
int     tre[maxn];          //树结构

double sumft(int i, int j) {
    return pref[j] - pref[i - 1];
}

string replace(string &s) {
    string ss;
    for (int i = 0; i<s.size(); i++) {
        if (s[i] != '|')ss.append(".");
        else ss.append("|");
    }
    return ss;
}

class Node {
public:
    int  value;
    Node *left;
    Node *right;
    string s;//该节点对应的一行字符串
    int   n;//0、1、2分别代表根节点、左孩子、右孩子

    Node(int value = 0, int n = 0) {
        this->value = value;
        this->n = n;
        this->left = NULL;
        this->right = NULL;
        this->s.append(itoa(value, new char[10], 10));
    }
    void addNode(int value = 0) {
        //保证有孩子的节点对应的字符串末尾有"-|"
        if ('|' != s[s.size() - 1])s.append("-|");
        string ss;
        int index;
        //判断新节点添加到那一边
        if (value <= this->value) {
            //若没有左孩子,则添加为该节点的左孩子
            if (NULL == this->left) {
                left = new Node(value, 1);
                //新节点是父节点的左孩子，这时如果父节点也是其上一层节点的左孩子，那么把前面的都换成点，否则只把前面的数字换成点
                if (1 == this->n) {
                    ss = replace(s).substr(0, s.size() - 1);
                    index = ss.rfind("|");
                    if (index != string::npos)ss = ss.substr(0, index) + "." + ss.substr(index + 1);
                    ss.append("|-");
                }
                else {
                    ss = replace(s) + "-";
                }
                left->s.insert(0, ss);
            }
            else {
                this->left->addNode(value);
            }
        }
        else {
            //此处同上
            if (NULL == this->right) {
                right = new Node(value, 2);
                if (2 == this->n) {
                    ss = replace(s).substr(0, s.size() - 1);
                    index = ss.rfind("|");
                    if (index != string::npos)ss = ss.substr(0, index) + "." + ss.substr(index + 1);
                    ss.append("|-");
                }
                else {
                    ss = replace(s) + "-";
                }
                right->s.insert(0, ss);
            }
            else {
                right->addNode(value);
            }
        }
    }
    void print() {
        if (NULL != this->right)this->right->print();

        cout << s << endl;

        if (NULL != this->left)this->left->print();
    }
};

void bldTre(int &tag, int bg, int ed) {
    if (bg > ed) {
        return;
    }

    tre[tag++] = R[bg][ed];
    if (bg == ed) {
        return;
    }

    bldTre(tag, bg, R[bg][ed] - 1);
    bldTre(tag, R[bg][ed] + 1, ed);
}

int main() {

    /*
    //输入
    int n;
    cout << "请输入二分检索树的节点个数(<" << maxn << ")：";
    scanf("%d", &n);

    cout << "请输入每个节点被查找到的概率：";
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &chn[i]);
    }
    */

    //文件读入
    int n;
    ifstream ifs;
    ifs.open("Input.txt");

    ifs >> n;
    cout << "二分检索树的节点个数：" << n << endl;
    cout << "每个节点被查找到的概率：";
    for (int i = 1; i <= n; i++) {
        ifs >> chn[i];
        cout << chn[i] << " ";
    }
    cout << endl;

    //计算前缀和
    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + chn[i];
    }

    //初始化表
    for (int i = 1; i <= n; i++) {
        C[i][i - 1] = 0;
        C[i][i] = chn[i];
        R[i][i] = i;
    }
    C[n + 1][n] = 0;

    //填表的其他部分
    double minVal;
    for (int d = 1; d <= n - 1; d++) {              //某段元素的跨度

        for (int i = 1; i <= n - d; i++) {          //该段的起点

            int j = i + d;                          //该段的终点

            //更新该位置的最小值
            minVal = maxn;                          //初始化最小值
            for (int k = i; k <= j; k++) {
                if (C[i][k - 1] + C[k + 1][j] < minVal) {
                    minVal = C[i][k - 1] + C[k + 1][j];
                    R[i][j] = k;                    //更新根节点
                }
            }

            //加上该段的概率总和
            C[i][j] = minVal + sumft(i, j);

        }

    }

    //打印结果
    cout << "最优二分检索树的平均查找代价为：" << C[1][n] << endl;
    cout << "树图如下：" << endl;

    //打印树图
    int len = 0;
    bldTre(len, 1, n);

    Node node(tre[0]);
    for (int i = 1; i < len; i++) {
        node.addNode(tre[i]);
    }
    node.print();

    ForMyLove;

}
/**************************************

Input:
4
0.1 0.2 0.4 0.3

**************************************/

/**************************************

Output:

二分检索树的节点个数：4
每个节点被查找到的概率：0.1 0.2 0.4 0.3
最优二分检索树的平均查找代价为：1.7
树图如下：
..|-4
3-|
..|-2-|
......|-1

***************************************/

更多相关内容

动态规划：最优二分检索树
千次阅读 多人点赞 2021-05-14 23:23:01

1. 二分检索树的性能能成功检索的关键字是绿色的，即ai，不能成功被检索的关键字是红色的，即Ei，假设他们按从小到大排列。他们被检索的概率分别是P(i)和Q(i)。设level(ai)为第i内个节点所在深度，level(Ei)为第...

1. 二分检索树的性能

能成功检索的关键字是绿色的，即ai，不能成功被检索的关键字是红色的，即Ei，假设他们按从小到大排列。他们被检索的概率分别是P(i)和Q(i)。

设level(ai)为第i内个节点所在深度，level(Ei)为第i外个节点所在深度。

能使
$\sum_{1 \leq i \leq n} \mathrm{P}(\mathrm{i}) * \operatorname{level}\left(a_{i}\right)+\sum_{0 \leq \mathrm{i} \leq \mathrm{n}} \mathrm{Q}(\mathrm{i}) *(\operatorname{level}(E i)-1)$

取值最小的二分检索树为最优二分检索树。

上图二分检索树的代价为P(2)*1 + P(1)*2 + P(4)*2 + P(3)*3 + P(5)*3 + Q(0)*2 + Q(1)*2 + Q(2)*3 + Q(3)*3 + Q(4)*3 + Q(5)*3。

2.多阶段决策

将最优二叉检索树的构造，看作一个多阶段决策过程。第i个阶段要决策怎样构造一个共有i个内节点的二叉检索树。即第一个阶段，找出所有只有1个内节点的检索树，第二个阶段，找出所有有2个节点的检索树，第三阶段，找出所有3个节点的检索树。注意，第i个阶段，依赖于第i-1个阶段，体现在当节点数增加1时，要怎样调整树根，才能保证是最优二叉检索树。也就是说，第i个阶段要遍历所有节点，其左子树和右子树的装配来自于第i-1个阶段已经决策好的最优检索树，找到总成本最小的一种情况。

记原始问题为 $T_{0n}$ ，即要构造 $E_0, a_1, E_1, ..., a_n, E_n$ 共 $2 n + 1$ 个节点的最优二分检索树。

设 $C (i, j)$ 为 $T_{ij}(E_i, a_i, E_{i+1}, ..., a_j, E_j)$ 的检索成本。则原问题 $T_{0n}$ 的检索成本为 $C (0, n)$ 。

那么第 $n$ 阶段的决策过程，就是确定一个树根 $A_K$ ，使 $C(0, n)=min\{A_k\}$ ，他表示以 $A_k$ 为根，左右子树均来自于第 $n - 1$ 个阶段已经确定的最优二叉检索树的成本。

3.左右子树的成本

以 $a_k$ 为根，其左右子树的成本分别为 $C (0, k - 1)$ 和 $C (k, n)$ 。

$\begin{array}{l} \operatorname{COST}(L)=\sum_{1 \leq i<k} P(i)^{*} \operatorname{level}\left(a_{i}\right)+\sum_{0 \leq i<k} Q(i)^{*}\left(\operatorname{level}\left(E_{i}\right)-1\right) \\ \operatorname{COST}(R)=\sum_{k<i \leq n} P(i) * \operatorname{level}\left(a_{i}\right)+\sum_{k \leq i \leq n} Q(i)^{*}\left(\operatorname{level}\left(E_{i}\right)-1\right) \end{array}$

4. 递推公式

以上只求出了左右子树的成本，其中的 $l e v e l ()$ 都是以子树为标准测定的，而要把子树装配到 $a_k$ 上形成原始的二分检索树，需要再加上左右子树所有节点的概率和ak的概率P(k)，即所有节点的概率和，1。

所以此二叉搜索树的代价为：
$\sum_{0 \leq i \leq n} {Q(i)}+\sum_{1 \leq i \leq n (i!=k)} {P(i)} + P(k)\\ =COST(L)+COST(R)+ \sum_{0 \leq i \leq n} {Q(i)}+\sum_{1 \leq i \leq n} {P(i)} \\ =COST(L)+COST(R)+1$

所以原问题转化为：

$n)=min_{1\leq k \leq n}\{C(0, k-1)+C(k, n)+1\}$

类比原问题，那么任意 $i$ 到 $j$ 的节点，其最优二叉搜索树的成本为：

$j)=min_{i< k \leq j}\{C(i, k-1)+C(k, j)+Q(i)+\sum_{i<r\leq j}{[P(r)+Q(r)]} \}$

记 $j)=Q(i)+\sum_{i<r\leq j}{[P(r)+Q(r)]}$

则 $j)=\min_{i< k \leq j}\{C(i, k-1)+C(k, j)+W(i, j) \}$

至此，递推公式求解完成。

5. 例题

初始状态：
$W(i, i)=Q(i)表示初始化未成功检索节点E_i$ $C (0, 0) = 0 表示无成本$ $R (0, 0) = 0 表示空树$

且 $j)=Q(i)+\sum_{i<r\leq j}{[P(r)+Q(r)]} \\ =Q(i)+\sum_{i<r< j}{[P(r)+Q(r)]+P(j)+Q(j)} \\ =W(i, j-1)+P(j)+Q(j)$

先算 $W$

第0阶段：

初始化所有未成功检索的节点：

$W (0, 0) = Q (0) = 2$ $W (1, 1) = Q (1) = 3$ $W (2, 2) = Q (2) = 1$ $W (3, 3) = Q (3) = 1$ $W (4, 4) = Q (4) = 1$

第1阶段：

$W (0, 1) = W (0, 0) + P (1) + Q (1) = 2 + 3 + 3 = 8$

$W (1, 2) = W (1, 1) + P (2) + Q (2) = 3 + 3 + 1 = 7$

$W (2, 3) = W (2, 2) + P (3) + Q (3) = 1 + 1 + 1 = 3$

$W (3, 4) = W (3, 3) + P (4) + Q (4) = 1 + 1 + 1 = 3$

第2阶段：

$W (0, 2) = W (0, 1) + P (2) + Q (2) = 8 + 3 + 1 = 12$

$W (1, 3) = W (1, 2) + P (3) + Q (3) = 7 + 1 + 1 = 9$

$W (2, 4) = W (2, 3) + P (4) + Q (4) = 3 + 1 + 1 = 5$

第3阶段：

$W (0, 3) = W (0, 2) + P (3) + Q (3) = 12 + 1 + 1 = 14$

$W (1, 4) = W (1, 3) + P (4) + Q (4) = 9 + 1 + 1 = 11$

第4阶段：

$W (0, 4) = W (0, 3) + P (4) + Q (4) = 14 + 1 + 1 = 16$

再算 $C$ 和 $R$

第0阶段(空树)：

$C (0, 0) = R (0, 0) = 0$

$C (1, 1) = R (1, 1) = 0$

$C (2, 2) = R (2, 2) = 0$

$C (3, 3) = R (3, 3) = 0$

$C (4, 4) = R (4, 4) = 0$

第1阶段(只有1个节点)：

$C (0, 1) = W (0, 1) = 8, R (0, 1) = 1$

$C (1, 2) = W (1, 2) = 7, R (1, 2) = 2$

$C (2, 3) = W (2, 3) = 3, R (2, 3) = 3$

$C (3, 4) = W (3, 4) = 3, R (3, 4) = 4$

第2阶段(2个节点)：

$C(0,2)=W(0,2)+\min_{0<k\leq{2}}{\{C(0,0)+C(1,2), C(0,1)+C(2,2)\}}=12+\min{\{7,8\}}=19, R(0,2)=1$

$C(1,3)=W(1,3)+\min_{1<k\leq{3}}{\{C(1,1)+C(2,3), C(1,2)+C(3,3)\}}=9+\min{\{3,7\}}=12, R(1, 3)=2$

$C(2,4)=W(2,4)+\min_{2<k\leq{4}}{\{C(2,2)+C(3,4), C(2,3)+C(4,4)\}}=5+\min{\{3,4\}}=8, R(2,4)=3$

第3阶段(3个节点)：

$C(0,3)=W(0,3)+\min_{0<k\leq{3}}{\{C(0,0)+C(1,3), C(0,1)+C(2,3)，C(0,2)+C(3,3)\}}=14+\min{\{12,11, 19\}}=25, R(0,3)=2$

$C(1,4)=W(1,4)+\min_{1<k\leq{4}}{\{C(1,1)+C(2,4),C(1,2)+C(3,4), C(1,3)+C(4,4)\}}=11+\min{\{8,10,12\}}=19, R(1, 4)=2$

第4阶段(4个节点)：

$C(0,4)=W(0,4)+\min_{0<k\leq{4}}{\{C(0,0)+C(1,4), C(0,1)+C(2,4)，C(0,2)+C(3,4), C(0,3)+C(4,4)\}}=16+\min{\{19,16,22,25\}}=32, R(0,4)=2$

树的形态
最终决策为R(0,4)=2，表示最优二叉检索树以a2为根节点，其左子树为T01，右子树为T24。查看C(0,1)对应的决策，发现R(0,1)=1，说明该节点为a1，查看C(2,4)对应的决策，发现R(2,4)=3，说明其右子树以a3为根节点。a3的左子树为T22，右子树为T34，说明a3左子树为未成功检索，右子树为a4。

其最终形态：

收起

展开全文

算法动态规划 c++
用动态规划法构造最优二分检索树
2009-04-15 13:11:25

在VC++6。0下用C++语言描述用动态规划法构造最优二分检索树问题，是学习算法的很好参考。

收起
动态规划,最优二分检索树
千次阅读 2019-10-25 10:21:23

最优二分检索树 最优二分检索树问题：求一棵使得预期成本最小的二分检索树一、问题引出或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于...

最优二分检索树

最优二分检索树问题：求一棵使得预期成本最小的二分检索树

一、问题引出

或是一棵空树；或者是具有如下性质的非空二叉树：

（1）左子树的所有结点均小于根的值；

（2）右子树的所有结点均大于根的值；

对于一个给定的标识符集合，可能有若干棵不同的二分检索树:

不同形态的二分检索树对标识符的检索性能是不同的。

设给定的标识符集合是{a1,a2,…,an}，并假定a1＜a2＜ … ＜ an。设，P(i)是对ai检索的概率，Q(i)是正被检索的标识符X恰好满足： ai＜X＜ai+1，0≤i≤n（设a0=-∞,an+1=+∞)时的概率，即一种不成功检索情况下的概率。

内结点：代表成功检索情况，刚好有n个

外结点：代表不成功检索情况，刚好有n＋1个

平均检索成本＝Σ每种情况出现的概率×该情况下所需的比较次数

平均检索成本的构成：成功检索成分＋不成功检索成分

       ●成功检索：在内结点终止的成功检索    P(i)*level(ai) ；其中，level(ai)= 结点ai的级数=l

       ●不成功检索：外部结点的不成功检索的成本分担额为：Q(i)*(level(Ei)-1)

最优二分检索树问题：求一棵使得预期成本最小的二分检索树

二、问题分析

2.1、多阶段决策过程

把构造二分检索树的过程看成一系列决策的结果。

决策的策略：决策树根，如果{a1,a2,…,an}存在一棵二分检索树，ak是该树的根，则内结点a1,a2,…,ak-1和外部结点E0,E1,…,Ek-1将位于根ak的左子树中，而其余的结点将位于右子树中。

       ● 左、右子树的预期成本——左、右子树的根处于第一级

       ● 左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少1

2.1、最优性原理成立

若T最优二分检索树，则COST(L)和COST(R)将分别是包含a1,a2,…,ak-1和E0,E1,…,Ek-1、及ak＋1, ak+2, …,an和Ek,Ek+1,…,En的最优二分检索(子)树。记由ai+1,ai+2,…,aj和Ei,Ei+!,…,Ej构成的二分检索树的成本为C(i,j)，则对于最优二分检索树T有，

                COST(L) = C(0,k-1)

                COST(R) = C(k,n)

C[i,j] 表示点i+1，i+2到点j所组成的最优解

W[i,j] 表示i-j所有节点的概率和，因为在左右子树添加一个根节点，导致左右子树的所有节点的深度增加了1，所以加上W[i,j]

三、最优检索树构建过程

四、例子

设n=4,且(a1,a2,a3,a4)=(do,if,read,while)。设P(1:4) = (3,3,1,1)，Q(0:4) = (2,3,1,1,1) (概率值“扩大”了16倍)

初始：W(i,i)=Q(i)     C(i,i)=0  R(i,i)=0

1、计算W C R

2、计算结果

3、二分检索树：

       T04=2 =>T01(左子树），T24(右子树）  即0到4以2为分界

       T01=1 =>T00(左子树），T11(右子树）

       T24=3 =>T22(左子树），T34(右子树）

4、树的形态

收起

展开全文

算法导论 · 动态规划 · 最优二分检索树

千次阅读 2019-07-26 23:27:41

如果已知集合元素的搜索概率，那么自然会提出一个关于最优二叉搜索树的问题，搜索中的平均比较数是可能的最小值。例如，考虑四个要搜索的键a、b、c和d，其概率分别为0.1、0.2、0.4和0.3。则0.11+0.22+0.43+0.34=2.9...

算法说明
构造最佳二叉搜索树：
如果已知集合元素的搜索概率，那么自然会提出一个关于最优二叉搜索树的问题，搜索中的平均比较数是可能的最小值。
例如，考虑四个要搜索的键a、b、c和d，其概率分别为0.1、0.2、0.4和0.3。则0.11+0.22+0.43+0.34=2.9
源代码

#include <cstdio>
#include <cstring>

#define maxn 101
#define minc(a, b) (a) > (b) ? (b) : (a)
#define INF 1 << 29 

double c[maxn][maxn], p[maxn];
int n, root[maxn][maxn];
int main() {
	memset(c, 0, sizeof(c));
	memset(root, 0, sizeof(root));
	freopen("7.optimalBinarySearchTrees.txt", "r", stdin);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lf", &p[i]);
	}
	
	//init
	for(int i = 0; i <= n; i++) {
		c[i][i-1] = 0;
		c[i][i] = p[i];
		root[i][i] = i;
	}
	for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n - k + 1; i++) {
            int j = i + k - 1;
			double sum = 0;
            c[i][j] = INF;

			for(int k = i; k <= j; k++) {
				sum += p[k];
			}
//			printf("%d, %d, %.1f\n", i, j, sum);
            for (int r = i; r <= j; r++) {
                double t = c[i][r - 1] + c[r + 1][j] + sum;
                if (c[i][j] > t) {
                    c[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    }
	
	for(int i = 1; i <= n + 1; i++) {
		for(int j = 0; j <= n; j++) {
			if(c[i][j] == 0) printf("null ");
			else printf("%-5.1f", c[i][j]);
		}
		printf("\n");
	}
	
	printf("\n");
	for(int i = 1; i <= n + 1; i++) {
		for(int j = 0; j <= n; j++) {
			if(c[i][j] == 0) printf("null ");
			else printf("  %-3d", root[i][j]);
		}
		printf("\n");
	}	
	
	return 0;
}

输入数据
运行结果

收起

展开全文

动态规划 C/C++

最优二分搜索树（动态规划）
2015-11-17 14:50:49

设S=(x1,x2,…,xn)是有序集，且x1…，已知键值和区间的存取概率分布为(a0,b1,a1,b2,…,bn,an)，其中ai表示相应区间的搜索概率，bi表示相应键值的...在所有表示有序集的二叉树中找出一棵具有最小平均路长的二叉搜索树

收起
【计算机算法设计与分析】——5.4最优二分检索树
2018-10-19 11:31:00

（n为结点个数）为成本差额转载于:https://www.cnblogs.com/chihaoyuIsnotHere/p/9815498.html

收起
单源点最短路径 最优二分检索树 程序实现
2010-11-18 20:38:27

单源点最短路径，最优二分检索树算法程序实现，包含设计文档和源代码

收起
【动态规划】(下)图像压缩，最大子段和，最优二分检索树--以及对追踪解的一点优化
2021-04-29 20:23:04

动态规划解法介绍完整代码优化查找前序列 O ( n ) O(n) O(n) 最优二叉检索树 介绍完整代码图像压缩介绍引用：计算机中的图像由一系列像素点构成，每个像素点称为一个像素，图像分辨率越高，使用的像素就越多...

收起

算法 c++
算法——最优二分检索树
千次阅读 2013-11-09 00:01:32

算法思想：采用动态规划的方法，如果ak为最优二分检索树的跟，则其左子树也是一棵最优二分检索树，同理，右子树也是一棵最优二分检索树。记由ai+1,ai+2,…,aj和Ei,Ei+1,…,Ej构成的最优二分检索树的预期成本为...

收起

算法动态规划
动态规划_最优二分检索树
2013-11-05 00:31:00

下面逐步的来讲解怎么样通过动态决策构建最优二分检索树，首先一步一步的来：前奏：二分检索树（Binary Search Tree）的定义：二分检索树是一棵二元树，它或者为空，或者其每个结点的数据元素都可以比较大小，且...

收起
最优二分检索树的实现
2008-12-15 16:34:47

已知一个固定的标识符集合，希望产生一种构造二分检索树的方法。

收起
动态规划-最优二分检索树
千次阅读 2013-10-21 23:54:48

最优二分检索树 二分检索树T是一棵二元树 ①T的左子树的所有元素比根结点中的元素小； ②T的右子树的所有元素比根结点中的元素大； ③T的左子树和右子树也是二分检索树。 注：二分检索树要求树中所有结点的元素...

收起
动态规划---->最优二分检索树
千次阅读 2013-05-14 11:04:31

最优二分检索树 最优二分检索树问题：求一棵使得预期成本最小的二分检索树一、问题引出或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均...

收起
基于C++实现的最优二分查找树
2019-07-24 19:17:03

1、实验题目 ...设计算法，输入如表3-1，输出是最优二叉搜索树的结构，形如： k2为根 k1为k2的左孩子 d0为k1的左孩子 …… 表3-1 搜索概率表点击此处下载文档和源码 ...

收起
[算法导论] 动态规划—最优二分搜索树
2018-07-20 20:18:00

我们可以建立一颗二分搜索树来实现英语到汉语的关联。为了更快速地翻译，我们可以使用AVL树或者红黑树使每次查询的时间复杂度Θ(lgn)，实际上对于字典翻译程序来说这么做存在一个问题，比如“the”这个单词经常用，...

收起
最优二分检索树讲解
2017-03-08 19:51:27

http://lib.csdn.net/article/datastructure/10132

收起
算法设计与分析——最优二分搜索树（动态规划）
千次阅读 2018-11-03 18:41:16

最优二分搜索树问题对于一个给定的序列，{b0，a1，b1……an，bn}，其中a1，a2……an是实节点，b0，b1，b2……bn是虚节点（就是二分搜索树最终找不到实节点的范围），如何找出并构建一个总耗费最小的二分搜索树？ ...

收起
动态规划实现最优二分搜索树
2018-11-30 22:06:00

　(1）二叉搜索树（二分检索树）二叉搜索树Ｔ是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：　a·Ｔ的左子树的所有元素比根结点中的元素小；　b·Ｔ的右子树的所有元素比根结点...

收起
动态规划练习题-最优二分查找树
2021-04-13 11:37:58

问题描述：最优二叉查找树：给定n个互异的关键字组成的序列K=，且关键字有序(k1举例说明：n=5的关键字集合以及如下的搜索概率，构造二叉搜索树。期望搜索代价的计算公式：下图中图a显示了给定上面的概率分布pi、qi，...

收起
最小成本二分检索树_OBST
2013-11-30 01:35:07

利用C++实现的最小成本二分检索树，能够根据double类型的成功检索P和不成功检索Q构造出最小成本二分检索树，利用一个二叉树类自动构造出该树，并打印到标准输出！

收起
最优二分搜索树用C语言实现
2010-03-20 19:00:17

最优二分搜索树，OBST算法,用C语言实现，希望对你有帮助

收起
二叉检索树.cpp 数据结构二叉检索树
2019-12-02 22:05:10

二叉检索树 c++数据结构对应于数据机构与算法分析（c++版）第三版或第二版 Clifford A.Shaffer 重庆大学使用教材

收起
最优二叉搜索树的动态规划算法
2020-04-23 17:44:31

使用C#实现的动态规划算法关键字序列：0.15,0.1,0.05,0.1,0.2 非关键字序列：0.05,0.1,0.05,0.05,0.05,0.1 以上的测试数据，输入数据可以得到结果

收起

动态规划：最优二分检索树

1. 二分检索树的性能

2.多阶段决策

3.左右子树的成本

4. 递推公式

5. 例题

用动态规划法构造最优二分检索树

动态规划,最优二分检索树

一、问题引出

二、问题分析

2.1、多阶段决策过程

2.1、最优性原理成立

三、最优检索树构建过程

四、例子

算法导论 · 动态规划 · 最优二分检索树

最优二分搜索树（动态规划）

【计算机算法设计与分析】——5.4最优二分检索树

单源点最短路径最优二分检索树程序实现

【动态规划】(下)图像压缩，最大子段和，最优二分检索树--以及对追踪解的一点优化

算法——最优二分检索树

动态规划_最优二分检索树

最优二分检索树的实现

动态规划-最优二分检索树

动态规划---->最优二分检索树

基于C++实现的最优二分查找树

[算法导论] 动态规划—最优二分搜索树

最优二分检索树讲解

算法设计与分析——最优二分搜索树（动态规划）

动态规划实现最优二分搜索树

动态规划练习题-最优二分查找树

最小成本二分检索树_OBST

最优二分搜索树用C语言实现

二叉检索树.cpp 数据结构二叉检索树

最优二叉搜索树的动态规划算法

最优二分检索树

动态规划：最优二分检索树

1. 二分检索树的性能

2.多阶段决策

3.左右子树的成本

4. 递推公式

5. 例题

用动态规划法构造最优二分检索树

动态规划,最优二分检索树

一、问题引出

二、问题分析

2.1、多阶段决策过程

2.1、最优性原理成立

三、最优检索树构建过程

四、例子

算法导论 · 动态规划 · 最优二分检索树

最优二分搜索树（动态规划）

【计算机算法设计与分析】——5.4最优二分检索树

单源点最短路径 最优二分检索树 程序实现

【动态规划】(下)图像压缩，最大子段和，最优二分检索树--以及对追踪解的一点优化

算法——最优二分检索树

动态规划_最优二分检索树

最优二分检索树的实现

动态规划-最优二分检索树

动态规划---->最优二分检索树

基于C++实现的最优二分查找树

[算法导论] 动态规划—最优二分搜索树

最优二分检索树讲解

算法设计与分析——最优二分搜索树（动态规划）

动态规划实现最优二分搜索树

动态规划练习题-最优二分查找树

最小成本二分检索树_OBST

最优二分搜索树 用C语言实现

二叉检索树.cpp 数据结构二叉检索树

最优二叉搜索树的动态规划算法

最优二分检索树

单源点最短路径最优二分检索树程序实现

最优二分搜索树用C语言实现