算法导论15.5最优二叉查找树实现(Java语言）

不念不忘少年蓝@ 2022-04-21 15:54 155阅读 0赞

这两天在看算法导论中的最优二叉查找树，关于最优二叉查找树的动态规划实现原理大家可以参考算法导论第15章第5小节。

我把自己用Java语言实现的最优二叉查找树贴出来供大家参考一下。

package homework.part5.work1;
    
    import java.util.Scanner;
    
    public class OptimalBST {
    
    	private double[] p;
    	private double[] q;
    	private int n;
    	
    	private double[][] e;
    	private double[][] w;
    	private int[][] root;
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		OptimalBST sample=new OptimalBST();
    		sample.getInputInfo();
    		sample.optimalBST();
    		sample.constructOptimalBST(sample.root, 1, sample.n);
    		
    	}
    	
    	public void getInputInfo()
    	{
    		System.out.println("输入关键字的个数");
    		Scanner in=new Scanner(System.in);
    		this.n=in.nextInt();
    		p=new double[n+1];
    		q=new double[n+1];
    		System.out.println("依次输入"+this.n+"个关键字的概率p");
    		for(int i=0;i<n;i++)
    		{
    			p[i+1]=in.nextDouble();
    		}
    		System.out.println("依次输入"+(this.n+1)+"个非关键字的概率q");
    		for(int i=0;i<=n;i++)
    		{
    			q[i]=in.nextDouble();
    		}
    		
    	}
    	
    	public void optimalBST()
    	{
    		e=new double[n+2][n+1];
    		w=new double[n+2][n+1];
    		root=new int[n+1][n+1];
    		
    		for(int i=1;i<n+2;i++)
    		{
    			e[i][i-1]=q[i-1];
    			w[i][i-1]=q[i-1];
    		}
    		
    		for(int l=1;l<=n;l++)
    		{
    			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];
    				for(int r=i;r<=j;r++)
    				{
    					double 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;
    					}
    				}
    			}
    		}
    		
    	}
    	
    	public void constructOptimalBST(int[][] root,int i,int j)
    	{
    		int r=root[i][j];
    		if(i==1&&j==this.n)
    		{
    			System.out.println("k"+r+"是根");
    		}
    		if(r-1<i)
    		{
    			System.out.println("d"+(r-1)+" 是 k"+r+"的左子树");
    		}else
    		{
    			System.out.println("k"+root[i][r-1]+" 是 k"+r+"的左子树");
    			constructOptimalBST(root,i,r-1);
    		}
    		
    		if(j<r+1)
    		{
    			System.out.println("d"+j+" 是 k"+r+"的右子树");
    		}else
    		{
    			System.out.println("k"+root[r+1][j]+" 是 k"+r+"的右子树");
    			constructOptimalBST(root,r+1,j);
    		}
    	}
    	
    	
    }

下面我使用书本上的例子，测试一下上面的程序，测试的结果如下所示：

输入关键字的个数
    5
    依次输入5个关键字的概率p
    0.15 0.10 0.05 0.10 0.20
    依次输入6个非关键字的概率q
    0.05 0.10 0.05 0.05 0.05 0.10
    k2是根
    k1 是 k2的左子树
    d0 是 k1的左子树
    d1 是 k1的右子树
    k5 是 k2的右子树
    k4 是 k5的左子树
    k3 是 k4的左子树
    d2 是 k3的左子树
    d3 是 k3的右子树
    d4 是 k4的右子树
    d5 是 k5的右子树

从上面的运行结果来看，符合书本上的最优二叉查找树，如图15-7(b)。

下面我们使用上面的程序来做一下课后习题15.5-2，运行的结果如下所示：

输入关键字的个数
    7
    依次输入7个关键字的概率p
    0.04 0.06 0.08 0.02 0.10 0.12 0.14
    依次输入8个非关键字的概率q
    0.06 0.06 0.06 0.06 0.05 0.05 0.05 0.05
    k5是根
    k2 是 k5的左子树
    k1 是 k2的左子树
    d0 是 k1的左子树
    d1 是 k1的右子树
    k3 是 k2的右子树
    d2 是 k3的左子树
    k4 是 k3的右子树
    d3 是 k4的左子树
    d4 是 k4的右子树
    k7 是 k5的右子树
    k6 是 k7的左子树
    d5 是 k6的左子树
    d6 是 k6的右子树
    d7 是 k7的右子树

期望搜索代价为：3.12  
最优二叉查找树结构图如下：

![1356876905_1790.png][]

[1356876905_1790.png]: https://img-my.csdn.net/uploads/201212/30/1356876905_1790.png