前面給出了二分檢索樹的定義，下圖給出了關于保留字的一個子集的兩棵二分檢索樹。
為了确定辨別符x是否在一棵二分檢索樹中出現，将x先與根比較，如果X比根中辨別符小，則檢索在左子樹中繼續；如果x等于根中辨別符，則檢索成功地終止；否則檢索在右子樹中繼續下去。上述步驟可以形式化為過程Search。
已知一個固定的辨別符集合，希望産生一種構造二分檢索樹的方法。可以預料，同一個辨別符集合有不同的二分檢索樹，而不同的二分檢索樹有不同的性能特征。
下面說說不成功檢索的含義：為了得到二分檢索樹的成本函數，在這棵檢索樹的每一棵空子樹的位置上加上一個虛構的結點，即外部結點，它們在圖4.2中畫成方框。所有其它結點是内部結點。如果一棵二分檢索樹表示n個辨別符，那麼正好有n個内部結點和n+1個外部結點。每個内部結點代表一次成功檢索可能終止的位置。每個外部結點表示一次不成功檢索可能終止的位置。
二分檢索樹的預期成本可用公式表示如下：
ΣP(i)*level(ai) + ΣQ(i)*(level(Ei)-l)
1≤i≤n 0≤i≤n
定義辨別符集(a1,a2,…,an)的最優二分檢索樹是一棵使(4.1)式取最小值的二分檢索樹。
如果T是最優的，則(4.2)式必定是最小值。進而COST(L)對于包含a1,a2,…,ak-1和E0,El,…,Ek-1的所有二分檢索樹必定是最小值，同理COST(R)也必定是最小值。
如果用C(i,j)表示包含ai+1,…,aj和Ei,…,Ej的最優二分檢索樹的成本，那麼要讓T是最優的，就必須有:
COST(L) = C(0,k-1)和COST(R) = C(k,n)
而且應該選擇k使得 P(k) + C(0,k-1) + C(k,n) + w(0,k-1) + w(k,n) 取最小值。
是以，關于C(0,n)有
C(0,n) = min {c(0,k-1) + C(k,n) + P(k) + w(0,k-1) + w(k,n)}
0<k≤n
将(4.3)一般化，對任何C(i,j)則有
C(i,j) = min {C(i,k-1) + C(k,j) + P(k) + W(i,k-1) + W(k,i)}
i<k≤j
= min {C(i,k-1) + C(k,j)+W(i,j)}
用下列步驟解(4.4)式可得C(0,n)。
首先計算所有使得j-i=1的C(i,j)(注意C(i,i)=0且W(i,i)=Q(i)，0≤i≤n)；
接着計算所有使得j-i=2的C(i,j)；
然後計算j-i=3的所有C(i,j)，等等。
如果在這計算期間，記下每棵Tij樹的根R(i,j)，那麼最優二分檢索樹就可以由
這些R(i,j)構造出來。
需要指出的是，R(i,j)是使(4.4)式取最小值的k值。
下面舉個例子：找最小成本二分檢索樹