最佳化二元搜尋樹

計算機科學中， 一個最佳化二元搜尋樹（Optimal BST），有時也被叫做重量平衡二元樹， 是有可能在已知的一串序列中得到最短搜尋時間的一棵二元搜尋樹（或期望的搜尋時間）。 最佳化二元搜尋樹可分為兩種：靜態的和動態的。

靜態的最佳化問題中，在完全被創建好之前，這棵樹是不能被修改的。在這狀況中，在這棵樹中的每個節點都存在特定的設計，這些設計是依照每個節點被存取的機率去設計出會得到最短的搜尋時間。不同的演算法能依照每筆資料所給的存取機率去創建或逼近地做出一個靜態的最佳化樹。

動態的最佳化問題中，這棵樹可以在任何時間被修改，是允許執行樹旋轉的。 這棵樹有一個從樹的根開始的指標，他可以藉著移動並使用他去修改一棵樹。在這狀況裡，一定會有一連串序列是有著最小的花費，使得這個指標要去走訪整棵樹去找出這個序列。 伸展樹被推測和動態最佳化樹在任何的情況下都有一個常數比率存在，雖然這還沒有被證明出來。