数据结构查找2静态树表索引顺序表 [复制链接]

对于静态顺序查找表和静态有序查找表，有一个重要前提，即它们的被查找概率是相等的，倘若查找概率不等且已知，则应该考虑重新设计查找结构。

本文介绍的两种静态表，静态树表和顺序索引表，可以通过排列，使得p较大的数据先被查找，这样，相较于顺序查找，可以较好的缩短平均查找长度。

引入性能判断依据PH：

PH=∑wi*hi

hi为第i个结点在二叉树上的层次数

wi为结点的权重

由于构造最优二叉树书上懒得讲

这里记录一个构造次优二叉树（次优查找树），PH在同顶点近似为最小。

B站一up主视频：BV1sJW7xq

构造方法：不断寻找Δpi最小的结点作为根节点结点左、右段分别递归调用狗构造左右子树。Δpi=Σ后面值-Σ前面值

采用存储结构：二叉树

采用设计方法：递归

BiNode*createSOStree(intleft,intright,int*data){if(leftright)returnNULL;//递归出口intposition;BiNode*T=(BiNode*)malloc(sizeof(BiNode));position=Find(left,right,data);//找到处理位置T-data=data[position];//取值T-lchild=createSOStree(left,position-1,data);T-rchild=createSOStree(position+1,right,data);//递归returnT;//当前树建造完成返回}

索引顺序表

又称分块查找，是顺序查找的改良

通过小表保存地址，再到大表中去查找

对于小表，必须要存在可查找的逻辑

对于大表，可通过小表查找到后进行顺序查找

平均查找长度为两表平均之和