什么是优异二分搜索树（MBST）?

一、什么是优异二分搜索树（MBST）

优异二分搜索树（Most Optimal Binary Search Tree，MBST）是一种用于在有序数据集合中进行高效搜索的数据结构。MBST具有最小的平均搜索成本，因此被广泛应用于压缩领域，特别是在编码和解码算法中。

MBST是一种特殊的二叉搜索树，其在搜索时具有最小的平均搜索成本。在二分搜索树中，树中的每个节点都包含一个关键字，并且满足以下性质：

左子树中的所有关键字小于根节点的关键字。右子树中的所有关键字大于根节点的关键字。

MBST通过优化树的结构，使得在搜索时可以尽量减小搜索的平均成本。这种优化是通过在构建树时选择合适的节点作为根节点来实现的，以使得树的深度最小化。因此，MBST可以在有序数据集合中以较快的速度找到目标关键字，从而提高搜索效率。

构建MBST的一种常用方法是动态规划。该方法通过自底向上的方式构建树，从最小子问题开始，逐步扩展到整个问题的解。

具体步骤如下：

定义一个二维数组dp[i][j]，其中i表示子树中的名列前茅个关键字的索引，j表示子树中的最后一个关键字的索引。dp[i][j]表示在从i到j这个关键字范围内构建的子树中，达到最小平均搜索成本的树的成本。初始化dp[i][i]，即子树中只有一个关键字时，成本为关键字的概率。计算dp[i][j]，其中i<=j。对于dp[i][j]，可以通过遍历子树中的所有可能的根节点，计算在以该根节点为根的树中的平均搜索成本，然后选择最小的成本作为dp[i][j]的值。通过不断扩展子树的规模，直到构建整棵树，即dp[0][n-1]，其中n表示关键字的总数。此时，dp[0][n-1]即为MBST的最小平均搜索成本。

延伸阅读1：什么是数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。