最优二叉搜索树
0020算法笔记——【动态规划】最优二叉搜索树问题
标签: 最优二叉搜索树算法笔记最小平均路长四边形不等式动态规划
2013-03-20 10:37 10325人阅读 评论(4) 收藏 举报 本文章已收录于: 算法与数据结构知识库
分类:
算法(49)
版权声明:本文为博主原创文章,未经博主允许不得转载。
1、问题描速:
设 S={x1, x2, ···, xn} 是一个有序集合,且x1, x2, ···, xn表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素,而且具有性质:存储于每个顶点中的元素x 大于其左子树中任一个顶点中存储的元素,小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如(xi, xi+1) 的开区间。在表示S的二叉搜索树中搜索一个元素x,返回的结果有两种情形:
(1) 在二叉树的内部顶点处找到: x = xi
(2) 在二叉树的叶顶点中确定: x∈ (xi , xi+1)
设在情形(1)中找到元素x = xi的概率为bi;在情形(2)中确定x∈ (xi , xi+1)的概率为ai。其中约定x0= -∞ , xn+1= + ∞ ,有
集合{a0,b1,a1,……bn,an}称为集合S的存取概率分布。 最优二叉搜索树:在一个表示S的二叉树T中,设存储元素xi的结点深度为ci;叶结点(xj,xj+1)的结点深度为dj。
注:在检索过程中,每进行一次比较,就进入下面一层,对于成功的检索,比较的次数就是所在的层数加1。对于不成功的检索,被检索的关键码属于那个外部结点代表的可能关键码集合,比较次数就等于此外部结点的层数。对于图的内结点而言,第0层需要比较操作次数为1,第1层需要比较2次,第2层需要3次。
p表示在二叉搜索树T中作一次搜索所需的平均比较次数。P又称为二叉搜索树T的平均路长,在一般情况下,不同的二叉搜索树的平均路长是不同的。对于有序集S及其存取概率分布(a0,b1,a1,……bn,an),在所有表示有序集S的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。
设Pi是对ai检索的概率。设qi是对满足ai
对于有n个关键码的集合,其关键码有n!种不同的排列,可构成的不同二叉搜索树有棵。(n个结点的不同二叉树,卡塔兰数)。如何评价这些二叉搜索树,可以用树的搜索效率来衡量。例如:标识符集{1, 2, 3}={do, if, stop}可能的二分检索树为:
若P1=0.5, P2=0.1, P3=0.05,q0=0.15, q1=0.1, q2=0.05, q3=0.05,求每棵树的平均比较次数(成本)。
Pa(n)=1 × p1 + 2 × p2+3 × p3 + 1×q0 +2×q1+ 3×( q2 + q3 ) =1 × 0.5+ 2 × 0.1+3 ×0.05 + 1×0.05 +2×0.1+ 3×( 0.05 + 0.05 ) =1.5 Pb(n)=1 × p1 + 2 × p3+3 × p2 + 1×q0 +2×q3 + 3×( q1 + q2 ) =1 × 0.5+ 2 × 0.05 + 3 ×0.1 + 1×0.15 +2×0.05+ 3×( 0.1 + 0.05 ) =1.6
Pc(n)=1 × p2 + 2 × (p1 + p3) + 2×(q0 +q1 +q2 + q3 ) =1 × 0.1+ 2 × (0.5 + 0.05) + 2×(0.15 + 0.1 + 0.05 + 0.05) =1.9 Pd(n)=1 × p3 + 2 × p1+3 × p2 + 1 × q3+2 × q0 +3 × (q1+ q2) =1 × 0.05 + 2 × 0.5 + 3 × 0.1 + 1×0.05 + 2 × 0.15 + 3 × (0.1 + 0.05) =2.15 Pe(n)=1 × p3 + 2 × p2+3 × p1 + 1 × q3+2 × q2 +3 × (q0 + q1) =1 × 0.05 + 2 × 0.1+ 3 × 0.5 + 1×0.05 + 2 × 0.15 + 3 × (0.15 + 0.1) =2.85 因此,上例中的最小平均路长为Pa(n)=1.5。
可以得出结论:结点在二叉搜索树中的层次越深,需要比较的次数就越多,因此要构造一棵最小二叉树,一般尽量把搜索概率较高的结点放在较高的层次。 2、最优子结构性质:
假设选择 k为树根,则 1, 2, …, k-1 和a0, a1, …, ak-1 都将位于左子树 L 上,其余结点 (k+1, …, n 和 ak, ak+1, …, an)位于右子树 R 上。设COST(L) 和COST(R) 分别是二分检索树T的左子树和右子树的成本。则检索树T的成本是:P(k)+ COST(L) + COST(R) + …… 。若 T 是最优的,则上式及 COST(L) 和COST(R) 必定都取最小值。 证明:二叉搜索树T 的一棵含有顶点xi , ··· , xj和叶顶点(xi-1 , xi ) , ··· , ( xj , xj+1)的子树可以看作是有序集{ xi , ··· , xj}关于全集为 { xi-1 , xj+1 }的一棵二叉搜索树(T自身可以看作是有序集) 。根据S 的存取分布概率,在子树的顶点处被搜索到的概率是:
。{xi , ··· , xj}的存储概率分布为{ai-1, bi, …,
bj, a
j },其中,ah,bk分别是下面的条件概率:
。
设Tij是有序集{xi , ··· , xj}关于存储概率分布为{ai-1, bi, …, bj, aj}的一棵最优二叉搜索树,其平均路长为pij,Tij的根顶点存储的元素xm,其左子树Tl和右子树Tr的平均路长分别为pl和pr。由于Tl和Tr中顶点深度是它们在Tij中的深度减1,所以得到:
由于Ti是关于集合{xi , ··· , xm-1}的一棵二叉搜索树,故Pl>=Pi,m-1。若Pl>Pi,m-1,则用Ti,m-1替换Tl可得到平均路长比Tij更小的二叉搜索树。这与Tij是最优二叉搜索树矛盾。故Tl是一棵最优二叉搜索树。同理可证Tr也是一棵最优二叉搜索树。因此最优二叉搜索树问题具有最优子结构性质。
3、递推关系:
根据最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下:
bj, a
j },其中,ah,bk分别是下面的条件概率:
。
设Tij是有序集{xi , ··· , xj}关于存储概率分布为{ai-1, bi, …, bj, aj}的一棵最优二叉搜索树,其平均路长为pij,Tij的根顶点存储的元素xm,其左子树Tl和右子树Tr的平均路长分别为pl和pr。由于Tl和Tr中顶点深度是它们在Tij中的深度减1,所以得到:
由于Ti是关于集合{xi , ··· , xm-1}的一棵二叉搜索树,故Pl>=Pi,m-1。若Pl>Pi,m-1,则用Ti,m-1替换Tl可得到平均路长比Tij更小的二叉搜索树。这与Tij是最优二叉搜索树矛盾。故Tl是一棵最优二叉搜索树。同理可证Tr也是一棵最优二叉搜索树。因此最优二叉搜索树问题具有最优子结构性质。
3、递推关系:
根据最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下:
初始时:
记 wi,j pi,j为m(i,j) ,则m(1,n)=w1,n p1,n=p1,n为所求的最优值。计算m(i,j)的递归式为:
4、求解过程:
1)没有内部节点时,构造T[1][0],T[2][1],T[3][2]……,T[n+1][n]
2)构造只有1个内部结点的最优二叉搜索树T[1][1],T[2][2]…, T[n][n],可以求得m[i][i] 同时可以用一个数组存做根结点元素为:s[1][1]=1, s[2][2]=2…s[n][n]=n
3)构造具有2个、3个、……、n个内部结点的最优二叉搜索树。 ……
r (起止下标的差)
0 T[1][1], T[2][2] , …, T[n][n],
1 T[1][2], T[2][3], …,T[n-1][n],
2 T[1][3], T[2][4], …,T[n-2][n],
……
r T[1][r+1], T[2][r+2], …,T[i][i+r],…,T[n-r][n]
……
n-1 T[1][n]
具体代码如下:
[cpp] view plain copy 1. //3d11-1 最优二叉搜索树 动态规划
2. #include "stdafx.h"
3. #include
4. using namespace std;
5.
6. const int N = 3;
7.
8. void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,double **w);
9. void Traceback(int n,int i,int j,int **s,int f,char ch);
10.
11. int main()
12. {
13. double a[] = {0.15,0.1,0.05,0.05};
14. double b[] = {0.00,0.5,0.1,0.05};
15.
16. cout
17. for(int i=0; i
18. {
19. cout20. }
21.
22. double **m = new double *[N+2];
23. int **s = new int *[N+2];
24. double **w =new double *[N+2];
25.
26. for(int i=0;i
27. {
28. m[i] = new double[N+2];
29. s[i] = new int[N+2];
30. w[i] = new double[N+2];
31. }
32.
33. OptimalBinarySearchTree(a,b,N,m,s,w);
34. cout
35. cout
36. Traceback(N,1,N,s,0,'0');
37.
38. for(int i=0;i
39. {
40. delete m[i];
41. delete s[i];
42. delete w[i];
43. }
44. delete[] m;
45. delete[] s;
46. delete[] w;
47. return 0;
48. }
49.
50. void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,
double **w)
51. {
52. //初始化构造无内部节点的情况
53. for(int i=0; i
54. {
55. w[i+1][i] = a[i];
56. m[i+1][i] = 0;
57. }
58.
59. for(int r=0; r
60. {
61. for(int i=1; i
62. {
63. int j = i+r;//j为终止元素下标
64.
65. //构造T[i][j] 填写w[i][j],m[i][j],s[i][j]
66. //首选i作为根,其左子树为空,右子树为节点
67. w[i][j]=w[i][j-1]+a[j]+b[j];
68. m[i][j]=m[i+1][j];
69. s[i][j]=i;
70.
71. //不选i作为根,设k为其根,则k=i+1,……j
72. //左子树为节点:i,i+1……k-1,右子树为节点:k+1,k+2,……j
73. for(int k=i+1; k
74. {
75. double t = m[i][k-1]+m[k+1][j];
76.
77. if(t
78. {
79. m[i][j]=t;
80. s[i][j]=k;//根节点元素
81. }
82. }
83. m[i][j]+=w[i][j];
84. }
85. }
86. }
87.
88. void Traceback(int n,int i,int j,int **s,int f,char ch)
89. {
90. int k=s[i][j];
91. if(k>0)
92. {
93. if(f==0)
94. {
95. //根
96. cout
97. }
98. else
99. {
100. //子树
101. cout
102. }
103.
104. int t = k-1;
105. if(t>=i && t
106. {
107. //回溯左子树
108. Traceback(n,i,t,s,k,'L');
109. }
110. t=k+1;
111. if(t
112. {
113. //回溯右子树
114. Traceback(n,t,j,s,k,'R');
115. }
116. }
117. }
4、构造最优解:
算法OptimalBinarySearchTree中用s[i][j]保存最优子树T(i,j)的根节点中的元素。当s[i][n]=k时,xk为所求二叉搜索树根节点元素。其左子树为T(1,k-1)。因此,i=s[1][k-1]表示T(1,k-1)的根节点元素为xi。依次类推,容易由s记录的信息在O(n)时间内构造出所求的最优二叉搜索树。 5、复杂度分析与优化: 算法中用到3个数组m,s和w,故所需空间复杂度为O(n^2)。算法的主要计算量在于计算。对于固定的r,它需要的计算时间O(j-i+1)=O(r+1)。因此算法所耗费的总时间为:
形不等式》可以得到:。事实上,由《动态规划加速原理之四边
而此状
态转移方程的时间复杂度为O(n^2)。由此,对算法改进后的代码如下:
[cpp] view plain copy
1. //3d11-1 最优二叉搜索树 动态规划加速原理 四边形不等式
2. #include "stdafx.h"
3. #include
4. using namespace std;
5.
6. const int N = 3;
7.
8. void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,double **w);
9. void Traceback(int n,int i,int j,int **s,int f,char ch);
10.
11. int main()
12. {
13. double a[] = {0.15,0.1,0.05,0.05};
14. double b[] = {0.00,0.5,0.1,0.05};
15.
16. cout
17. for(int i=0; i
18. {
19. cout20. }
21.
22. double **m = new double *[N+2];
23. int **s = new int *[N+2];
24. double **w =new double *[N+2];
25.
26. for(int i=0;i
27. {
28. m[i] = new double[N+2];
29. s[i] = new int[N+2];
30. w[i] = new double[N+2];
31. }
32.
33. OptimalBinarySearchTree(a,b,N,m,s,w);
34. cout
35. cout
36. Traceback(N,1,N,s,0,'0');
37.
38. for(int i=0;i
39. {
40. delete m[i];
41. delete s[i];
42. delete w[i];
43. }
44. delete[] m;
45. delete[] s;
46. delete[] w;
47. return 0;
48. }
49.
50. void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,
double **w)
51. {
52. //初始化构造无内部节点的情况
53. for(int i=0; i
54. {
55. w[i+1][i] = a[i];
56. m[i+1][i] = 0;
57. s[i+1][i] = 0;
58. }
59.
60. for(int r=0; r
61. {
62. for(int i=1; i
63. {
64. int j = i+r;//j为终止元素下标
65. int i1 = s[i][j-1]>i?s[i][j-1]:i;
66. int j1 = s[i+1][j]>i?s[i+1][j]:j;
67.
68. //构造T[i][j] 填写w[i][j],m[i][j],s[i][j]
69. //首选i作为根,其左子树为空,右子树为节点
70. w[i][j]=w[i][j-1]+a[j]+b[j];
71. m[i][j]=m[i][i1-1]+m[i1+1][j];
72. s[i][j]=i1;
73.
74. //不选i作为根,设k为其根,则k=i+1,……j
75. //左子树为节点:i,i+1……k-1,右子树为节点:k+1,k+2,……j
76. for(int k=i1+1; k
77. {
78. double t = m[i][k-1]+m[k+1][j];
79.
80. if(t
81. {
82. m[i][j]=t;
83. s[i][j]=k;//根节点元素
84. }
85. }
86. m[i][j]+=w[i][j];
87. }
88. }
89. }
90.
91. void Traceback(int n,int i,int j,int **s,int f,char ch)
92. {
93. int k=s[i][j];
94. if(k>0)
95. {
96. if(f==0)
97. {
98. //根
99. cout
100. }
101. else
102. {
103. //子树
104. cout
105. }
106.
107. int t = k-1;
108. if(t>=i && t
109. {
110. //回溯左子树
111. Traceback(n,i,t,s,k,'L');
112. }
113. t=k+1;
114. if(t
115. {
116. //回溯右子树
117. Traceback(n,t,j,s,k,'R');
118. }
119. }
120. }
运行结果如图:
【算法学习】最优二叉查找树(动态规划)
标签: 算法c
2012-10-19 11:07 20641人阅读 评论(5) 收藏 举报
本文章已收录于:
算法与数据结构知识库
分类:
数据结构与算法(18)
版权声明:本文为博主原创文章,未经博主允许不得转载。 一、什么是最优二叉查找树
最优二叉查找树: 给定n个互异的关键字组成的序列K=,且关键字有序(k1
图一显示了给定上面的概率分布pi、qi,生成的两个二叉查找树的例子。图二就是在这种情况下一棵最优二叉查找树。
概率分布:
i 0
1 2 3 4 5 pi 0.15 0.10 0.05 0.10 0.20
qi 0.05 0.10 0.05 0.05 0.05 0.10
已知每个关键字以及虚拟键被搜索到的概率,可以计算出一个给定二叉查找树内一次搜索的期望代价。假设一次搜索的实际代价为检查的节点的个数,即所发现的节点的深度加1.计算一次搜索的期望代价等式为:
建立一棵二叉查找树,如果是的上式最小,那么这棵二叉查找树就是最优二叉查找树。
而且有下式成立:
二、最优二叉查找树的最优子结构
最优子结构:
如果一棵最优二叉查找树T有一棵包含关键字ki,..,kj的子树T',那么这可子树T'对于关键字Ki,...,kj和虚拟键di-1,...dj的子问题也必定是最优的。可以应用剪贴法证明。
根据最优子结构,寻找最优解:
给定关键字ki,...,kj,假设kr(i
递归解:
定义e[i,j]为包含关键字ki,...,kj的最优二叉查找树的期望代价,最终要计算的是e[1,n]。
当j = i - 1时,此时子树中只有虚拟键,期望搜索代价为e[i,i - 1] = qi-1.
当j >= i时,需要从ki,...,kj中选择一个根kr,然后分别构造其左子树和右子树。下面需要计算以kr为根的树的期望搜索代价。然后选择导致最小期望搜索代价的kr做根。
现在需要考虑的是,当一棵树成为一个节点的子树时,期望搜索代价怎么变化?子树中每个节点深度都增加1.期望搜索代价增加量为子树中所有概率的总和。
对一棵关键字ki,...,kj的子树,定义其概率总和为:
因此,以kr
为根的子
树的期望搜索代价
为:
而
因此e[i,j]可以进一步写为:
这样推导出最终的递归公式为:
三、代码实现(C++):
[cpp] view plain copy
print?
1. //最优二叉查找树
2.
3. #include
4.
5. using namespace std;
6.
7. const int MaxVal = 9999;
8.
9. const int n = 5;
10. //搜索到根节点和虚拟键的概率
11. double p[n + 1] = {-1,0.15,0.1,0.05,0.1,0.2};
12. double q[n + 1] = {0.05,0.1,0.05,0.05,0.05,0.1};
13.
14. int root[n + 1][n + 1];//记录根节点
15. double w[n + 2][n + 2];//子树概率总和
16. double e[n + 2][n + 2];//子树期望代价
17.
18. void optimalBST(double *p,double *q,int n)
19. {
20. //初始化只包括虚拟键的子树
21. for (int i = 1;i
22. {
23. w[i][i - 1] = q[i - 1];
24. e[i][i - 1] = q[i - 1];
25. }
26.
27. //由下到上,由左到右逐步计算
28. for (int len = 1;len
29. {
30. for (int i = 1;i
31. {
32. int j = i + len - 1;
33. e[i][j] = MaxVal;
34. w[i][j] = w[i][j - 1] + p[j] + q[j];
35. //求取最小代价的子树的根
36. for (int k = i;k
37. {
38. double temp = e[i][k - 1] + e[k + 1][j] + w[i][j];
39. if (temp
40. {
41. e[i][j] = temp;
42. root[i][j] = k;
43. }
44. }
45. }
46. }
47. }
48.
49. //输出最优二叉查找树所有子树的根
50. void printRoot()
51. {
52. cout
53. for (int i = 1;i
54. {
55. for (int j = 1;j
56. {
57. cout
58. }
59. cout
60. }
61. cout
62. }
63.
64. //打印最优二叉查找树的结构
65. //打印出[i,j]子树,它是根r的左子树和右子树
66. void printOptimalBST(int i,int j,int r)
67. {
68. int rootChild = root[i][j];//子树根节点
69. if (rootChild == root[1][n])
70. {
71. //输出整棵树的根
72. cout
73. printOptimalBST(i,rootChild - 1,rootChild);
74. printOptimalBST(rootChild + 1,j,rootChild);
75. return;
76. }
77.
78. if (j
79. {
80. return;
81. }
82. else if (j == i - 1)//遇到虚拟键
83. {
84. if (j
85. {
86. cout
87. }
88. else
89. cout
90. return;
91. }
92. else//遇到内部结点
93. {
94. if (rootChild
95. {
96. cout
"
97. }
98. else
99. cout
"
100. }
101.
102. printOptimalBST(i,rootChild - 1,rootChild);
103. printOptimalBST(rootChild + 1,j,rootChild);
104. }
105.
106. int main()
107. {
108. optimalBST(p,q,n);
109. printRoot();
110. cout
111. printOptimalBST(1,n,-1);
112. }
我们将表e、w以及root旋转45°,便于查看上述程序的计算过程。上述代码核心在于函数optimalBST,其计算顺序是从下到上、从左到右。首先是依据概率数组pi、qi初始化:给最下面的一行赋值。然后是三个for循环:从下到上计算表中每一行的值,可以充分利用前面计算出来的结果。如果每当计算e[i][j]的时候都从头开始计算w[i][j],那么需要O(j-i)步加法,但是将这些值保存在表w[1...n+1][0...n]中,就避免这些复杂的计算。
输出结果: