最佳二叉排序树定义

最佳二叉排序树（Optimal Binary Search Tree，简称OBST）是一种特殊的二叉树，它具有最优查询效率的特点，通常用于对于大型数据集进行高效率查询的场景。

OBST 是一种二叉排序树，所以它的特点与一般的二叉排序树一样，即具备左小右大的特征。OBST 与一般的二叉排序树不同的是，通过精心构建节点的概率，可以使OBST 的查询次数最少，从而达到最优查询效率的目的。

OBST的节点构成

一个OBST 至少有一个节点，也有可能有很多节点。每一个节点有两个子节点：左边的子节点的键值小于该节点的键值，右边的子节点的键值大于该节点的键值。与其他的二叉排序树不一样的是：对于每一个节点，都含有一个权重值，该值是该节点被搜索到的概率。对于每一个查询，OBST都是按照该节点的权重值来进行查询的，因此OBST中的节点概率是必需的。

OBST节点概率的计算方法

在构建OBST时，需要计算每个节点的概率，即每个键值被查询到的概率。一般是基于历史数据来进行的。如果历史数据不可得，就可以用其他的方法来近似计算。

假设有 $n$ 个查询，并已知各个查询被搜索到的概率为 $p_1, p_2, …,p_n$，则每个查询在OBST 中的概率为 $q_i = \sum_{j=1}^{i}p_j$。这个概率式递归地从下往上计算得到。当搜索表中所有的查询都被计算完毕后，就可以确定对应的权重。

OBST 的构建方法

OBST的构建是一种动态规划的过程，首先确定 OBST 中键值的序列，然后用概率值来构建 OBST。设 OBST $($i, $j)$ 是 p($i$ ~ $j$) 中最佳二叉排序树，其成本为 c($i$， $j$), 则 OBST的最终成本产生于从 i 到 j 内任意节点产生成为根节点的成本之和。

对于 i ($i ≤ k ≤ j$)，在OBST($i$， $j$)中，节点 $k$ 有可能成为树根，故其左右子树为 OBST($i$， $k-1$)和OBST($k+1$， $j$)，其成本为：$w_{i,j} + c_{i,k-1} + c_{k+1,j}$。由此，可以得到递归式：

$c_{i,j} =

\begin{cases}

q_i+p_i+c_{i,i-1}, & j=i-1\\

\min\limits_{i \le k\le j}[k, j] + \min\limits_{1 \le k\le j}[i, k-1] + w_{i,j}, & i \le j

\end{cases}

$

其中 $w_{i,j}$ 为 $p_i$ 到 $p_j$ 的总权重值，也就是查询概率的总和。

OBST的查询效率

OBST的最优查询效率取决于构建该树的策略。OBST使用查找树法查询时，可以得到最佳查询效率。OBST 的内部节点数比叶结点数少1。在理想情况下，OBST 按照概率排列构建。这些概率反映了查询出现的频率，因此 OBST 能够使平均查询次数最少。