一、基本概念
查找：在数据结构中寻找满足条件的数据元素的过程称为查找。
查找表：用于查找的数据集合称为查找表。
关键字：数据元素的唯一标识，可以区分不同的数据元素。
二、效率评价
查找长度：在查找算法中，需要对比关键字的次数称为查找长度。
平均查找长度（ASL）：所有查找过程中进行对比关键字的次数的平均值。
三、查找算法
（一）顺序查找

//查找表的定义
typedef struct {
    ElemType *data;
    int TableLen;
}SSTable;
//顺序查找算法
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0;i<ST.TableLen&&ST.data[i]!=key;++i)
    return i==ST.TableLen?-1;
}

（二）折半查找

int Binary_Search(SSTable ST,ElemType key){
    int low=0,high=ST.TableLen-1,mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(L.data[mid]==key)
        {
            return mid;
        }
        else if(L.data[mid]>key)
        {
            high=mid-1;
        }
        else
        {
            low=mid+1;
        }
    }
    return -1;
}

（三）分块查找
①先查找索引表，确定数据元素所在的分块
②再查找分块
四、查找结构
（一）二叉排序树
1、定义
二叉排序树，又称为二叉查找树（PST）
二叉排序树的左子树的结点的关键字小于根结点的关键字小于右子树结点的关键字。

typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

2、查找

BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&T->key!=key)
    {
        if(key<T->key)
        {
            T=T->lchild;
        }
        else
        {
            T=T->rchild;
        }
    }
    return T;
}

3、插入

int BSTInsert(BSTree &T,int key){
    if(T==NULL)
    {
        T=(BSTNode*)malloc(sizeof(BSTNode));
        T->data=key;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    else if(key==T->key)
    {
        return 0;
    }
    else if(key<T->key)
    {
        return BSTInsert(T->lchild,key);
    }
    else
    {
        return BSTInsert(T->rchild,key);
    }
}

（二）平衡二叉树
1、定义
平衡二叉树（AVL）：树上任一结点的左子树和右子树的高度之差不超过1.
2、插入
在平衡二叉树中插入结点后可能会导致二叉树失去平衡，此时需要对最小不平衡子树进行平衡旋转。
（1）LL平衡旋转
在A的左孩子B的左子树中插入导致不平衡。
进行右旋，使得B代替A成为父结点，A成为B的右孩子。
（2）RR平衡旋转
在A的右孩子C的右子树中插入导致不平衡。
进行左旋，使得C代替A成为父结点，A成为C的左孩子。
（3）LR平衡旋转
在A的左孩子B的右子树B2中插入导致不平衡。
先进行左旋，使得B2代替B成为父结点，B成为B2的左孩子；
再进行右旋，使得B2代替A成为父结点，A成为B2的右孩子。
（4）RL平衡旋转
在A的右孩子C的左子树C1中插入导致不平衡。
先进行右旋，使得C1代替C成为父结点，C成为C1的右孩子；
再进行左旋，使得C1代替A成为父结点，A成为C1的左孩子。
（三）红黑树（RBT）
1、定义
满足下列要求：
①每个结点可以是红色或者黑色
②根结点是黑色的
③叶结点是黑色的
④不存在两个相邻的红结点
⑤每一个由根结点到叶结点的路径中，黑结点的数目相同
2、性质
①从根结点到叶结点的最长路径不超过最短路径的2倍
②含有n个内部结点的红黑树的高度不超过$2log_2(n+1)$
3、插入
将插入结点的父结点的兄弟结点称为“叔叔结点”，在插入一个新结点时，进行下列判断：
（1）判断是否为根结点
①若新结点是根结点，染为黑色
②若新结点不是根结点，染为红色
（2）判断是否仍为红黑树
①若仍为红黑树，插入结束
②若不再是红黑树，进行调整：
A.若插入结点的叔叔结点是黑色，进行平衡旋转并染色：
LL平衡旋转：旋转后父结点替换爷结点并染色
RR平衡旋转：旋转后父结点替换爷结点并染色
LR平衡旋转：旋转后儿结点与爷结点染色
RL平衡旋转：旋转后儿结点与爷结点染色
B.若插入结点的叔叔结点是红色，将叔父爷结点染色，并将爷结点视为新结点。
（四）B树
1、定义
B树，又称多路平衡查找树。B树中允许的孩子的个数称为B树的阶m。B树满足下面的条件：
①树中的每个结点至多有m个子树，即最多有m-1个关键字
②若根结点并非终端结点，则至少含有两个子树
③除根结点之外的所有非叶子结点中，至少有m/2（向上取整）个子树，即至少含有m/2+1（向上取整）个关键字
④所有的叶结点均位于同一层，且不带信息
2、插入
若插入的关键字超过了结点的关键字上限，则将中间的关键字向上提取一层，并将左右的关键字分裂为两个结点。
3、删除
（1）删除
若删除的关键字在终端结点，可直接删除；
若不在终端结点，则需要使用直接前驱或直接后继来替代该关键字。
【注意】
直接前驱指的是关键字左侧指针下“最右下”的元素
直接后继指的是关键字右侧指针下“最左下”的元素
（2）判断
若结点的关键字低于下限，则需要向左右兄弟“借”关键字
（五）B+树
B+树在符合B树条件下，只在叶子结点保存指向关键字的指针。
（六）散列表
1、定义
散列表：又称哈希表，可以通过散列函数将数据元素的关键字映射到存储地址。
散列函数：表示“关键字”——>“存储地址”的映射关系
冲突：插入元素时，映射的存储地址已经存有其他元素
同义词：映射到同一地址的元素称为同义词
2、解决冲突的方案
（1）拉链法
配合链表，在每个存储单元中存储指针。
（2）开放定址法
发生冲突时，按照一定的规则寻找另一个空闲位置。
常用规则如下：
①线性探测法
②平方探测法
③双散列法
④伪随机序列法
3、散列函数的构造
1、除留余数法
取一个最靠近表长的质数，用关键字除以质数，取余数作为地址。
2、直接定址法
定义一个线性函数，直接通过函数计算地址。
3、数字分析法
选择关键字中的某几位作为地址。
4、平方取中法
根据关键字平方的中间几位作为地址。