【动态规划】最优二叉搜索树——算法设计与分析

文章目录

• 一、问题定义
• • 1.1 二叉搜索树
  • 1.2 概率分布
  • 1.3 检索数据的平均时间
  • 1.4 最优二叉搜索树问题
• 二、算法
• • 2.1 分析问题结构
  • 2.2 建立递推关系
  • 2.3 自底向上计算
  • 2.4 追踪最优方案
  • 2.5 复杂度分析

一、问题定义

1.1 二叉搜索树

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

规定树根为第0层，圆结点为数据，方结点为数据之间的空隙。

1.2 概率分布

实际上每个数据出现的概率是不同的，给定序列，构造二叉搜索树，形成了个结点，和个空隙，其中

记在出现的概率为，在空隙的概率为，则的存取概率分布为

1.3 检索数据的平均时间

对于数据集和存取概率分布：

规定树根为第0层，结点在中的深度是，空隙的深度为，平均比较次数为：

例如，给定树：

，（用**包围）

则平均检索时间为：

1.4 最优二叉搜索树问题

对于数据集和存取概率分布，不同的树的组织形式会产生不同的平均检索时间，如何求一棵平均比较次数最少的二叉搜索树？

二、算法

2.1 分析问题结构

以为界划分子问题：

令，存取概率分布：

2.2 建立递推关系

假设以作为树的根，则树被划分为三部分：

左子树：

根：

右子树：

令，表示到之间所有概率（数据和空隙）之和；设是相对于输入和的最优二叉搜索树的平均比较次数

则可建立递推方程：

（1）为了不遗漏最优解，所以需要从到依次选取做根尝试，选出最小值

（2）表示以做根的最优左子树的比较次数

（3）表示以做根的最优右子树的比较次数

（4）对于给定的数据，需要先与根进行比较后才可以进入到左子树或右子树；而由于使用根将左子树和右子树连接起来，子树的每个结点高度均增加了一层，所以在比较次数上也要加1，所以是由增加的左子树的比较次数、增加的右子树的比较次数、和根的比较次数之和

的证明：

由根引起的比较次数增加为：

2.3 自底向上计算

初始化：当左子树或右子树为空时，其平均查找数为0

不妨以来观察：

	0	1	2	3	4
0	NULL	NULL	NULL	NULL	NULL
1	0 √	√	√	√	※
2	NULL	0			√
3	NULL	NULL	0		√
4	NULL	NULL	NULL	0	√
5	NULL	NULL	NULL	NULL	√

显然，要计算一个值，我们需要计算它一行一列的数据，因此确定计算顺序：

2.4 追踪最优方案

构造追踪数组，表示的根节点。

在计算的过程中，选出最小的，记录

追踪时，从出发，假设，则说明在处进行了分割，分为子树和，再分别查看和…

如此寻找直至对角线部分。

2.5 复杂度分析

时间复杂度

空间复杂度