数据结构与算法 - 查找

目录

一、查找的定义 二、线性表的查找    2.1 、顺序查找    2.2、二分查找    2.3、分块查找 三、树表查找    3.1 、二叉排序树    3.2 、平衡二叉树

一、查找的定义

查找 又称检索，是数据处理中经常使用的一种重要运算。采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，及表中的数据元素按何种方式组织。     查找有内查找和外查找之分。若整个查找过程都在内存进行，则称为内查找；反之，若查找过程需要访问外存，则称为外查找。 关键字 是指数据元素(记录)中某个项或组合项的值，用它可以标识一个数据元素(记录)。能唯一确定一个数据元素(记录)的关键字，称为主关键字；而不能唯一确定一个数据元素(记录)的关键字，称为次关键字。 查找表 是指由具有同一类型(属性)的数据元素(记录)组成的集合。分为静态查表和动态查找表。     静态查找是指仅对查找表进行查找操作，而不改变查找表中的数据元素。动态查找是指除进行查找操作外，可能还要进行向表中插入或删除数据元素的操作。

平均查找长度

二、线性表的查找

    2.1 、顺序查找

顺序查找( Sequential Search) 是一种最基本也是最简单的查找方法。它的基本思想是蛮力法，从表的一端开始，顺序扫描线性表，逐个进行结点关键字值与给定的值k相比较，若当前扫描到的结点关键字与k相等，则查找成功；若扫描整个表后，仍未找到关键字与给定值k相等的结点，则查找失败。     顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。使用单链表作存储结构时，查找必须从头指针开始，因此只能进行顺序查找。顺序查找代码如下：

    //蛮力法的算法 
    int n = 100; //规模
    int k = 20;  //查找目标元素
    NSMutableArray * array = [NSMutableArray array];
    for (int i = 0; i < n; i++) {
        NSNumber * number = @(arc4random()%n);
        [array addObject:number];
    }
    for (int i = 0; i < n; i++) {
        NSNumber * number = array[i];
        if ([number intValue] == k) {
            NSLog(@"找了%d次 目标元素索引为%d", i,i);
            break;
        }
        if(i == n - 1){
            NSLog(@"没有查找到目标元素");
        }
    }

    顺序查找算法的 时间复杂度 为O(n)。     顺序查找的优点是算法简单，且对表的结构无任何要求，无论用顺序表还是链表来存放结点，也无论结点是否按关键字有序，都同样适用。顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找。对于线性链表，只能进行顺序查找。

    2.2 、二分查找

二分查找( Binary Search)又称折半查找 ，是一种效率较高的查找方法。但是，二分查找要求线性表是 有序表 ，即表中的数据元素按关键字有序组织，并且要用顺序表作为表的存储结构。     在下面讨论中，假设有序表是递增有序的。     二分查找的基本思想是减治法，首先将待查找的k值和有序表R中间位置mid=(1+m)/2上的结点的关键字进行比较：     (1)若相等，则查找完成。     (2)若R[mid]。key>k，则说明待查找的结点在表的前半部分中，可在前半部分表中继续进行二分查找。     (3)若R[mid]。key<k，则说明待查找的结点在表的后半部分中，可在后半部分表中继续进行二分查找。     这样，经过一次关键字的比较就缩小一半查找区间；如此反复，直到找到关键字为k的结点(查找成功)，或当前的查找区间为空(查找失败)。     二分查找示例代码如下：

二分查找示例图

    int n = 100; //规模
    int key = 39; //查找目标元素
    //初始化元素数组
    NSMutableArray * array = [NSMutableArray array];
    for (int i = 0; i < n; i++) {
        NSNumber * number = @(arc4random()%n);
        [array addObject:number];
    }
    //对数组进行排序 升序
    NSArray *sortedArray = [array sortedArrayUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
        return [obj1 compare:obj2]; //升序
    }];
    
    //初始化查找元素的区间
    int begin = 0;
    int end = (int)sortedArray.count;
    //查找目标元素索引
    int keyIndex = BinarySearch(sortedArray, key, begin, end);
    
//二分查找递归函数 返回目标元素索引 -1表示没有查找到
int BinarySearch(NSArray *sortedArray, int key, int begin, int end) {
    //查找次数
    static int i = 0;
    i++;
    //查找区间中间元素索引
    int mid = -1;
    mid = (begin + end)/2;
    if(begin > end){
        NSLog(@"没有查找到目标元素");
        return -1;
    }
    if ([sortedArray[mid] intValue] > key) {
        end = mid - 1;
        return BinarySearch(sortedArray, key, begin, end);
    }else if([sortedArray[mid] intValue] == key){
        NSLog(@"找了%d次 目标元素索引为%d",i,mid);
        return mid;
    }else {
        begin = mid + 1;
        return BinarySearch(sortedArray, key, begin, end);
    }
}

    二分查找算法的效率为O(log n)(以2为底的对数)。效率比顺序查找高，缺点是只适用于有序顺序表。

    2.3 、分块查找

分块查找( Blocking Search)又称索引顺序查找 ，是一种性能介于顺序查找和二分查找之间的查找方法。     它要求按如下的索引方式来存储查找表：将表均分为b块，前b-1块中的结点数为S=[n/b]，第b块的结点数小于等于S；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是“分块有序”的；抽取各块中的最大关键字及其块起始位置构成一个索引表ID[b]，即IDi中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。

分块查找示意图

    分块查找的基本思想是 分治法 ，首先，查找索引表，因为索引表是有序表，故可采用二分查找或顺序查找，以确定待查的结点在哪块；然后，在已确定的块中进行顺序查找。

分块查找的平均长度

    显然，当S=n时AS取极小值√n+1，即当采用顺序查找确定块时，应将各块中的结点数选定为√n。     例如，若表有10000个结点，则应把它分成100个块，每块中含100个结点。用顺序查找确定块，分块查找平均需要做100次比较，而顺序查找平均需要做5000次比较，二分查找最多需要14次比较。由此可见，分块查找算法的效率介于顺序查找和二分查找之间。

    分块查找的优点是，在表中插入或删除一个记最时，只要找到该记录所属的块， 就在该块中进行插入或删除运算，因块内记录的存放是任意的，所以，插入或删除比较容易，无须移动大量记录。分块查找的主要代价是需要增加一个辅助数组存储索引表和对初始表进行分块排序建立索引表的运算 。

三、树表查找

    由上可知，当用线性表作为查找表的组织形式时，上面的三种查找法中，其中以二分查找效率最高。但由于二分查找要求表中结点按其关键字有序组织，且不能用链表作存储结构，因此，当表的元素插入或删除操作频繁时，为维护表的有序性，势必要移动表中大量的结点，这种由移动结点引起的额外的时间开销，就会抵消二分查找的优点。在这种情况下，可采用以下的几种特殊的树或二叉树作为查找表的存储结构，在此将它们统称为 树表 。

    3.1 、二叉排序树

二又排序树( Binary Sort Tree)又称为二叉查找树 ，是一种特殊的二叉树。其定义为：二又排序树或者是一棵空树，或者是具有如下性质的二叉树：     (1)若它的左子树非空，则左子树上所有的结点的值均小于根结点的值。     (2)若它的右子树非空，则右子树上所有的结点的值均大于根结点的值。     (3)左、右子树本身又各是一棵二又排序树。     从二叉排序树的定义可得出二叉排序树的一个重要性质：按中序遍历该树所得到的中序序列是一个递增有序序列 。例如下图：

二叉排序树示意图

       3.1.1 、二叉排序树的插入和生成

    在二叉排序树中插入新的结点，只要保证插入后仍符合二又排序树的定义即可。插入过程和示意图如下：     (1)若二叉排序树为空，则待插入结点s作为根结点插入到空树中。     (2)当二叉排序树非空，将待插结点的关键字s->key和树根的关键字t->key进行比较，若s->key=t->key，则说明此树中已有此结点，无须插入；若s->key<t->key，则将待插结点s插入根的左子树中，否则将s插入根的右子树中。     (3)子树中的插入过程与步骤(1)和步骤(2)相同，直到把结点s作为新的结点插入二叉排序树中，或直到发现该树中已有此*s结点为止。     显然，插入过程从根结点开始逐层向下查找插入位置，且插入的结点必然是叶结点。

二叉排序树的插入和生成示意图

       3.1.2 、二叉排序树的删除

    从二叉排序树中删除一个结点，不能把以该结点为根结点的子树都删去，只能删掉该结点，并且还要保证删除后所得的二叉树仍然是二叉排序树。即在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。

    删除操作必须首先进行查找，以确定被删除结点是否在二又排序树中。若不在，则不做任何操作；否则，设找到被删除的结点是p，f指向p的双亲，删除操作可按p是否有左子树来分别处理(当然也可按p是否有右子树来处理)：     (1)若被删除的结点p没有左子树，则删除p时只要将p的右子树按照二叉排序树的特性链接到合适的位置即可，若p是根结点(有右子树)，则只要将p的右子树的根作为新的根结点；若p不是根结点，则删除p时必须将它与其双亲f之间的链接断开。所以，恰好可利用此链将待链接的p的右子树链接到f的左(或右)链域上，即若p是f的左孩子，则将米p的右子树链接到f的左链上，否则将p的右子树链接到f的右链上，其指针变化如图所示。显然，若p的右指针树为空，则p是树叶，此时，p-> rchild=NULL，相当于将空树链接到f的左(或右)链域中。     (2)若被删除结点p有左子树，p也可能有右子树，因此，删除p时应考虑p的左子树、右子树链接到合适的位置，并保持二又排序树的特性。此时有两种操作：一是令p的左子树直接链接到p的双亲f的左(或右)链域上，而p的右子树下接到p的中序前驱结点S的右链上(s是p的左子树中最右下的结点，即s是p的左子树中关键字的值最大的结点)，它的链域为空，其指针变化情况如图所示；另一种是以p的中序前驱S顶替p(即把S的数据复制到p中)，将s的左子树直接上接到s的双亲结点q的左(或右)链域上，然后删去*s，其指针变化情况如图所示。显然，前一种操作法可能增加树的深度，不如后一种做法好。

二叉排序树的删除示意图

       3.1.3 、二叉排序树查找

    因为二叉排序树可看做是一个有序表，所以，在二叉排序树上进行查找，和二分法类似，也是一个逐步缩小查找范围的过程。实际上在前面介绍的二叉排序树的插入和删除操作中都使用了查找操作。     查找算法思想如下：首先将待查关键字key与根节点关键字t进行比较：     a.如果key = t, 则返回根节点指针。     b.如果key < t,则进一步查找左子书。     c.如果key > t,则进一步查找右子树。

    在二叉排序树上进行查找，若查找成功，则是从根结点出发走一条从根到待查结点的路径：若查找不成功，则是从根结点出发走一条从根到某个叶子结点的路径。因此与二分查找类似，和关键字比较的次数不超过树的深度。然而，二分查找法查找长度为n的有序表，其判定树是唯一的，而含有n个结点的二叉排序树的形态却不唯一。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也不同，如下图所示的树：

结点插入的先后次序不同

//二叉排序树查找算法
#include <stdio.h>
#include <stdlib.h>

typedef struct BSTNode {
    int data;
    struct BSTNode *lTree,*rTree;
}BSTNode,*BSTree;

//递归实现二叉排序树的插入操作
void InsertBST(BSTree &BT,BSTNode *BN) {
    if(BT==NULL)
        BT=BN;
    else if(BT->data > BN->data)
        InsertBST(BT->lTree,BN);
    else
        InsertBST(BT->rTree,BN);
}

//删除操作
//判断它属于哪种类型
//1、叶子节点。
//2、只有左子树或者只有右子树。
//3、既有左子树，又有右子树。
bool deleteBST(BSTree &BT,BSTNode *BN) {
    BSTNode* tmp;
    if(BN->lTree == NULL && BN->rTree == NULL)
        delete BN;
    else if(BN->lTree == NULL) {
        tmp=BN;
        BN=BN->rTree;
        delete tmp;
    }   else if(BN->rTree == NULL)  {
        tmp=BN;
        BN=BN->lTree;
        delete tmp;
    }    else
    {
        tmp=BN;
        BSTNode * s = BN->lTree;
        while (s->rTree) 
        { 
            tmp = s; 
            s = s->rTree; 
        } 
        BN->data = s->data;
        if (tmp != BN) {
            tmp->rTree = s->lTree;
        }
        else { 
            tmp->lTree = s->lTree;
        }
        delete s;
    }
    return true;
}
//创建二叉排序树
void CreateBST(BSTree &BT,int n)  {  
    BT=NULL;//这里一定要将BT置空，表示刚开始的时候是空树，不置空的话，编译器分配的BT是非空的  
    int i,j;  
    int r[100];  
    BSTNode *s;  
    for(j=0;j<n;j++)  
        cin>>r[j];  
    for(i=0;i<n;i++)  {  
        s=new BSTNode;  
        s->data=r[i];  
        s->lTree=NULL;  
        s->rTree=NULL;  
        InsertBST(BT,s);  
    }  
}

//递归实现搜索查找
BSTNode* searchBST(BSTree &BT,int value) {
    if(BT==NULL)
        return  NULL;
    if(BT->data==value)
        return BT;
    if(BT->data>value)
        return searchBST(BT->lTree,value);
    if(BT->data<value)
        return searchBST(BT->rTree,value);
}

int main() {
    BSTree bt;
    BSTNode * bn;
    CreateBST(bt,20);
    searchBST(bt,16);
    return 0;
}

二叉排序树的查的效率也为O(log n)(以2为底的对数)。二叉排序树的查找和二分查找相差不大，并且二又排序树的插入和删除结点十分方便，无须移动大量结点，所以，对于需要经常做插入、删除和查找运算的表，宜釆用二叉排序树结构。

    3.2 、平衡二叉树

平衡二叉树( Balanced Binary Tree或 Height-Balanced Tree)又称为AVL树 。它或者是一棵空树，或者是任何结点的左子树和右子树的深度最多相差1的二又树。若将二叉树上的结点的 平衡因子 ( Balance Factor，BF)定义为该结点的左子树的深度减去右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二又树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。平衡二叉树的结点结构如下图所示：

平衡二叉树和非平衡二叉树

       3.2.1 、平衡二叉树的构造

    动态的保持二叉排序树平衡的方法，其基本思想是：在构造二叉树的过程中，当插入一个结点时，首先，检查是否因插入结点而破坏了树的平衡性，若是，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，以达到新的平衡。     所谓最小不平衡树，是指以离插入结点最近、且平衡因子绝对值大于1的结点作为根的子树。为了方便，不妨假设二叉排序树最小不平衡树的根结点是A，调整该子树的规律可归纳为以下4种情况：

LR型(先B左旋转，后A右旋转)调整

LL型右旋调整

RL型(先B右旋转，后A左旋转)调整

RR型左旋调整

   含有N个结点的AVL树，树的高度h=O(log n)(以2为底的对数)。由于在AVL树上查找时，和关键字比较的次数不会超过树的高度h，且不再蜕变成单支树的情形。因此，查找AVL树的时间复杂度是O(log n)(以2为底的对数)。然而，动态平衡过程仍需耗费不少的时间，故在实际应用中是否采用AVL树，还要根据具体情况而定。一般情况下，若结点关键字是随机分布的，并且系统对平均查找长度没有苛求，则可使用二又排序树。

注：文中的图片均转摘自网络