什么是優(yōu)異二分搜索樹（MBST）?

一、什么是優(yōu)異二分搜索樹（MBST）

優(yōu)異二分搜索樹（Most Optimal Binary Search Tree，MBST）是一種用于在有序數(shù)據(jù)集合中進行高效搜索的數(shù)據(jù)結(jié)構(gòu)。MBST具有最小的平均搜索成本，因此被廣泛應(yīng)用于壓縮領(lǐng)域，特別是在編碼和解碼算法中。

MBST是一種特殊的二叉搜索樹，其在搜索時具有最小的平均搜索成本。在二分搜索樹中，樹中的每個節(jié)點都包含一個關(guān)鍵字，并且滿足以下性質(zhì)：

左子樹中的所有關(guān)鍵字小于根節(jié)點的關(guān)鍵字。右子樹中的所有關(guān)鍵字大于根節(jié)點的關(guān)鍵字。

MBST通過優(yōu)化樹的結(jié)構(gòu)，使得在搜索時可以盡量減小搜索的平均成本。這種優(yōu)化是通過在構(gòu)建樹時選擇合適的節(jié)點作為根節(jié)點來實現(xiàn)的，以使得樹的深度最小化。因此，MBST可以在有序數(shù)據(jù)集合中以較快的速度找到目標關(guān)鍵字，從而提高搜索效率。

構(gòu)建MBST的一種常用方法是動態(tài)規(guī)劃。該方法通過自底向上的方式構(gòu)建樹，從最小子問題開始，逐步擴展到整個問題的解。

具體步驟如下：

定義一個二維數(shù)組dp[i][j]，其中i表示子樹中的名列前茅個關(guān)鍵字的索引，j表示子樹中的最后一個關(guān)鍵字的索引。dp[i][j]表示在從i到j(luò)這個關(guān)鍵字范圍內(nèi)構(gòu)建的子樹中，達到最小平均搜索成本的樹的成本。初始化dp[i][i]，即子樹中只有一個關(guān)鍵字時，成本為關(guān)鍵字的概率。計算dp[i][j]，其中i<=j。對于dp[i][j]，可以通過遍歷子樹中的所有可能的根節(jié)點，計算在以該根節(jié)點為根的樹中的平均搜索成本，然后選擇最小的成本作為dp[i][j]的值。 通過不斷擴展子樹的規(guī)模，直到構(gòu)建整棵樹，即dp[0][n-1]，其中n表示關(guān)鍵字的總數(shù)。此時，dp[0][n-1]即為MBST的最小平均搜索成本。

延伸閱讀1：什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，并確保經(jīng)過這些運算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型。簡而言之，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合。“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系，分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的兩個密切相關(guān)的方面，同一邏輯結(jié)構(gòu)可以對應(yīng)不同的存儲結(jié)構(gòu)。算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于指定的存儲結(jié)構(gòu)。