查找章节总结之二——次优查找树

阳光穿透心脏的1/2处 2022-04-04 09:54 424阅读 0赞

# 查找章节总结之二-静态次优查找树 #

## 1.前言 ##

在[上一篇博客][Link 1]中介绍了,查找章节较为简单的基础部分的东西,同时在计算平均查找长度的时候,我们假定每个点的查找的概率均为相同的,但是实际上,每个点查找的概率可能会出现不相同的情况,再按照前面的方法计算可能效果不是太好.例如我们假设一个有序列表各个查找概率分别为p1=0.1,p2=0.2,p3=0.1,p4=0.4,p5=0.2,那么按照我们之前求出的折半查找的平均查找长度公式,计算可得  
 A S L = 0.1 ∗ 2 + 0.2 ∗ 3 + 0.1 ∗ 1 + 0.4 ∗ 2 + 0.2 ∗ 3 = 2.2 ASL=0.1\*2+0.2\*3+0.1\*1+0.4\*2+0.2\*3=2.2 ASL=0.1∗2\+0.2∗3\+0.1∗1\+0.4∗2\+0.2∗3=2.2  
但是如果我们在查找时,令给定值先于第四个数进行比较,比较不相等的时候才在左子序列或右序列中进行折半查找的话.  
 A S L = 0.1 ∗ 3 + 0.2 ∗ 2 + 0.1 ∗ 3 + 0.4 ∗ 1 + 0.2 ∗ 1 = 1.8 ASL=0.1\*3+0.2\*2+0.1\*3+0.4\*1+0.2\*1=1.8 ASL=0.1∗3\+0.2∗2\+0.1∗3\+0.4∗1\+0.2∗1=1.8  
可见在查找概率不相同的时候我们要采取用别的方法,来进行查找.

## 2.静态最优查找树 ##

P H = ∑ i = 1 n w i h i ; PH=\\sum\_\{i=1\}^nw\_ih\_i; PH=i=1∑nwihi;

式中wi=cpi,称为节点的权,其中pi为查找到该节点的概率,c为一个常数,hi为第i个节点在二叉树上的层次树,我们称PH值最小的二叉树为静态最优二叉树.构造这个静态最优查找树耗费好像比较大,所以书上并没有直接展开讲,有兴趣的同学可以去了解下[最优二叉树详解][Link 2]

## 3.次优查找树 ##

### 3.1介绍 ###

给定一个按关键字有序排列的记录序列,以及他们每个的权值,构建一棵二叉树,使得这个二叉树的PH值,在所有具有同样权值的二叉树中的近似值为最小,这一类的二叉树为最优查找树.

### 3.2构造方法 ###

1.首先我们在记录序列中取第i个记录来构造根节点ri,使得  
 Δ P i = ∣ ∑ j = i + 1 h w j − ∑ j = l i − 1 w j ∣ \\Delta P\_i=|\\sum\_\{j=i+1\}^\{h\}w\_j-\\sum\_\{j=l\}^\{i-1\}w\_j| ΔPi=∣j=i\+1∑hwj−j=l∑i−1wj∣  
(h为节点个数,l为1)取最小值（用来控制左右两边的权值和差值为最小）.然后分别对左序列和右序列进行同样的操作,来完成构造次优生成树.

2.我们假设有一个这样的数组  
 s w i = ∑ j = l i w j sw\_i=\\sum\_\{j=l\}^iw\_j swi=j=l∑iwj  
设wj-1=0和swj-1=0,那么我们可以得到  
 \{ s w i − 1 − s w l − 1 = ∑ j = l i − 1 w j ; s w h − s w i = ∑ j = i + 1 h w j ; \\left\\\{ \\begin\{aligned\} sw\_\{i-1\}-sw\_\{l-1\}=\\sum\_\{j=l\}^\{i-1\}w\_j;\\\\ sw\_h-sw\_i=\\sum\_\{j=i+1\}^hw\_j; \\end\{aligned\} \\right. ⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧swi−1−swl−1=j=l∑i−1wj;swh−swi=j=i\+1∑hwj;

所以  
 Δ P i = ∣ ( s w h + s w l ) − s w i − s w i − 1 ∣ \\Delta P\_i=|(sw\_h+sw\_l)-sw\_i-sw\_\{i-1\}| ΔPi=∣(swh\+swl)−swi−swi−1∣

### 3.3代码 ###

typedef struct node
    {
    	int key;
    	int w;
    }node;
    
    typedef struct tree
    {
    	struct *node lchild;
    	struct *node rchild;
    }tree,*Bittree;
    
    Bittree T;
    int sum_sw(int *sw, list test)
    {
    	sw[0] = 0;
    	for (int i = 1; i <= length; i++)
    	{
    		sw[i] += sw[i - 1] + test.w[i];
    	}
    }
    
    int secondoptimal(Bittree &T, int *W, int *sw, int left, int right) 
    {
    	int i = left;
    	int min = abs(sw[right] - sw[left]);//为min赋初始值，该值为第一位数所表示的PI的值
    	int dw = sw[right] + sw[left-1];//方便下一步的计算
    	for(int j=left+1;j<=right;j++)
    	{
    		if(abs(dw-sw[j]-sw[j-1])<min)
    		{
    			i = j;
    			min = abs(dw - sw[j] - sw[j - 1]);
    		}
    	}
    	T = (Bittree)malloc(sizeof(tree));
    	T->data = W[i];
    	if (i == left)
    		T->lchild = NULL;
    	else
    	{
    		secondOptimal(T->lchild, W, sw, left, i - 1);//建立左子树
    	}
    	if (i == right) 
    	{
    		T->rchild = NULL;
    	}
    	else 
    	{
    		secondOptimal(T->rchild, W, sw, i + 1, right);//建立右子树
    	}
    }

理清楚思路之后还是,代码写出来的难度应该是不大,再跟着书上的例题跑一跑自己的思路,就基本没什么问题了.?

[Link 1]: https://blog.csdn.net/qq_40184139/article/details/85032106
[Link 2]: https://blog.csdn.net/say_c_box/article/details/72909925