判定树 折半查找只适用于有序表，且限于顺序存储结构（对线性链表无法有效的进行折半查找）
斐波那契查找：根据斐波那契序列的特点进行分割，假设开始时表中记录个数比某个斐波那契数小１即
n=fu-1,然后将给定值key和 [fu -1 ].key 进行比较，若想等则查找成功； 若key<[fu-1].key 继续自
elem[1]到elem[fu-1 - 1 ]的子表进行查找，否则继续在自elem[fu-1 + 1]至elem[fu - 1]的子表中进行
查找，后一子表的长度为fu-2 -1。斐波那契查找的平均性能比折半查找好，但最坏情况比折半查找差
静态树表查找
对于查找表的查找概率不等时引入的静态树表查找。
静态最优查找树（static optimal search tree)
近似最优查找树（nearly optimal search tree)
序列（rl,rl + 1, ..., rn)
其中 r1.key < rl+1 . key < .... < rh.key
与每个记录对应的权值
wl,wl+1,...,wh
现构造一颗二叉树，使这棵二叉树的带权内路径长度PH值在所有具有同样的权值的二叉树中
近视为最小，称这类二叉树为次优先查找树（nearly optimal search tree)
void SecondOptimal(BiTrre& T,ElemType R[], float sw[],int low,int high){
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]);
}
T = (BiTree)malloc(sizeof(BiTNode));
T->data = R[i];
if (i==low) T->lchild = NULL;
else SecondOptimal(T->lchild,R,sw,low,i-1);
if(i==high) T->rchild=NULL;
else SecondOptimal(T->rchild,R,sw,i+1,high);
}
typedef BiTree SOSTree;
status CreateSOSTree(SOSTree & T, SSTable ST) {
if(ST.length == 0 ) T=NULL;
else {
FindSW(sw,ST); // 按照由有序表ST中各数据元素的weight域求累计权值表sw.
SecondOptimal(T,ST.elem,sw,1,ST.length);
}
return OK;
}
由于在次优先查找树的过程中,没有考虑单个关键字的相应权值,则有可能出现被选为根的关键字
的权值比与它相邻的关键字的权值小.此时应当适当的调整:选临近的权值较大的关键字作为次优先查找树的根结点.
索引顺序表的查找
分块查找
表有序或者分块有序. 所谓"分块有序" 指的是第二个子表中所有记录的关键字均大于第一个表中的最大关键字.
第三个子表的所有关键字均大于第二个表中的最大关键字,...,依次类推.
结构索引表和块表 每个索引项包括关键字项和指针项.
查找分2部,先查找子快,在子表中顺序查找.
比顺序查找快,不及折半查找.
动态查找表
二叉排序树,平衡二叉树(Binary sort tree)
二叉排序树或者是一颗空树；或者具有下列性质的二叉树：（1）若它的左子树不空，则左子树上
所有节点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有的结点的值均大于
它的根节点的值；（3）它的左右子树也分别为二叉排序树。
BiTree SearchBST(BiTree T, KeyType key)
{
if((!T) || EQ(key,T->data.key)) return (T);
else if LT(key,T->data.key) return (SearchBST(T->lchild,key));
else return (SearchBST(T->rchild,key));
}
二叉排序树的插入/删除
与次优二叉树不同的是二叉排序树是查找过程中动态生成的。
Status SearchBST(BiTree T, KeyType key,BiTree& p)
{
if((!T) || EQ(key,T->data.key)) return (p=T,return TRUE);
else if LT(key,T->data.key) return (SearchBST(T->lchild,key,p));
else return (SearchBST(T->rchild,key,p));
}
Status InsertBST(BiTree & T,ElemType e)
{
if(!SearchBST(T,e.key,NULL,p) {
s = (BiTree)malloc(sizeof(BiTNode));
s->data = e; s->lchild = s->rchild = NULL;
if (!p) T = s;
else if LT(e.key,p->data.key) p->lchild = s;
else p->rchild = s;
return TRUE;
}
else return FALSE;
}
二叉排序树的删除
分三种情况讨论
（1）若*p结点为叶子结点，即PL和PR均为空树，由于删去叶子节点不破坏整个树结构，
则只需修改双亲节点的指针即可。
（2）若*p结点只有左子树PL或只有右子树PR，此时要另PL或PR直接成为其双亲节点的*f的左子树即可。
（3）若*p结点的左子树和右子树均不空。显然，此时不能如上简单处理。有2种做法
一，另*p的左子树为*f的左子树，而*p的右子树为*s的右子树。
二，另*p的直接前驱（或直接后继）代替*p ，然后从二叉排序树中删去它的直接前驱（或直接后继）
Status DeleteBST(BiTree & T, KeyType key) {
if(!T) return FALSE;
else {
if(EQ(key, T->data.key)) {return Delete(T)};
else if(LT(key,T->data.key)) return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);
}
}
Status Delete(BiTree & p) {
if (!p->rchild) {
q = p; p = p->lchild; free(q);
}
else if (!p->lchild) {
q = p; p = p->rchild; free(q);
}
else {
q = p; s = p->lchild;
while(s->rchild) {q = s; s = s->rchild;} //左转，然后向右走到尽头
p->data = s->data; //s指向被删节点的前驱
if(q != p) q->rchild = s->lchild; //重接*q的右子树
else q->lchild = s->lchild; //重接*q的左子树
delete s;
}
reutrn TRUE;
}
本文转自莫水千流博客园博客，原文链接：http://www.cnblogs.com/zhoug2020/p/4220343.html，如需转载请自行联系原作者
