一、什么是優異二分搜索樹（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)是帶有結構特性的數據元素的集合，它研究的是數據的邏輯結構和數據的物理結構以及它們之間的相互關系，并對這種結構定義相適應的運算，設計出相應的算法，并確保經過這些運算以后所得到的新結構仍保持原來的結構類型。簡而言之，數據結構是相互之間存在一種或多種特定關系的數據元素的集合，即帶“結構”的數據元素的集合?！敖Y構”就是指數據元素之間存在的關系，分為邏輯結構和存儲結構。

數據的邏輯結構和物理結構是數據結構的兩個密切相關的方面，同一邏輯結構可以對應不同的存儲結構。算法的設計取決于數據的邏輯結構，而算法的實現依賴于指定的存儲結構。