BST最优二叉检索树(java版本)

这个内容是去年暑假讲的,但是一直没有实现,

其实说白了就是区间dp,求一个序列构成二叉树,中序遍历有序.

核心和其他区间dp一样,枚举中间值.然后枚举出来后再将整个区间的概率累加,因为相当于加深了一层.

JAVA代码,附测试数据

import java.util.Arrays;
import java.util.Scanner;


public class Main {
	/**
	 * 输入p: 访问概率数组； 0,1,....n是排好序的Key值
	 * 输出A=new float[n][n]: 最优时间矩阵
	 * 输出R=new int[n][n]: 根结点矩阵
	 * @param p
	 * @param A
	 * @param R
	 */
	static void optimalBST(double[] p, double[][] A, int[][] R) {
		int n = p.length;
		Arrays.sort(p);
		for (int i = 0; i < n; i++) {
			A[i][i] = p[i];
			R[i][i] = i; // the root is itself
		}
		for (int len = 1; len < n; len++) {
			for (int st = 0; st + len < n; st++) {
				int ed = st + len;
				int root = st;
				double min = Double.MAX_VALUE;
				for (int k = st; k <= ed; k++) {
					double tmp;
					if (k == st)
						tmp = A[k + 1][ed];
					else if (k == ed)
						tmp = A[st][k - 1];
					else
						tmp = A[k + 1][ed] + A[st][k - 1];
					if (min > tmp) {
						min = tmp;
						root = k;
					}
				}
				R[st][ed] = root;
				A[st][ed] = min;
				for (int i = st; i <= ed; i++)
					A[st][ed] += p[i];
			}
		}
	}
	public static void print(int st,int ed,int [][] R){
		if(st==ed) {
			System.out.print(R[st][ed]);
			return;
		}
		System.out.print("(");
		print(st,R[st][ed]-1,R);
		System.out.print(")");
		System.out.print(R[st][ed]);
		System.out.print("(");
		print(R[st][ed]+1,ed,R);
		System.out.print(")");
		
	}
	public static void main(String[] args) {
		
		//Scanner input = new Scanner(System.in);
		double [][] A = new double[5][5];
		int [][] R = new int[5][5];
//		optimalBST1(new double [] {0.15, 0.10,0.05,0.10,0.20},A,R);
//		System.out.println(A[0][4]);
//		print(0,4,R);
		optimalBST(new double [] {0.15, 0.10,0.05,0.10,0.20},A,R);
		System.out.println(A[0][4]);
		print(0,4,R);
	}
}