算法:最优二叉搜索树

《算法:最优二叉搜索树》
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<X<ai+1,0<=i<=n的标识符X检索的概率, (假定a0=--∞且an+1=+ ∞)。



  对于有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, aj },其中,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] 

计算过程:

《算法:最优二叉搜索树》
填表:
《算法:最优二叉搜索树》

源代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 3;

void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,double **w);
void Traceback(int n,int i,int j,int **s,int f,char ch);

int main()
{ 
	double a[] = { 0.15,0.1,0.05,0.05};
	double b[] = { 0.00,0.5,0.1,0.05};

	cout<<"有序集的概率分布为:"<<endl;
	for(int i=0; i<N+1; i++)
	{ 
		cout<<"a"<<i<<"="<<a[i]<<",b"<<i<<"="<<b[i]<<endl;
	}

	double **m = new double *[N+2];
	int **s = new int *[N+2];
	double **w =new double *[N+2];

	for(int i=0; i<N+2; i++)
	{ 
		m[i] = new double[N+2];
		s[i] = new int[N+2];
		w[i] = new double[N+2];
	}

	OptimalBinarySearchTree(a,b,N,m,s,w);
	cout<<"二叉搜索树最小平均路长为:"<<m[1][N]<<endl;
	cout<<"构造的最优二叉树为:"<<endl;
	Traceback(N,1,N,s,0,'0');

	for(int i=0; i<N+2; i++)
	{ 
		delete m[i];
		delete s[i];
		delete w[i];
	}
	delete[] m;
	delete[] s;
	delete[] w;
	return 0;
}

void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,double **w)
{ 
	//初始化构造无内部节点的情况
	for(int i=0; i<=n; i++)
	{ 
		w[i+1][i] = a[i];
		m[i+1][i] = 0;
	}

	for(int r=0; r<n; r++)//r代表起止下标的差
	{ 
		for(int i=1; i<=n-r; i++)//i为起始元素下标
		{ 
			int j = i+r;//j为终止元素下标

			//构造T[i][j] 填写w[i][j],m[i][j],s[i][j]
			//首选i作为根,其左子树为空,右子树为节点
			w[i][j]=w[i][j-1]+a[j]+b[j];
			m[i][j]=m[i+1][j];//m[i][j]=m[i-1][j]+m[i+1][j]; m[i-1][j]=0;
			s[i][j]=i;//记录根节点 

			//不选i作为根,设k为其根,则k=i+1,……j
			//左子树为节点:i,i+1……k-1,右子树为节点:k+1,k+2,……j
			for(int k=i+1; k<=j; k++)
			{ 
				double t = m[i][k-1]+m[k+1][j];

				if(t<m[i][j])
				{ 
					m[i][j]=t;
					s[i][j]=k;//根节点元素
				}
			}
			m[i][j]+=w[i][j];
		}
	}
}

void Traceback(int n,int i,int j,int **s,int f,char ch)
{ 
	int k=s[i][j];
	if(k>0)
	{ 
		if(f==0)
		{ 
			//根
			cout<<"Root:"<<k<<" (i:j):("<<i<<","<<j<<")"<<endl;
		}
		else
		{ 
			//子树
			cout<<ch<<" of "<<f<<":"<<k<<" (i:j):("<<i<<","<<j<<")"<<endl;
		}

		int t = k-1;
		if(t>=i && t<=n)
		{ 
			//回溯左子树
			Traceback(n,i,t,s,k,'L');
		}
		t=k+1;
		if(t<=j)
		{ 
			//回溯右子树
			Traceback(n,t,j,s,k,'R');
		}
	}
}

《算法:最优二叉搜索树》

    原文作者:顾道长生'
    原文地址: https://blog.csdn.net/wl1780852311/article/details/103006232
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞