次优二叉搜索树

缘起

【1】中我们介绍了最优二叉搜索树. 并给出了算导中的算法实现. 但是它最大的弊病就在于令人尴尬的建树的O(n^3)的复杂度上. 所以【2】的9.1节提出了近似解决方案——次优二叉搜索树. 也就是确定根节点的算法并不像【1】中那样严格的根据dp公式得到最佳分割点，而是只要两边的权重之差达到最小即可(具体公式可以参见【2】，已经写的很清晰了).

大量实践证明，次优比最优在查找性能上的损失不会超过3%, 一般都在 %1和%2左右，但是次优建树的算法复杂度是O(nlogn)的，远比最优的O(n^3)来的可行性高. 所以实际中人们使用的都是次优查找树. 顺便说一句，次优和最优都是静态查找树.

顺便说一下，相比 SecondOptimal-BST 这种名词，我更喜欢 NearlyOptimal-BST.

本文就来实现这一算法.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;
#define LOCAL
const int MAX_N = 7; // 英语单词的最多个数（背景参见算导）
int data[MAX_N] = {0,'A', 'B', 'C', 'D', 'E'}; // 关键词, 索引0不用于存储数据（保证升序即可, 因为次优二叉搜索树前提是 一棵BST）
double p[MAX_N] = {0, 0.4, 0.15, 0.1, 0.05, 0.1}; // 各个节点被搜索的概率,索引0不用于存储数据

double sp[MAX_N] = {0}; // p的部分和序列

typedef struct NearlyOptimalBSTNode // 其实和普通BST没区别, 区别只在构建BST的过程中
{
	NearlyOptimalBSTNode *left, *right; // 左右孩子
	char val; // 数据

	NearlyOptimalBSTNode(char val): val(val), left(0), right(0){}
} NearlyOptimalBSTNode, *NearlyOptimalBST;

void build(NearlyOptimalBST &root, int lb, int ub) // 使用 data[lb..., ub]构建 次优二叉搜索树
{
	if (lb > ub) return; // 什么也不做，注意，这是有可能的，你看下面的递归，如果 _min_r为lb或者ub的话
	if (lb == ub) // 一个节点构建次优显然只能它自己做根节点
	{
		root = new NearlyOptimalBSTNode(data[lb]);
		return;
	}
	double _min = sp[ub]-sp[lb]; // 下面的r取lb的时候的左右子树的差距, 即算法认定一开始是根节点取lb的时候最小，下面再比较选出真正最小的
	int _min_r = lb;
	for (int r = lb+1; r<=ub; r++) // 【2】的公式 9-13
	{
		int t = fabs(sp[ub]+sp[lb-1]-sp[r]-sp[r-1]);
		if (_min > t) // 更新, 因为发现更小的了
		{
			_min = t;
			_min_r = r;
		}
	}
	// _min_r是根节点
	root = new NearlyOptimalBSTNode(data[_min_r]);
	build(root->left,lb, _min_r-1); // 递归构建左右子树
	build(root->right, _min_r+1, ub);
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	NearlyOptimalBST root = 0;
	int n = 5;
	for (int i = 1; i<=n; sp[i] = sp[i-1] + p[i],i++); // 初始化部分和序列
	build(root, 1, n);

	return 0;
}

最后测试数据的bst长成下面的样子

上面的数字表示被搜索的概率

参考

【1】https://yfsyfs.github.io/2019/06/17/%E6%9C%80%E4%BC%98%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/

【2】数据结构（C语言版）严蔚敏 吴伟民