在日常生活中，人们几乎每天都在进行各种各样的查找工作。例如，在电话号码薄中查找电话号码；在字典中查阅词汇等。
在程序设计中，特别是对于非数值处理语言，要消耗大量的时间进行查找运算，而且由于查找运算的频率很高，几乎在任何一个计算机系统软件和应用软件中都会涉及。当问题涉及的数据量相当大的时候，查找方法的效率就显得格外重要，在一些实时应答系统中尤其如此。所以，一个好的查找方法会大大提高程序及系统的效率和速度。
一、基本概念
1. 查找的定义
① 查找又称检索，是数据处理中经常使用的一种重要运算。
② 在本章的讨论中，假定被查找的对象是一组结点组成的表或文件，而每个结点由若干个数据项组成，并假设每个结点都有一个能唯一标识该结点的关键字。在这种假定下，查找的定义是：给定一个值k的结点，若找到，则查找成功，输出该结点在表中的位置；否则查找失败，输出失败的信息。
③ 因为查找是对已存入计算机中的数据所进行的操作，所以，采用何种查找方法，首先取决于使用哪种数据结构来表示表，即表中的数据元素按何种方式组织。为了提高查找速度，常常用某些特殊的数据结构组织存储表。因此，在研究各种查找方法时，首先必须弄清这些方法所使用的数据结构。
④ 查找有内查找和外查找之分。若整个查找过程都在内存中进行，则称为内查找；反之，若查找过程需要访问外存，则称为外查找。
2. 基本术语
① 数据项：项是具有独立含义的标识单位，是数据不可分割的最小单位。
② 组合项：组合项由若干项组合而成。
③ 数据元素：数据元素是由若干项、组合项构成的数据单位，是在某一问题中作为整体进行考虑和处理的基本单位。数据元素有型和值之分，表中项名的集合，也即表头部分就是数据元素的类型。
④ 关键字：关键字是数据元素中某个项或组合项的值，用它可以标识一个数据元素。能唯一确定一个数据元素的关键字，称为主关键字；而不能唯一确定的一个数据元素的关键字，称为次关键字。
⑤ 查找表：查找表是由具有同一类型的数据元素组成的集合。分静态查找表和动态查找表。
二、线性表的查找
1. 顺序查找
① 顺序查找是一种最基本也是最简单的查找方法。它的基本思想是，从表的一端开始，顺序扫描整个线性表，逐个进行结点关键字值与给定的值k相比较，若当前扫描到的结点关键字与k相等，则查找成功；若扫描了整个表后，仍未找到关键字与给定值k相等的结点，则查找失败。
② 顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。使用单链表作为存储结构时，查找必须从头指针开始，因此只能进行顺序查找。下面介绍顺序表作为存储结构时的顺序查找。
③ 基本类型的具体算法
typedef struct{ KeyType key; //关键项 Datatype other; //其他域 }SSTable; SSTable R[MAX]; //约定从下标1开始存放查找表元素，0单元闲置
④ 基于顺序表的顺序查找算法
int SeqSearch(SSTable R[],int n,KeyType k){ int i=n; R[0].key=k; while(R[i].key!=k){ i--; } return i; }
2. 二分查找
① 二分查找又称为折半查找，是一种效率较高的查找方法。但是，二分查找要求线性表是有序表，即表中的数据元素按关键字有序组织，并且要用顺序表作为表的存储结构。在下面的讨论中，假设顺序表是有序递增的。
② 二分查找的基本思想是，首先将待查找的k值和有序表R中间位置mid=(1+n)/2上的结点的关键字进行比较：
（1）若相等，则查找完成
（2）若R[mid].key>k，则说明待查找的结点在表的前半部分，可在前半部分表中继续进行二分查找。
（3）若R[mid].key<k，则说明待查找的结点在表的后半部分，可在后半部分表中继续进行二分查找。
③ 这样，经过一次关键字的比较就缩小一半查找区间；如此反复，直到找到关键字为k的结点（查找成功），或当前的查找区间为空（查找失败）。
④ 二分查找算法
int BinSearch(table R[],int n,KeyType k){ int low,mid,high; low=1; //设置查找的上下区间 high=n; while(low<=high){ //当前查找区间为非空 mid=(low+high)/2; if(k==R[mid].key) return mid; //查找成功返回在表中的位置 if(k<R[mid].key) high=mid-1; //缩小查找区间为左子表 else low=mid+1; //缩小查找区间为右子表 } return 0; //查找失败 }
3. 分块查找
① 分块查找又称索引顺序查找，是一种性能介于顺序查找和二分查找之间的查找方法。它要求按如下的索引方式来存储查找表：将表均分为b块，前b-1块中的结点数为S=[n/b]，第b块的结点数小于等于S；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是“分块有序”的；抽取各块中的最大关键字及其块起始位置构成一个索引表ID[b]，即ID[i]中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增的有序表。
② 分块查找的基本思路是，首先，查找索引表，因为索引表是有序表，故可采用二分查找或顺序查找，以确定待查找的结点在哪块；然后，在已确定的块中进行顺序查找。
③ 分块查找的优点是，在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块中进行插入或删除运算。因块内记录的存放是任意的，所以，插入或删除比较容易，无须移动大量记录。分块查找的主要代价是需要增加一个辅助数组存储索引表和对初始表进行分块排序建立索引表的运算。
当线性表作为查找表的组织形式时，可以有三种查找法，其中以二分查找效率最高。但由于二分查找要求表中结点按其关键字有序组织，且不能用链表作为存储结构，因此，当表的元素插入或删除操作频繁时，为维护表的有序性，势必要移动表中大量的结点，这种由移动结点引起的额外的时间开销，就会抵消二分查找的优点。在这种情况下，可采用二叉树作为存储结构，在此将它们统称为树表。
三、二叉排序树
（1）二叉排序树又称为二叉查找树，是一种特殊的二叉树。其定义为：
（1）若它的左子树非空，则左子树上所有的结点的值均小于根结点的值
（2）若它的右子树非空，则右子树上所有的结点的值均大于根结点的值
（3）左、右子树本身又各是一棵二叉排序树
（2）二叉排序树定义：
typedef struct node{ KeyType key; Datatype other; struct node *lchild，*rchild; }BSTNode;
1. 二叉排序树的插入和生成
① 在二叉排序树中插入新的结点，只要保证插入后仍符合二叉排序树的定义即可。插入过程如下：
（1）若二叉排序树为空，则待插入结点*s作为根结点插入到空树中
（2）当二叉树非空，将待插入结点的关键字s->key和树根的关键字t->key进行比较，若s->key=t->key，则说明此树中已有此结点，无需插入；若s->key<t->key，则将待插入结点*s插入到根的左子树中，否则将*s插入根的右子树中
（3）子树中的插入过程与步骤（1）（2）相同，直到把结点*s作为新的结点插入二叉排序树中，或直到发现该树中已有此*s结点为止。
② 二叉排序树的插入算法
BSTNode *INSERTBST(BSTNode *s,BSTNode t){ BSTNode *f,*p; if(t==NULL) return s; p=t; while(p!=NULL){ f=p; if(s->key==p->key) return t; if(s->key<p->key) p=p->lchild; else p=p->rchild; } if(s->key<f->key) f->lchild=s; else f->rchild=s; return t; }
③ 二叉排序树的生成算法
BSTNode *CREATBST(){ BSTNode *t,*s; KeyType key,endflag=0; DataType data; t=NULL; scanf("%d",&key); while(k!=endflag){ s=malloc(BSTNode *)malloc(sizeof(BSTNode)); s->lchild=s->rchild=NULL; s->key=key; scanf("%d",data); s->other=data; t=INSERTBST(t,s); scanf("%d",&key); } return 0; }
2. 二叉排序树的查找
① 二叉排序树的查找算法
BSTNode *BSTSearch(BSTNode *t,KeyType t){ BSTNode *p=t; while(p!=NULL){ if(p->key==k) return p; if(p->key>k) p=p->lchild; else p=p->rchild; } }
四、平衡二叉树
平衡二叉树又称AVL树。它或者是一棵空树，或者是任何结点的左子树和右子树的深度最多相差1的二叉树。若将二叉树上的结点的平衡因子定义为该结点的左子树的深度减去右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1，0，和1.只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
平衡二叉树的节点结构定义如下：
typedef struct node{ KeyType key; Datatype other; int bf; struct node * lchild,* rchild; }AVLnode;
1. 平衡二叉树的构造
（1）基本思想：在构造二叉树的过程中，当插入一个结点时，首先，检查是否因插入结点而破坏了树的平衡性，若是，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，以达到新的平衡。
（2）所谓最小不平衡树，是指以离插入结点最近、且平衡因子绝对值大于1的结点作为根的子树。为了方便，不妨假设二叉排序树最小不平衡树的根结点是A，调整该子树的规律可归纳为四种情况：LL型，LR型，RR型和RL型。
LL型：插入位置在根结点的左子树的左子树，插入后二叉树不平衡
LR型：插入位置在根结点的左子树的右子树，插入后二叉树不平衡
RR型：插入位置在根结点的右子树的右子树，插入后二叉树不平衡
RL型：插入位置在根结点的右子树的左子树，插入后二叉树不平衡
①LL型调整操作：向右旋转
②RR型调整操作：向左旋转
③LR型调整操作：先向左旋转，再向右旋转
④RL型调整操作：先向右旋转，再向左旋转
2. 平衡二叉树的插入
（1）基本思想：
①由于s的插入而失去平衡时，找到最小不平衡子树
②当s插入后，修改有关结点的平衡因子
③判断以a为根的子树是否失去平衡
（2）可以证明：含有N个结点的AVL树，树的高度h=O(log2N)。由于在AVL树上查找时，和关键字比较的次数不会超过树的高度h，且不再蜕变成单支树的情形。因此，查找AVL树的时间复杂度是O(log2N)。然而，动态平衡过程仍需要耗费不少时间，故在实际应用中是否采用AVL树，还要根据具体情况而定。一般情况下，若结点关键字是随机分布的，并且系统对平均查找长度没有苛求，则可使用二叉排序树。
3. 平衡二叉树的算法
平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等等
①红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
②AVL是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
③Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap并不一定是。
④伸展树（Splay Tree）是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。在伸展树上的一般操作都基于伸展操作。
