最优二叉搜索树探究【C/C++】

客官°小女子只卖身不卖艺 2022-05-04 08:27 175阅读 0赞

# 简述 #

## 什么是二叉树 ##

下面的这棵树，就是二叉搜索树

![在这里插入图片描述][70]

## 相对于什么最优 ##

这里考虑的是ASL（average search length）平均搜索长度。即根据概率来生成ASL最小的搜索树。

--------------------

到这里，最优二叉搜索树的概念就已经清楚了。

--------------------

## 解决方法 ##

如果是递归来搜索也是可以的，但是很明显需要做很多的重复的计算。  
为了解决这个问题，所以我们采用动态规划来做，很明显，这样能降低计算的复杂度。

*  处理方法：**动态规划**

在非叶节点上时候，为特定的数值，在叶子节点上时候，是一个区间（**这里不懂可以再看上面的图**）

显然，我们需要先用递归的方式来理解一下这个问题。

*  `w[i][j] = a[i-1] + b[i] +.. + b[j] + a[j]`
 *  其中，`a[i]`表示的是第i个区间的概率，`b[i]`表示的是第i个节点的概率
 *  `w[i][i] = a[i-1] + b[i] + a[i]` 这不就是一个只有一个非叶子节点的二叉树么？
 *  如果是只有一个非叶子节点的二叉搜索树的话：我们这里很好求
 *  进行扩展：我们现在只考虑这么的一棵树，中间点为具体数值，那么就是非叶子节点。然后根据这个节点(**设为节点k**)的进行推理`ASL[i][j] = b[k] * 1 + (ASL_Left_tree + 1) * W[i][k-1] + (ASL_Right_tree + 1) * W[k+1][j]`
 *  注意到，中间有部分可以提出来，得到`ASL[i][j] = W[i][j] + (ASL_Left_tree ) * W[i][k-1] + (ASL_Right_tree ) * W[k+1][j]` （这里`W[i][j] = 1`）
 *  但是我们这里其实考虑的整棵数，对于更一般的，我们要考虑一个树的一部分。
 *  `ASL[i][j] = 1 + (ASL_Left_tree ) * W[i][k-1] + (ASL_Right_tree ) * W[k+1][j]` 这是上面的整理。下面再接着推理。
 *  `W[i][j] * ASL[i][j] = W[i][j] + (ASL_Left_tree ) * W[i][k-1] + (ASL_Right_tree ) * W[k+1][j]` 注意，这里的`W[i][j]`都是在全局的树上算的，因为这时候把左边的`W[i][j]` 就类似的得到的我们想要的条件概率下是计算算法。
 *  做类似的变换很容易发现，所谓左树和右树也是可以用`i,j`来表示的。然后，就得到一个很重要的 递推公式
 *  `W[i][j] * ASL[i][j] = W[i][j] + ASL[i][k-1] * W[i][k-1] + ASL[k+1][j] * W[k+1][j]` 但是我们注意到这里的 `w[i][j] * ASL[i][j]` 其实可以作为一个整体来计算的。这里就设置为`M[i][j]`
 *  所以公式变为了`m[i][j] = w[i][j] + m[i][k-1] + m[k+1][j]`。注意到，我们这里是假设了采用的是以第k个点作为分割点来构建子树的。但是实际上这个最优的究竟该怎么搞，肯定是需要遍历所有的可能的k来得到结果的。
 *  所以，其实`m[i][j] = w[i][j] + min(m[i][k-1] + m[k+1][j])`。但是我们这里需要注意到，我们想要的整棵数的ASL其实就是`m[1][N]`，而此时的概率为1了，所以得到的相等。

**边界条件讨论：**

*  `w[i+1][i]` 这种情况究竟是算什么呢？我们这里设置为`a[i]`
 *  `m[i+1][i]`这种情况呢？我们令它为0。这样，我们在利用上面的公式推理出来的结果的时候，就得到了`m[i][i] = w[i][i]`。
 *  至于它为0，其实很好证明，由于在`ASL[i+1][i]`肯定要是0才对的。

## 程序实现细节 ##

主要是注意一下，实现的时候，如何安排数据。建议的话，将b的那个数组前面空出一个来，这样的话，就不需要修改太多的公式。  
**原因如下：**

*  `w[i][j] = a[i-1] + b[i] +.. + b[j] + a[j]`
 *  为了避免程序实现的时候越界。（否则就需要修改公式了，这里先可以先完成之后，再考虑优化的问题）

--------------------

**看到这，如果你有去手动实现的话，你会意识到另外一个问题。这个可行的k究竟是什么？**

*  由于我们之前已经谈到了设置了时候，我们讲b的那个数组第一个位置放空，那么来说`i和j`都是从1开始遍历起的，终止当然就是以`N`作为终止点。
 *  知道上面的这些之后，我们就很容易理清了，我们尝试将i到j上的所有节点

## C++代码 ##

注释部分写好了详细的代码说明~  
main函数开始部分是自动生成数据来进行测试

#include <iostream>
    using namespace std;
    #include <string>
    #define N 15
    
    int S[N];
    double b[N + 1];
    double a[N + 1];
    // w[i][j] 表示i,j段的概率
    // 
    double w[N + 2][N + 2];
    // w[i][j] = a[i-1] + b[i] +...+b[j] + a[j]
    double m[N + 2][N + 2];
    int divided_point[N + 1][N + 1];
    string getAns(int begin, int end);
    int main() {
    	double sum = 0;
    	for (int i = 0; i < N; ++i) {
    		S[i] = 2 * i + 1;
    		b[i+1] = 0.6 / (N+1);
    		a[i] = 0.4 / (N+1);
    		sum += (a[i] + b[i+1]);
    	}
    	b[0] = 0;
    	a[N] = 1 - sum;
    	/*for (int i = 0; i < N; ++i) {
    		S[i] = 2 * i + 1;
    		a[i + 1] = 0.04;
    		b[i + 1] = 0.06;
    	}
    	a[0] = 0.1;
    	b[0] = 0;*/
    	// 初始化
    	for (int i = 0; i <= N; ++i) {
    		w[i + 1][i] = a[i];
    		m[i + 1][i] = 0;// ASL[i][i-1]为0！
    	}
    	// r表示的是长度
    	for (int r = 0; r < N; ++r)
    		for (int i = 1; i <= N-r; i++) {
    			// i表示的是起始点
    			int j = i + r; // j表示的是终点
    			// 由w[i][j]构造函数很容易得到
    			w[i][j] = w[i][j - 1] + a[j] + b[j];
    			m[i][j] = m[i + 1][j]; // 因为m[i][i-1]为0
    			divided_point[i][j] = i;
    			// 中间划分点设为b[i] k为滑动的移动点
    			for (int k = i + 1; k <= j; k++) {
    				double t = m[i][k - 1] + m[k + 1][j];
    				if (t < m[i][j]) { 
    					m[i][j] = t; 
    					divided_point[i][j] = k;
    				}
    			}
    			m[i][j] += w[i][j];
    		}
    	cout << m[1][N] << " " << w[1][N] << endl;
    	system("pause");
    }

[70]: /images/20220504/83faace3e038458999da66856b33cc4c.png