計算器科學中， 一個最佳二叉搜尋樹（BST），有時也被叫做重量平衡二叉樹， 是有可能在已知的一串序列中得到最短搜尋時間的一棵二叉搜尋樹（或期望的搜尋時間）。 最最佳化二叉搜尋樹可分為兩種：靜態的和動態的。
基本介紹
- 中文名：最佳化二元搜尋樹
- 外文名：Optimal binary search tree
簡介,樹旋轉,期望值,
簡介
計算器科學中，一個最佳二叉搜尋樹（BST），有時也被叫做重量平衡二叉樹，是有可能在已知的一串序列中得到最短搜尋時間的一棵二叉搜尋樹（或期望的搜尋時間）。最最佳化二叉搜尋樹可分為兩種：靜態的和動態的。
靜態的最最佳化問題中，在完全被創建好之前，這棵樹是不能被修改的。在這狀況中，在這棵樹中的每個節點都存在特定的設計，這些設計是依照每個節點被訪問的機率去設計出會得到最短的搜尋時間。不同的算法能依照每筆數據所給的訪問機率去創建或逼近地做出一個靜態的最最佳化樹。
動態的最最佳化問題中，這棵樹可以在任何時間被修改，是允許運行樹旋轉的。這棵樹有一個從樹的根開始的指針，他可以借著移動並使用他去修改一棵樹。在這狀況里，一定會有一連串序列是有著最小的花費，使得這個指針要去走訪整棵樹去找出這個序列。伸展樹被推測和動態最最佳化樹在任何的情況下都有一個常量比率存在，雖然這還沒有被證明出來。
