最优二叉查找树

(1）二叉查找树（二分检索树）二叉搜索树

Ｔ是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：

• Ｔ的左子树的所有元素比根结点中的元素小；
• Ｔ的右子树的所有元素比根结点中的元素大；
• Ｔ的左子树和右子树也是二叉搜索树。

(2）最优二叉搜索树

给定一个n个关键字的已排序的序列K=<k 1 ,k 2 ,…,k n >（ 不失一般性，设k 1 <k 2 <…<k n ），对每个关键字k i ，都有一个概率p i 表示其搜索频率。根据k i和p i 构建一个二叉搜索树T，每个k i 对应树中的一个结点。若搜索对象x等于某个k i ，则一定可以在T中找到结点k i ；若x<k 1 或 x>k n 或 k i <x<k i+1 (1≤i<n), 则在T中将搜索失败。为此引入外部结点d 0 ,d 1 ,…,d n ，用来表示不在K中的值，称为伪结点。这里每个d i 代表一个区间， d 0 表示所有小于k 1 的值， d n 表示所有大于k n 的值，对于i=1,2,…,n-1，d i 表示所有在k i 和k i+1 之间的值。 同时每个d i 也有一个概率qi 表示搜索对象x恰好落入区间d i 的频率。

(3)例

设有n=5个关键字的集合，每个k i 的概率p i 和d i 的概率q i 如表所示：其中

基于该集合，两棵可能的二叉搜索树如下所示。
(4)二叉搜索树的期望搜索代价代价等于从根结点开始访问结点的数量。

从根结点开始访问结点的数量等于结点在T中的深度+1； 二叉搜索树T的期望代价记depth T (i)为结点i在T中的深度，则T搜索代价的期望为：
$\begin{array}{rl}\mathrm{E}[\text{ search cost in }T]& =\sum _{i=1}^n\left({\mathrm{depth}}_T\left(k_i\right)+1\right)\cdot p_i+\sum _{i=0}^n\left({\mathrm{depth}}_T\left(d_i\right)+1\right)\cdot q_i\\ & =1+\sum _{i=1}^n{\mathrm{depth}}_T\left(k_i\right)\cdot p_i+\sum _{i=0}^n{\mathrm{depth}}_T\left(d_i\right)\cdot q_i\end{array}$

上面图中(a)的期望搜索代价为2.80。(b)的期望搜索代价为2.75。

最优二叉搜索树的定义对给定的概率集合，期望搜索代价最小的二叉搜索树称为最优二叉搜索树

• (1)最优二叉搜索树的最优子结构：如果一棵 最优二叉搜索树T T有一棵包含关键字k i ,…,k j 的子树T’，则T’必然是包含关键字ki ,…,k j 和伪关键字d i-1 ,…,d j 的子问题的最优解。

• (2)构造最优二叉搜索树利用最优二叉搜索树的最优子结构性来构造最优二叉搜索树。分析：

对给定的关键字k i ,…,k j ，若其最优二叉搜索树的根结点是k r（i≤r≤j），则k r 的左子树中包含关键字k i ,…,k r-1 及伪关键字d i-1,…,d r-1 ，右子树中将含关键字k i+1 ,…,k j 及伪关键字d r ,…,d j 。策略：检查所有可能的根结点k r （i≤r≤j），如果事先分别求出包含关键字k i ,…,k r-1 和关键字k r+1 ,…,k j 的最优二叉搜索子树，则可保证找到原问题的最优解。

• (3)计算过程： 求解包含关键字k i ,…,k j 的最优二叉搜索树，其中，i≥1，j≤n 且 j≥i-1。

定义e[i,j]：为包含关键字k i ,…,k j 的最优二叉搜索树的期望搜索代价。e[1,n]为问题的最终解。

当j≥i时，我们需要从k i ,…,k j 中选择一个根结点k r ，其左子树包含关键字k i ,…,k r-1 且是最优二叉搜索子树，其右子树包含关键字k r+1 ,…,k j 且为最优二叉搜索子树。

• (4)若k r 为包含关键字k i ,…,k j的最优二叉搜索树(树根)，则其期望搜索代价与左、右子树的期望搜索代价e[i,r-1]和e[r+1,j]有如下递推关系：
  $e[i,j]=p_r+(e[i,r-1]+w(i,r-1))+(e[r+1,j]+w(r+1,j))$
  其中，$w(i,j)=w(i,r-1)+p_r+w(r+1,j)$
  所以得出$e[i,j]=e[i,r-1]+e[r+1,j]+w(i,j)$

• (5)有上面的分析，可以得到kr的递推公式

e [ i , j ] = { q i − 1  if  j = i − 1 min ⁡ i ≤ r ≤ j { e [ i , r − 1 ] + e [ r + 1 , j ] + w ( i , j ) }  if  i ≤ j e[i, j]=\left\{\begin{array}{ll}q_{i-1} & \text { if } j=i-1 \\ \min _{i \leq r \leq j}\{e[i, r-1]+e[r+1, j]+w(i, j)\} & \text { if } i \leq j\end{array}\right. e[i,j]={ qi−1​mini≤r≤j​{ e[i,r−1]+e[r+1,j]+w(i,j)}​ if j=i−1 if i≤j​

边界条件：j=i-1，存在e[i, i-1]和e[j+1, j]的边界情况。此时，子树不包含实际的关键字，而只包含伪关键字d i-1 ，其期望搜索代价为：$e[i,i-1]=q_{i-1}$

• (6)构造最优二叉搜索树

定义root[i,j]，保存计算e[i, j]时使e[i, j]取得最小值的r。在求出e[1,n]后，利用root的记录构造出整棵最优二叉搜索树。

• (7)计算最优二叉搜索树的期望搜索代价

e[1..n+1,0..n]：用于记录所有e[i,j]的值。注：e[n+1,n]对应伪关键字d n 的子树；e[1,0]对应伪关键字d 0 的子树。
root[1..n]：用于记录所有最优二叉搜索子树的根结点，包括整棵最优二叉搜索树的根。
w[1..n+1,0..n]：用于子树保存增加的期望搜索代价，

且有$w[i,j]=w[i,j-1]+p_j+q_j$

这样，对于Θ(n 2 )个w[i,j]，每个的计算时间仅为Θ(1)。

上面算法是构造root表的算法

举例说明

(1)给出一组数据

$$\begin{array}{ccccccc}i& 0& 1& 2& 3& 4& 5\\ p_i& & 0.15& 0.10& 0.05& 0.10& 0.20\\ q_i& 0.05& 0.10& 0.05& 0.05& 0.05& 0.10\end{array}$$

(2)根据$w[i,j]=w[i,j-1]+p_j+q_j$求出w表的内容

(3)根据
e [ i , j ] = { q i − 1  if  j = i − 1 min ⁡ i ≤ r ≤ j { e [ i , r − 1 ] + e [ r + 1 , j ] + w ( i , j ) }  if  i ≤ j e[i, j]=\left\{\begin{array}{ll}q_{i-1} & \text { if } j=i-1 \\ \min _{i \leq r \leq j}\{e[i, r-1]+e[r+1, j]+w(i, j)\} & \text { if } i \leq j\end{array}\right. e[i,j]={ qi−1​mini≤r≤j​{ e[i,r−1]+e[r+1,j]+w(i,j)}​ if j=i−1 if i≤j​

求出e表的内容

(4)最后根据上面的算法得出root表的内容

　(5)下面给出C++的最优二叉搜索树的代码实现

  1 #include <iostream>
  2  
  3 using namespace std;
  4  
  5 const int MaxVal = 9999;
  6  
  7 const int n = 5;
  8 //搜索到根节点和虚拟键的概率
  9 double p[n + 1] = {
    -1,0.15,0.1,0.05,0.1,0.2};
 10 double q[n + 1] = {
    0.05,0.1,0.05,0.05,0.05,0.1};
 11  
 12 int root[n + 1][n + 1];//记录根节点
 13 double w[n + 2][n + 2];//子树概率总和
 14 double e[n + 2][n + 2];//子树期望代价
 15  
 16 void optimalBST(double *p,double *q,int n)
 17 {
    
 18     //初始化只包括虚拟键的子树
 19     for (int i = 1;i <= n + 1;++i)
 20     {
    
 21         w[i][i - 1] = q[i - 1];
 22         e[i][i - 1] = q[i - 1];
 23     }
 24  
 25     //由下到上，由左到右逐步计算
 26     for (int len = 1;len <= n;++len)
 27     {
    
 28         for (int i = 1;i <= n - len + 1;++i)
 29         {
    
 30             int j = i + len - 1;
 31             e[i][j] = MaxVal;
 32             w[i][j] = w[i][j - 1] + p[j] + q[j];
 33             //求取最小代价的子树的根
 34             for (int k = i;k <= j;++k)
 35             {
    
 36                 double temp = e[i][k - 1] + e[k + 1][j] + w[i][j];
 37                 if (temp < e[i][j])
 38                 {
    
 39                     e[i][j] = temp;
 40                     root[i][j] = k;
 41                 }
 42             }
 43         }
 44     }
 45 }
 46  
 47 //输出最优二叉查找树所有子树的根
 48 void printRoot()
 49 {
    
 50     cout << "各子树的根：" << endl;
 51     for (int i = 1;i <= n;++i)
 52     {
    
 53         for (int j = 1;j <= n;++j)
 54         {
    
 55             cout << root[i][j] << " ";
 56         }
 57         cout << endl;
 58     }
 59     cout << endl;
 60 }
 61  
 62 //打印最优二叉查找树的结构
 63 //打印出[i,j]子树，它是根r的左子树和右子树
 64 void printOptimalBST(int i,int j,int r)
 65 {
    
 66     int rootChild = root[i][j];//子树根节点
 67     if (rootChild == root[1][n])
 68     {
    
 69         //输出整棵树的根
 70         cout << "k" << rootChild << "是根" << endl;
 71         printOptimalBST(i,rootChild - 1,rootChild);
 72         printOptimalBST(rootChild + 1,j,rootChild);
 73         return;
 74     }
 75  
 76     if (j < i - 1)
 77     {
    
 78         return;
 79     }
 80     else if (j == i - 1)//遇到虚拟键
 81     {
    
 82         if (j < r)
 83         {
    
 84             cout << "d" << j << "是" << "k" << r << "的左孩子" << endl;
 85         }
 86         else
 87             cout << "d" << j << "是" << "k" << r << "的右孩子" << endl;
 88         return;
 89     }
 90     else//遇到内部结点
 91     {
    
 92         if (rootChild < r)
 93         {
    
 94             cout << "k" << rootChild << "是" << "k" << r << "的左孩子" << endl;
 95         }
 96         else
 97             cout << "k" << rootChild << "是" << "k" << r << "的右孩子" << endl;
 98     }
 99  
100     printOptimalBST(i,rootChild - 1,rootChild);
101     printOptimalBST(rootChild + 1,j,rootChild);
102 }
103  
104 int main()
105 {
    
106     optimalBST(p,q,n);
107     printRoot();
108     cout << "最优二叉树结构：" << endl;
109     printOptimalBST(1,n,-1);
110 }

DP实现最优二叉搜索树并打印出树结构

参考自
风沙迷了眼