Debug客栈
做一个爱分享的程序猿
Debug客栈
数据结构 静态树表查找算法

算法思想

在使用查找表中有n个关键字,表中的每个关键字被查找的概率都是1/n。在等概率的情况下,使用折半查找算法最优。

然而在某些情况下,查找表中的个关键字被查找的概率都是不同的。例如在UI设计师设计图片的时候,不同的设计师和不同的项目经理需求不同,有些项目经理喜欢暖色调,那么暖色调就会应用的多一些,有的项目经理比较喜欢冷色调,之后你的设计采用冷色调的概率也是比较大的。

在查找表中的关键字不同的情况下,对应于折半查找算法,按照上面的情况并不是最优的查找算法。

静态最优查找二叉树 若在考虑查找成功的情况下,描述查找过程的判定树其带权路径之和(用PH表示)最小时,查找性能最优。

算法思想例子

在查找表中各关键字查找概率不相同的情况下,对于使用折半查找算法,按照之前的方式进行,其查找的效率并不一定是最优的。例如,某查找表中有 5 个关键字,各关键字被查找到的概率分别为:0.1,0.2,0.1,0.4,0.2(全部关键字被查找概率和为 1 ),则根据之前介绍的折半查找算法,建立相应的判定树为(树中各关键字用概率表示):

https://www.debuginn.cn/wp-content/uploads/2019/02/002-9.png

折半查找查找成功的平均查找长度计算方式:

ASL = 判定树中的各节点的查找概率 * 所在层次

相对的平均查找长度为:

ASL=0.41 + 0.22 + 0.22 + 0.13 + 0.1*3=1.8

带权路径之和的计算公式:PH = 所有结点所在的层次数 * 每个结点对应的概率值。

但是由于构造最优查找树花费的时间代价较高,而且有一种构造方式创建的判定树的查找性能同最优查找树仅差 1% – 2%,称这种极度接近于最优查找树的二叉树为次优查找树。

次优查找树的构建方法

构建二叉树方式

首先取出查找表中每个关键字及其对应的权值,采用如下公式计算出每个关键字对应的一个值:

https://www.debuginn.cn/wp-content/uploads/2019/02/003-8.png

其中 wj 表示每个关键字的权值(被查找到的概率),h 表示关键字的个数。

表中有多少关键字,就会有多少个 △Pi ,取其中最小的做为次优查找树的根结点,然后将表中关键字从第 i 个关键字的位置分成两部分,分别作为该根结点的左子树和右子树。同理,左子树和右子树也这么处理,直到最后构成次优查找树完成。

算法实现

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define LIST_INIT_SIZE 100 //存储空间的初始分配量

typedef int Status;
typedef char KeyType;
typedef char TElemType;
typedef struct
{
    KeyType key;
    int weight;
}ElemType;
typedef struct
{
    ElemType *elem; //unit elem[0] keep NULL
    int length;   //length of table
}SSTable;

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode <em>lchild,</em>rchild;  //左孩子右孩子指针
}BiTNode,<em>BiTree,</em>Position;

typedef BiTree SOSTree;  //次优查找树采用二叉链表的存储结构
/*******************************声明部分****************************************/
Status InitTable(SSTable <em>L);
Status CreateTalbe(SSTable *L);
void SecondOpiamal(BiTree *T,ElemType R[],int sw[],int low,int high);
//递归构造次优查找树T
Status CreateSOSTree(SOSTree *T,SSTable ST);
//由有序表ST构造一棵次优查找树T
Status FindSW(int sw[],SSTable ST);
//构造有序表ST的累计权值表sw
Status Visit(ElemType e);
Status PreOrderTraverse(BiTree T,Status(</em>Visit)(ElemType e));
/*******************************函数部分****************************************/
Status InitTable(SSTable <em>L)
{
    (</em>L).elem = (ElemType <em>)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(!(</em>L).elem)
        exit(OVERFLOW);
    (*L).length = 0;
    return OK;
}

Status CreateTalbe(SSTable <em>L)
{
    int i;
 /</em>   printf("请输入顺序表的长度:");
    scanf("%d",&L->length);
    for(i = 1;i<=L->length;i++){
        printf("请输入第 %d 个元素的值:",i);
        scanf("%s",&L->elem[i].key);
        printf("请输入第 %d 个元素的权:",i);
        scanf("%d",&L->elem[i].weight);
    }*/
    L->length = 9;
    L->elem[1].key = 'A';
    L->elem[2].key = 'B';
    L->elem[3].key = 'C';
    L->elem[4].key = 'D';
    L->elem[5].key = 'E';
    L->elem[6].key = 'F';
    L->elem[7].key = 'G';
    L->elem[8].key = 'H';
    L->elem[9].key = 'I';

<pre class="prism-highlight line-numbers" data-start="1"><code class="language-null">L->elem[1].weight = 1;
L->elem[2].weight = 1;
L->elem[3].weight = 2;
L->elem[4].weight = 5;
L->elem[5].weight = 3;
L->elem[6].weight = 4;
L->elem[7].weight = 4;
L->elem[8].weight = 3;
L->elem[9].weight = 5;

return OK;
</code></pre>

}

void SecondOpiamal(BiTree *T,ElemType R[],int sw[],int low,int high)
{
    int i,j,min,dw;

<pre class="prism-highlight line-numbers" data-start="1"><code class="language-null">i = low;
min = abs(sw[high] - sw[low]);
dw = sw[high]+sw[low-1];
for(j = low+1;j<=high;j++){
    if( abs(dw-sw[j]-sw[j-1]) < min){
        i = j;
        min = abs(dw-sw[j]-sw[j-1]);
    }
}//for
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = R[i];  //生成结点
if(i == low)  //左子树空
    (*T)->lchild = NULL;
else
    SecondOpiamal(&(*T)->lchild,R,sw,low,i-1);  //构造左子树
if(i == high)
    (*T)->rchild = NULL;
else
    SecondOpiamal(&(*T)->rchild,R,sw,i+1,high);
</code></pre>

}

Status CreateSOSTree(SOSTree *T,SSTable ST)
{
    int sw[ST.length+1];
    if(ST.length == 0)
        *T = NULL;
    else{
        FindSW(sw,ST);
        SecondOpiamal(T,ST.elem,sw,1,ST.length);
    }
    return OK;
}

Status FindSW(int sw[],SSTable ST)
{
    int sum,i;
    sw[0] = 0;
    sum = 0;
    for(i = 1;i<=ST.length;i++){
        sum += ST.elem[i].weight;
        sw[i] = sum;
    }
    printf("sw中的元素为:\n");
    for(i = 0;i<=ST.length;i++)
        printf("%d  ",sw[i]);
    printf("\n");
    return OK;
}

Status Visit(ElemType e)
{
    printf("%c  ",e);
    return OK;
}

Status PreOrderTraverse(BiTree T,Status(*Visit)(ElemType e))  //递归
{
    if(T){
        if(Visit(T->data))
            if(PreOrderTraverse(T->lchild,Visit))
                if(PreOrderTraverse(T->rchild,Visit))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}
/*******************************主函数部分**************************************/
int main()
{
    SSTable L;
    SOSTree T;
    InitTable(&L);
    CreateTalbe(&L);
    CreateSOSTree(&T,L);
    printf("先序遍历次优二叉树:\n");
    PreOrderTraverse(T,Visit);
    return 0;
}

时间复杂度

由于使用次优查找树和最优查找树的性能差距很小,构造次优查找树的算法的时间复杂度为 O(nlogn),因此可以使用次优查找树表示概率不等的查找表对应的静态查找表(又称为静态树表)。

完整实例演示

例如,一含有 9 个关键字的查找表及其相应权值如下表所示:

https://www.debuginn.cn/wp-content/uploads/2019/02/001-10.png

则构建次优查找树的过程如下:

首先求出查找表中所有的 △P 的值,找出整棵查找表的根结点:

https://www.debuginn.cn/wp-content/uploads/2019/02/004-6.png

例如,关键字 F 的 △P 的计算方式为:从 G 到 I 的权值和 – 从 A 到 E 的权值和 = 4+3+5-1-1-2-5-3 = 0。

通过上图左侧表格得知,根结点为 F,以 F 为分界线,左侧子表为 F 结点的左子树,右侧子表为 F 结点的右子树(如上图右侧所示),继续查找左右子树的根结点:

https://www.debuginn.cn/wp-content/uploads/2019/02/005-5.png

通过重新分别计算左右两查找子表的 △P 的值,得知左子树的根结点为 D,右子树的根结点为 H (如上图右侧所示),以两结点为分界线,继续判断两根结点的左右子树:

https://www.debuginn.cn/wp-content/uploads/2019/02/006-4.png

通过计算,构建的次优查找树如上图右侧二叉树所示。

后边还有一步,判断关键字 A 和 C 在树中的位置,最后一步两个关键字的权值为 0 ,分别作为结点 B 的左孩子和右孩子,这里不再用图表示。

注意:在建立次优查找树的过程中,由于只根据的各关键字的 P 的值进行构建,没有考虑单个关键字的相应权值的大小,有时会出现根结点的权值比孩子结点的权值还小,此时就需要适当调整两者的位置。

总结

在解决静态树表查找时,使用次优查找树的表示概率不等的查找表对应的静态查找表(又称静态树表)。

感谢

本贝壳编写借鉴了一些经验,表示感谢。
静态树表查找算法及C语言实现 严长生
数据结构 – 算法9.3-9.4 静态树表-构造次优查找树
最优二叉查找树详解(算法导论学习笔记)

赞赏
本文链接:https://www.debuginn.cn/218.html
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可,转载请保留此文章链接
相关链接: Debug客栈  |  Debug客栈引导页  |  加入交流群  |  赞助本站  |  博主微博  |  博主推特  |  音乐下载器
社会主义核心价值观: 富强、民主、文明、和谐、自由、平等、公正、法治、爱国、敬业、诚信、友善

发表评论

textsms
account_circle
email

Debug客栈

数据结构 静态树表查找算法
算法思想 在使用查找表中有n个关键字,表中的每个关键字被查找的概率都是1/n。在等概率的情况下,使用折半查找算法最优。 然而在某些情况下,查找表中的个关键字被查找的概率都是…
扫描二维码继续阅读
2017-11-30