《数据结构——C语言描述》第8章：查找

二叉排序树插入新结点的过程 在二叉排序树中插入新结点，要保证插入后仍满足 BST性质。其插入过程是： 1)若二叉排序树T为空，则为待插入的关键字key申请 一个新结点，并令其为根； 2)若二叉排序树T不为空，则将key和根的关键字比较： (a)若二者相等，则说明树中已有此关键字key，无 须插入。 (b)若key<T→key，则将key插入根的左子树中。 (c)若key>T→key，则将它插入根的右子树中。



二叉排序树的特点 （1） 二叉排序树中任一结点x，其 左(右)子树中任一结点y(若存在)的 关键字必小(大)于x的关键字。 （2） 二叉排序树中，各结点关键 字是惟一的。 （3） 按中序遍历该树所得到的中 序序列是一个递增有序序列。
二叉排序树的存储结构



int KeyType； typedef struct node { KeyType key； InfoType otherinfo； struct node *lchild，*rchild； } BSTNode； typedef BSTNode *BSTree；


顺序查找的优点 算法简单，且对表的结构无任何要求，无论是用 向量还是用链表来存放结点，也无论结点之间是 否按关键字有序，它都同样适用。 顺序查找的缺点 查找效率低。
二分查找


二分查找又称折半查找，它是一种效率较高的查找方 法。 二分查找要求：线性表是有序表，即表中结点按关键 字有序，并且要用向量作为表的存储结构。不妨设有 序表是递增有序的。
8.2线性表的查找
顺序查找(Sequential Search) 基本思想是：从表的一端开始，顺序扫描线性表， 依次将扫描到的结点关键字和给定值K相比较。若当 前扫描到的结点关键字与K相等，则查找成功；若扫 描结束后，仍未找到关键字等于K的结点，则查找失 败。
基于顺序结构的顺序查找算法
类型说明 typedef struct{ KeyType key； /* KeyType由用户定义 */ InfoType otherinfo； /* 此类型依赖于应用 */ }NodeType； typedef NodeType Seqlist[n+1]； /*多出0号单 元用作监视哨*/
第八章
查找
基本概念 线性表的查找 树表的查找 散列(Hash)技术
8.1查找的基本概念
查找（Searching）的定义是：给定一个关键 字值K，在含有n个结点的表中找出关键字等于 给定值K的结点。若找到，则查找成功，返回 该结点的信息或该结点在表中的位置；否则查 找失败，返回相关的指示信息。
lg(n 1)
二分查找的优点和缺点


虽然二分查找的效率高，但是要将 表按关键字排序。 二分查找只适用顺序存储结构。为 保持表的有序性，在顺序结构里插 入和删除都必须移动大量的结点。
分块查找

分块查找表存储结构 分块查找表由"分块有序"的线性表 和索引表组成。


分块查找的基本思想 ： 首先查找索引表 索引表是有序表，可采用二分查找 或顺序查找，以确定待查的结点在 哪一块。 然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找。



二叉排序树的生成 是从空的二叉排序树开始，每输入 一个结点数据，就调用一次插入算 法将它插入到当前已生成的二叉排 序树中。
生成二叉排序树 的算法 见右边









BSTree CreateBST(void) { BSTree T=NULL； KeyType key； scanf("％d"， &key)； while(key) { InsertBST(&T， key)； scanf("％d"， &key)； } return T； }
查找表的数据结构表示
若在查找的同时对表做修改操作（如插入和删除 等），则相应的表称之为动态查找表（Dynamic Search Table）。否则称之为静态查找表(Static Search Table)。 若整个查找过程都在内存进行，则称之为内查找； 反之，若查找过程中需要访问外存，则称之为外
例：设算法的输入实例中有序的关键 字序列为： 05，13，19，21，37，56， 64，75，80，88，92查找的关键字
K=21

第一步：05，13，19，21，37，56，64，
low
75，80，88，92
m id
high

第二步：05，13，19，21，37，56，64，
low

3)*p有两个孩子 先令q=p，将被删结点的地址保存在q 中；然后找*q的中序后继*p，并在查 找过程中仍用parent记住*p的双亲位 置。*q的中序后继*p一定是*q的右子 树中最左下的结点，它无左子树。因 此，可以将删去*q的操作转换为删去 的*p的操作，即在释放结点*p之前将 其数据复制到*q中，就相当于删去了 *q。








p=(BSTNode *)malloc(sizeof(BSTNode ))； p->key=key； p>lchild=p->rchild=NULL； if(*TPtr==NULL) *Tptr=p； else if(key<f->key) f->lchild=p； else f->rchild=p； }
查找关键字等于给定值K=24的结点
(见P199)

因为索引表小，不妨用顺序查找方法查 找索引表。即首先将K依次和索引表中 各关键字比较，直到找到第1个关键宇 大小等于K的结点，由于K<48，所以关 键字为24的结点若存在的话，则必定在 第二块中；然后，由ID[2].addr找到第 二块的起始地址7，从该地址开始在 R[7..12]中进行顺序查找，直到 R[11].key=K为止。
算法分析 生成林成功时的顺序查找的平均查找长度 ： n n ASL= pici =pi (n i 1) =np1+(ni 1 i 1 1)p2+…+2pn-1+pn （式8.2） 在等概率情况下，pi=1/n(1≤i≤n)，故成 功的平均查找长度为 (n+…+2+1)/n=(n+1)/2 即查找成功时的平均比较次数约为表长的 一半。

分块查找的优点 ①在表中插入或删除一个记录时，只 要找到该记录所属的块，就在该块内 进行插入和删除运算。 ②因块内记录的存放是任意的，所以 插入或删除比较容易，无须移动大量 记录。


8.3 树表的查找





1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找 (搜索)树(Binary Search Tree)。其定义为：二 叉排序树或者是空树，或者是满足如下性质的二 叉树： （1）若它的左子树非空，则左子树上所有结点 的值均小于根结点的值； （2）若它的右子树非空，则右子树上所有结点 的值均大于根结点的值； （3）左、右子树本身又各是一棵二叉排序树。
75，80，88，92
m id
high

第三步：05，13，19，21，37，56，64，
low high
m id
75，80，88，92 此时R[mid].key＝K，return mid＝4。
二分查找判定树 二分查找过程可用二叉树来描述： 把当前查找区间的中间位置上的结 点作为根，左子表和右子表中的结 点分别作为根的左子树和右子树。 由此得到的二叉树，称为描述二分 查找的判定树(Decision Tree)或比较 树(Comparison Tree)。
二叉排序树删除算法





void DelBSTNode(BSTree *Tptr，KeyType key) { BSTNode *parent=NUll， *p=*Tptr，*q，*child； while(p){ if(p->key==key) break； parent=p； p=(key<p->key)?p>lchild：p->rchild； } if(!p) return； q=p； if(q->lchild&&q->rchild) for(parent=q，p=q>rchild； p->lchild；

二叉排序树插入新结点的 算法
void InsertBST(BSTree *Tptr，KeyType key) { BSTNode *f，*p=*TPtr； while(p){ if(p->key==key) return； f=p； p=(key<p->key)?p>lchild：p>rchild； }



算法分析 分块查找是两次查找过程。整个查找过程 的平均查找长度是两次查找的平均查找长 度之和。 以二分查找来确定块，分块查找成功 时的平均查找长度 ASLblk=ASLbn+ASLsq≈lg(b+1)1+(s+1)/2≈lg(n/s+1)+s/2 以顺序查找确定块，分块查找成功时 的平均查找长度 ASL’blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2 s)



2) 删去*p。 删*p时，应将*p的子树(若有)仍连接在树 上且保持BST性质不变。按*p的孩子数目分 三种情况进行处理。 ②删除*p结点的三种情况 1)*p是叶子(即它的孩子数为0) 无须连接*p的子树，只需将*p的双亲 *parent中指向*p的指针域置空即可。 2)*p只有一个孩子*child 只需将*child和*p的双亲直接连接后，即 可删去*p。