跳转至

Chapter7 查找

\[ 查找 \begin{cases} 基本概念：静态查找、动态查找\\ 线性结构 \begin{cases} 顺序查找\\ 折半查找\\ 分块查找\\ \end{cases}\\ 树形结构 \begin{cases} 二叉排序树BST\\ 二叉平衡树AVL\\ \end{cases}\\ 散列结构 \begin{cases} 性能分析\\ 冲突处理\\ \end{cases}\\ \end{cases}\\ \]

7.1 查找基本概念

  • 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一是查找成功,即在数据集合中找到了满足条件的数据元素，二是查找失败。

  • 查找表：用于查找的数据集合称为查找表,它由同一类型的数据元素(或记录)组成。对查找表的常见操作有:1查询符合条件的数据元素;2插入、删除数据元素。

  • 静态查找表：若一个查找表的操作只涉及查找操作,则无须动态地修改查找表,此类查找表称为静态查找表。与此对应,需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等;适合动态查找表的查找方法有二叉排序树的查找、散列查找等。

  • 关键字：数据元素中唯一标识该元素的某个数据项的值,使用基于关键字的查找,查找结果应该是唯一的。例如,在由一个学生元素构成的数据集合中,学生元素中"学号"这一数据项的值唯一地标识一名学生。

  • 平均查找长度ASL：在查找过程中,一次查找的长度是指需要比比较的关键字次数,而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值,其数学定义为 ASL = SUM(n,i=1)PiCi

7.2 顺序查找和折半查找

7.2.1 顺序查找

顺序查找又称线性查找,它对顺序表和链表都是适用的。

对于顺序表,可通过数组下标递增来顺序扫描每个元素；对于链表,可通过指针next来依次扫描每个元素。

1从线性表的一端开始,逐个检查关键字是否满足给定的条件；

2若查找到某个元素的关键字满足给定条件,则查找成功,返回该元素在线性表中的位置；

3若已经查找到表的另一端,但还没有查找到符合给定条件的元素,则返回查找失败的信息。

下述算法中，ST.elem[0]称为哨兵,引入它的目的是使得Searoch_seq内的循环不必判断数组是否会越界。算法从尾部开始查找,若找到ST.elem[i]==key则返回 i 值,查找成功。否则一定在查找到ST.elem[0]==key时跳出循环,此时返回的是0,查找失败。该哨兵可以避免很多不必要的判断语句，从而提高程序效率

//对于一般线性表的顺序查找

typedef struct{     //查找表的数据结构
    ElemType *elem; //动态数组基址
    int TableLen;   //表长度
}SSTable;

int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;//哨兵
    for(int i=ST.TableLen;St.elem[i]!=key;--i);//从后往前找
    return i;//若查找成功，则返回元素下标；若查找失败，则返回0
}

需要注意的是，一般线性表的平均查找长度ASL，与有序线性表的平均查找长度ASL有区别，如果是有序线性表，查找到大于目标值的时候，即可返回失败了。

7.2.2 折半查找

折半查找又称二分查找，它仅适用于有序的顺序表

折半查找的基本思想:

1首先将给定值key与表中中间位置的元素比较,若相等,则查找成功,返回该元素的存储位置

2若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如,在查找表升序排列时,若key大于中间元素,则所查找的元素只可能在后半部分),然后在缩小的范围内继续进行同样的查找。

重复上述步骤,直至到找到为止,或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。

!()[]

int Binary_Search(SSTable L,ElemType key){
    int low=0,high=L.TableLen-1,mid;
    while(low<=high){
        mid=(low+high)/2;       //取中间位置
        if(L.elem[mid]==key)
            return mid;         //查找成功则返回所在位置
        else if(L.elem[mid]>key)
            high=mid-1;         //从前半部分继续查找
        else
            low=mid+1;          //从后半部分继续查找
    }
    return -1;                  //查找失败，返回-1
}

7.2.3 分块查找

分块查找又称索引顺序查找,它吸取了顺序查找和折半查找各自的优点,既有动态结构,又适于快速查找。

分块查找的基本思想：

将查找表分为若干子块。块内的元素可以无序,但块间的元素是有序的,即第一个块中的最大关键字小于第二个块中的所有记录的关键字,第二个块中的最大关键字小于第三个块中的所有记录的关键字,以此类推。

再建立一个个索引表,素引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址,索引表按关键字有序排列。

分块查找的过程分为两步:第一步是在索引表中确定待查记录录所在的块,可以顺序查找或折半查找索引表;第二步是在块内顺序查找。

7.3 树形查找

7.3.1 二叉排序树（BST）

构建一颗二叉排序树的目的并不是排序，而是提高查找、插入和删除关键字的速度

  • 二叉排序树的定义

    二叉排序树(也称二叉查找树)或者是一棵空树,或者是具有下列特性的二叉树:

    1 若左子树非空,则左子树上所有结点的值均小于根结点的值直。

    2 若右子树非空,则右子树上所有结点的值均大于根结点的值。

    3 左、右子树也分别是一棵二叉排序树。

  • 二叉排序树的查找

    二叉排序树的查找是从根结点开始,沿某个分支逐层向下比较的过程。若二叉排序树非空,先将给定值与根结点的关键字比较,若相等,则查找成功;若不等,若小于根结点的关键字,则在根结点的左子树上查找,否则在根结点的右子树上查找。这显然是一个递归的过程。

    //二叉排序树的非递归查找
BSTNode *BST_Search(BiTree T,ElemType key){
    while(T!=NULL&&key!=T->data){       //若树空或等于根结点值，则结束循环
        if(key < T->data) T=T->lchild;  //小于，则在左子树上查找
        else T=T->rchild;               //大于，则在右子树上查找
    }
    return T;
}

  • 二叉排序树的插入

    二叉排序树作为一种动态树表,其特点是树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字值等于给定值的结点时再进行插入的。

    插入结点的过程如下:若原二叉排序树为空,则直接插入;否则,若关键字k小于根结点值,则插入到左子树,若关键字k大于根结点值,则插入到右子树。插入的结点一定是一个新添加的叶结点,且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。

    int BST_Insert(BiTree &T,KeyType k){
    if(T==NULL){    //原树为空，新插入的记录为根结点
        T=(BiTrr)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = t->rchild = NULL;
        return 1;   //返回1，插入成功
    }
    else if(k==T->data) //树中存在相同关键字的结点，插入失败
        return 0;
    else if(k<T->data)  //插入T的左子树
        return BST_Insert(T->lchild,k);
    else                //插入T的右子树
        return BST_Insert(T->rchild,k);
}

  • 二叉排序树的构造

    void Creat_BST(BiTree &T,KeyType str[],int n){
    T=NULL;         //初始时T为空树
    int i=0;
    while(i<n){     //依次将每个关键字插入二叉排序树
        BST_Insert(T,str[i]);
        i++;
    }
}

  • 二叉排序树的删除

    1 若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质。

    2 若结点z只有一棵左子树或右子树,则让2的子树成为2父结点的于子树,替代z的位置

    3 若结点z有左、右两棵子树,则令z的直接后继(或直接前驱)替代z,然后从二叉排序 树中删去这个直接后继(或直接前驱),这样就转换成了第一或第二种情况。

  • 二叉排序树的查找效率

    二叉排序树的查找效率,主要取决于树的高度。若二叉排序树的左、右子树的高度之差的绝对值不超过1(平衡二叉树,下一节),它的平均查找长度为O(log2n)。若二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表),则其平均查找长度为O(n)。

7.3.2 平衡二叉树（AVL）

  • 平衡二叉树的定义

    为了避免树的高度增长过快,降低二叉排序树的性能,规定在插入和删除结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树(BalancedBinary Tree),也称AVL树。定义结点左子树与右子树的高度:差为该结点的平衡因子,则平衡二叉树结点的平衡因子的值只可能是-1、0或1。

  • 平衡二叉树的插入

    二叉排序树保证平衡的基本思想如下:每当在二叉排序树中插入(或删除)一个结点时,首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡,则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A,再对以A为根的子树,在保持二叉排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。

    LL平衡旋转

    RR平衡旋转

    LR平衡旋转

    RL平衡旋转

  • 平衡二叉树的删除

    与平衡二叉树的插入操作类似,以删除结点w为例来说明平衡二叉树删除操作的步骤:

    1 用二叉排序树的方法对结点w执行删除操作。

    2 若导致了不平衡,则从结点w开始向上回溯,找到第一个不平衡的结点z(即最小不平衡子树);y为结点z的高度最高的孩子结点:x是结点y的高度最高的孩子结点

    3 然后对以z为根的子树进行平衡调整,其中x、y和z可能的位置有4种情况:

    y是z的左孩子,x是y的左孩子(LL,右单旋转); y是z的左孩子,x是y的右孩子(LR,先左后右双旋转); y是z的右孩子,x是y的右孩子(RR,左单旋转); y是z的右孩子,x是y的左孩子(RL,先右后左双旋转)。

  • 平衡二叉树的查找

    含有n个结点的平衡二叉树的最大深度为O(log2n),因此平衡查找效率为O(log2n)

7.4 散列表（Hash）

7.4.1 散列表的基本概念

  • 散列函数(也称哈希函数):一个把查找表中的关键字映射成该关键字对应的地址的函数,记为Hash(key)=Addr(这里的地址可以是数组下标、索引或内存地址等)。

  • 散列函数：散列函数可能会把两个或两个以上的不同关键字映射到同一地址,称这种情况为冲突,这些发生冲突的不同关键字称为同义词。一方面,设计得好的散列函数应尽量减少这样的冲突;另一方面,由于这样的冲突总是不可避免的,所以还要设计好处理中突的方法

  • 散列表(也称哈希表):根据关键字而直接进行访问的数据结构。也就是说,散列表建立了关键字和存储地址之间的一种直接映射关系。

7.4.2 散列函数的构造方法

  • 散列函数计算出的地址应尽可能均匀地分布在整个地址空间,尽可能地减少冲突。

  • 散列函数应尽量简单,能在较短的时间内计算出任意一个关键字对应的散列地址。

  • 直接定址法（散列函数）

    直接取关键字的某个线性函数值为散列地址，散列函数为 H(key) = key 或 H(key) = a*key + b 式中，a和b是常数。它适合关键字分布基本连续的情况，若关键字发布不连续，空位较多，则会造成存储空间的浪费

  • 除留余数法（散列函数）

    这是一种最简单、最常用的方法,假定散列表表长为m,取一个不大于m但最接近或等于m的质数p,利用以下公式把关键字转换成散列地址。散列函数为 H(key) = key % p 除留余数法的关键是选好p,使得每个关键字通过该函数转换后等概率地映射到散列空间上的任意一个地址,从而尽可能减少冲突的可能性。

7.4.3 处理冲突的方法

  1. 开放定址法

    指表中可存放新表项的空闲地址既指向它的同义词表项开放，又向它的非同义词表项开放。

    Hi = (H(key) + di) % m ，H(key)为散列函数：i=1,2,...,k；m表示散列表表长；di为增量序列。

    取定某一曾量序列，通常有以下4种取法：

    1）线性探测法，di = 1,2,...,m-1。它的特点是：冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元或查遍全表。但可能造成大量元素在相邻的散列地址上堆积起来，大大降低查找效率

    2）平方探测法，di = 12,-12,22,-22,...k2,-k2，平方探测法是一种处理冲突的较好方法，可以避免“堆积”问题，缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元

    3）双散列法。di = i*Hash2(key)。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)计算该关键字的地址增量，Hi=(H(key)+ixHash2(key))%m，初始探测位置H0=H(key)%m

    i为冲突的次数，开放地址法不能随意物理删除表中已有元素，需要标记，否则会截断其他同义词元素的查找路径

  2. 拉链法

    显然,对于不同的关键字可能会通过散列函数映射到同一地址,为了避免非同义词发生冲突,可以把所有的同义词存储在一个线性链表中,这个线性链表由其散列地址唯一标识。假设散列地址为i的同义词链表的头指针存放在散列表的第1个单元中,因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

    如下，采用H(key) = key%13的散列函数，再用拉链法处理冲突