-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathOptimalBST.java
More file actions
88 lines (82 loc) · 1.48 KB
/
OptimalBST.java
File metadata and controls
88 lines (82 loc) · 1.48 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package chapter15_DynamicProgramming;
/**
* 最优搜索树
* @author Arthur
*
*/
public class OptimalBST
{
public Result optimalBST(double[]p,double[]q,int n)
{
double[][] e=new double[n+2][n+1];//保存子树期望搜索代价
double[][] w=new double[n+2][n+1];//保存子树成为某节点子树时期望搜索代价的增加值
int[][] root=new int[n+1][n+1];//保存关键字k[i]到k[j]子树的根
for (int i = 1; i <= n+1; i++)//初始化
{
e[i][i-1]=q[i-1];
w[i][i-1]=q[i-1];
}
for (int l = 1; l <= n; l++)//计算1<=i<=j<=n所有的e[i][j]和w[i][j]
{
for (int i = 1; i <= n-l+1; i++)
{
int j=i+l-1;
e[i][j]=Double.MAX_VALUE;
w[i][j]=w[i][j-1]+p[j]+q[j];
double t;
for (int r = i; r <=j; r++)//尝试下标r
{
t=e[i][r-1]+e[r+1][j]+w[i][j];
if (t<e[i][j])
{
e[i][j]=t;
root[i][j]=r;
}
}
}
}
Result result=new Result(root, e, w);
return result;
}
}
class Result
{
private int[][] root;
private double[][] e;
private double[][] w;
public Result()
{
super();
}
public Result(int[][] root, double[][] e ,double[][] w)
{
super();
this.root = root;
this.e = e;
this.w = w;
}
public double[][] getW()
{
return w;
}
public void setW(double[][] w)
{
this.w = w;
}
public int[][] getRoot()
{
return root;
}
public void setRoot(int[][] root)
{
this.root = root;
}
public double[][] getE()
{
return e;
}
public void setE(double[][] e)
{
this.e = e;
}
}