数据结构——查找

查找的基本概念

查找表：由同一类型的数据元素/记录构成的集合。由于集合中的数据元素之间存在着 松散关系，因此查找表是一种应用灵便的结构

查找表类似于数据库，但可以人为的规定存储方式

查找方法取决于查找表的结构，即表中数据元素是依据何种关系组织在一起的

查找：指根据关键字的值获得对应确定的数据元素或记录

关键字

• 主关键字 (主键)：可唯一的标识一个记录的关键字
• 次关键字 ：用以识别若干记录的关键字

查找表可分为两类：

• 静态查找表：仅做 查询(检索) 操作的查找表
• 动态查找表：作 插入 和 删除 操作的查找表

有时会将查询结果为不在表中的数据元素插入到查找表中；或者，从查找表中删除查询结果为在查找表中的数据元素，此两类为动态查找表

平均查找长度：平均查找长度ASL，评价查找算法的指标

线性表的查找

线性表上查找的三种常用方式：

• 顺序表查找
• 折半查找 (二分)
• 分块查找

1.顺序查找

应用范围：

• 顺序表或线性链表表示的静态查找表
• 表内元素之间可以无序

数据元素一般带有一个关键字域，是查找标准

//结点结构定义
typedef struct node
{
    Key key;    //主键
    ....        //其余属性
}Node;
//顺序表结构定义
typedef struct list
{
    Node* p;       //表基地址
    int length;    //表长
}sqTable;

顺序查找是最基本的查找技术，就是挨个挨个的查，这里就不写挨个挨个查的代码了，写一下用哨兵优化过的顺序查找

int search(Key key, Node* node)
{
    int i = table.length;  //尾部开始判断
    node[0]->key = key;      //这里用到[0],因此在构造时需要空出[0]
    while(node[i]->key != key)
    {
        i--;
    }
    return i;  //返回0查找失败
}

算法分析：

• 查找第 i 个元素，需要比较 n-i+1 次
• 查找失败，需要比较 n+1 次

平均查找长度为：ASL(n) = (1+2+3…+n)/2 = (n+1)/2

2.有序表查找

2.1 二分查找

对有序表，每次将待查找的区间缩小一半

将有序表末尾记为 right，首部记为 left，则中间为

mid = ( right + left ) / 2

如果当前mid对应的值小于查找值，说明在当前位置 (mid) 的左边，缩小查找范围至mid的左边；反之若大于查找值，说明在右边，缩小查找范围至mid的右边

实现：

//递归版
int binarySearch2(int key, int* arr, int right, int left)
{
    if (left > right) return -1;
    int mid = (right + left) / 2;
    if (arr[mid] == key) return mid + 1;
    else if (arr[mid] > key) return binarySearch2(key, arr, mid-1, left);
    else return binarySearch2(key, arr, right, mid+1);
}
//非递归
int binarySearch(int n, int key, int* arr)
{
    int mid = 0;
    int right = n; //n为数组长度
    int left = 1;   //起始
    while(left<right)
    {
        mid = (left + right) / 2;  //折半
        if (arr[mid] == key)
        {
            return mid + 1;
        }
        else if (arr[mid] > key) //查找值小于中值，则将右范围移至mid前
        {
            right = mid - 1;
        }
        else    //查找值如果大于中值则同理
        {
            left = mid + 1;
        }
    }
    return -1;
}
int main(void)
{
    int arr[10] = { 0,4,7,9,10,13,41,56,74,78 };
    printf("%d\n", binarySearch(10, 78, arr));
    system("pause");
    return 0;
}

二分查找的过程可以绘制成一棵二叉树

C表示如果元素在这个位置，则需要查询C次

对具有n个结点的完全二叉树的深度为 [logn] + 1，因此最坏的查找次数为 [logn] + 1，最好为1次，因此二分查找的时间复杂度为 O(logn)

2.2 插值查找

2.3 斐波那契查找

3.线性索引查找(分块查找)

块间(索引)有序，块内无序

条件：

1. 将表分成几块，且表有序，或者分块有序
   若 i < j，则第 j 块中所有记录的关键字均大于第 i 块中的最大关键字

2. 建立 索引表 (每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序)
   
   下面标识第 i 块的起始下标，上面表示第 i 块中最大关键字

3. 查找过程：先确定待查记录所在块 (顺序或折半查找)，再在块内查找 (顺序查找)

分块查找的查找效率：ASL = L + L (L是对索引表进行查找的ASL， L 是块内查找的ASL)

优缺点

优点：插入和删除比较容易，无需进行大量移动

缺点：要增加一个索引表的存储空间并对初始索引表进行排序

适用情况：如果线性表既要快速查找又要经常动态变化，则可采用分块查找

4.查找方法比较

树表的查找

表结构在查找过程中动态生成，对于给定key值，若表中存在，则返回成功；否则，插入关键字为key的记录

1.二叉排序树

定义：二叉排序树可以是空树，也可以是满足以下性质的二叉树：

• 若其左子树非空，则左子树上所有结点的值均小于根结点的值
• 若其右子树非空，则右子树上所有结点的值均大于等于根结点的值
• 其左右子树本身又各是一棵二叉排序树

eg：

二叉排序树的中序遍历序列就是一个按关键字排序的递增有序序列

1.1 查找

递归查找二叉排序树中是否存在key

每次传入一个结点，判断：

• 若当前结点为NULL，则保存其父结点，并返回0 (用于插入中在对应位置插入)
• 若当前结点key与target的key相等，则返回1
• 当前结点大于target的key，则含有key的结点在当前结点的左边(如果存在)，向左递归；反之，朝右递归

//查找
/*
p保存结点
parent为在对应查找失败(即key结点不存它该存在的位置)时的父结点
child即当前结点
*/
int search(pTreeNode child, int key, pTreeNode parent, pTreeNode* p)
{
    if (!child)    //查找失败
    {
        //保存父结点，在父结点的子结点上进行插入
        *p = parent;
        return 0;
    }
    else if (child->data == key)
    {
        return 1;
    }
    else if (child->data > key)
    {
        return search(child->left, key, child, p);   //target比当前结点key值小，说明若结点存在
                                                     //则应在当前结点的左边，递归
    }
    else
    {
        return search(child->right, key, child, p);
    }
}

查找算法分析：

含有n个结点的二叉排序树，其平均查找长度与树的形态有关：

最好情况下，与二分查找中的判别树相同，深度为[logn]+1，为O(logn) (平衡状态下)

最差情况下为单支树形态，深度为n，为O(n) (不平衡状态下)

为了提高不平衡状态下的二叉树的查找效率，可以对其进行平衡化处理，平衡化处理的二叉树称为平衡二叉树

1.2 插入

插入过程：

• 若二叉排序树为空，则插入第一个结点作为根结点

• 否则，在其左右子树上继续查找 (借助上面的查找算法)：

  • 树中已有，不再插入

  • 树中没有：

    • 查找到某一个结点的左子树或右子树为空位置，则插入结点应该为该结点的左孩子或右孩子

//插入
int insert(pTreeNode* tree, int key)
{
    //p保存查找到的key对应的结点
    pTreeNode p, s;  
    //如果没有查找到对应结点，则插入
    if (!search(*tree, key, NULL, &p))
    {
        s = (pTreeNode)malloc(sizeof(treeNode));
        s->data = key;
        s->left = s->right = NULL;
        //tree是空树，将当前结点作为根结点
        if (!p)
        {
            *tree = s;
        }
        //大于父结点的，则插在父结点的右子树上
        else if (key > p->data)
        {
            p->right = s;
        }
        else
        {
            p->left = s;
        }
        return 1;
    }
    else
    {
        return 0;
    }
}

1.3 删除

删除一个结点，不能把此结点的子树删掉，还应保证删除后仍然满足二叉排序树的性质不变

因此对于删除而言，有三种情况：

• 删除叶子结点：直接删，改为空
• 删除仅有左或右子树的结点：左或右子树整个移动到删除结点的位置，代替父结点，子承父业 (
• 删除左右子树都有的结点：找到这个结点在中序遍历中的直接前驱或直接后继 s ，用 s 来替换该结点，然后再删除 s

PS：直接前驱或后继一定是左子树上的最右结点或==右子树上的最左结点== (因为左子树上一定比根结点小，左子树上最右的一定是最大且小于根结点的；右子树上最左结点同理)

void dele(pTreeNode* node)
{
    //如果左子树为空，则直接连接到右子树
    if (!(*node)->left)
    {
        pTreeNode q = *node;
        *node = (*node)->right;    //直接将被删除结点的地址修改为其右子树地址，这样就可以
                                   //在不需要知道其双亲的情况下直接让双亲指向了被删除结点的右子树
        free(q);
    }
    //右子树为空
    else if (!(*node)->right)
    {
        pTreeNode q = *node;
        *node = (*node)->left;
        free(q);
    }
    //左右子树均不为空
    else
    {
        pTreeNode q = *node; 
        pTreeNode s = q->right;
        //转向右子树，然后走左,走到没有左孩子的最左结点
        while (s->left)
        {
            q = s;
            s = s->left;
        }
        (*node)->data = s->data;  //s指向代替被删除结点的结点，即被删除结点的直接前驱或后继
        //q即s的双亲
        if (q != *node)  
        {
            q->left = s->right;      //重接左子树，s不存在左子树，因为是最左结点，但可能存在右子树
        }
        //q==*node 说明右子树只有一个结点
        else
        {
            q->right = s->right;   //重接右子树
        }
    }
}
//寻找删除结点
int deleteNode(pTreeNode* tree, int key)
{
    if (!(*tree)) return 0;
    if (key == (*tree)->data)
    {
        dele(tree);
    }
    else if (key < (*tree)->data)
    {
        return deleteNode(&(*tree)->left, key);
    }
    else
    {
        return deleteNode(&(*tree)->right, key);
    }
    return 1;
}

2.平衡二叉树

又称 AVL 树

定义：一棵平很二叉树可以是空树，或者是具有下列性质的二叉排序树：

• 左子树与右子树的高度之差的绝对值小于等于1
• 左子树和右子树也是平衡二叉排序树

因此给每个结点附加一个数字，给出该结点左子树与右子树的高度差，称这个数字为结点的平衡因子 (BF)

平衡因子 = 结点左子树的高度 - 结点右子树的高度

根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是 -1，0，或-1

2.1 失衡平衡二叉树

定义：如果在一棵 AVL 树中插入一个新结点后造成失衡 (即平衡因子不满足条件)，则必须重新调整树的结构，使之恢复平衡

最小不平衡子树：距离插入结点最近的，且以平衡因子的绝对值大于 1 的结点为根的子树，称为最小不平衡子树

四种失衡类型：

• LL型：当造成失衡的结点在发现者的左子树的左边时，称为 LL 型插入
• LR 型：当造成失衡的结点在发现者的左子树的右边时，称为 LR型插入
• RL型：当造成失衡的结点在发现者的右子树的左边时，称为 LR型插入
• RR型：当造成失衡的结点在发现者的右子树的右边时，称为 LR型插入

2.1.1 失衡平衡二叉树的分析与调整

失衡调整原则：

• 降低高度
• 维持二叉排序树性质

1. LL 调整
   
   对最小不平衡子树右旋
   

2. RR 调整
   
   对最小不平衡子树左旋，作为新的根结点的结点其原来的左子树在旋转后作为原来根结点的右子树连接
   

3. LR 型
   
   最小不平衡树的左孩子的右孩子作为新的根结点；原来根结点的左孩子作为左子树，原来的根结点作为右子树
   

4. RL 型
   
   
   最小不平衡子树的右孩子的左孩子作为新的根结点；原来根结点的右孩子作为右子树，原来的根结点作为左子树
   新的根结点对应的原结点的左孩子(即造成不平衡的那个结点)作为原根结点的右子树连接
   

3.多路查找树

其每个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。所有元素之间存在某种特定的排序关系

多路查找树的四种特殊形式：

• 2-3树
• 2-3-4树
• B树
• B+树

3.1 2-3树

其中的每一个结点都具有两个孩子 (称为2结点) 或三个孩子 (称为3结点)

• 一个 2 结点包含一个元素和两个孩子 (或没有孩子)。且左子树包含的元素小于该元素；右子树包含的元素大于该元素

• 一个 3 结点包含一小一大两个元素和三个孩子 (或没有孩子)。左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两者之间的元素

3.1.1 插入

插入的三种情况：

• 对于空树，插入结点即可
• 插入结点到一个 2 结点的叶子上，只需将其升级为3结点即可
• 插入结点到一个 3 结点上，因为3结点本身已经是2-3树的最大结点容量，因此需要拆分，且将树中两元素或插入的三者中选择其一向上移动一层

3.1.2 删除

删除的三种情况：

1. 删除元素位于 3结点上，直接删除即可，这样3结点会退为2结点

2. 所删除结点位于2结点上，此时不能直接删除，因为删除后2结点就只有一个孩子，不满足2-3树定义。此时需要分为四种情况：

   • 此结点的双亲也是2结点，且其双亲拥有一个3结点的右孩子，在删除节点后将其双亲及3结点左旋即可

   • 此结点双亲是2结点，且双亲结点的右孩子也是2结点，将根结点下移让右孩子成为3结点，再让比原来根结点元素稍大的元素成为根结点

   • 此结点的双亲是3结点，在删除后将双亲拆分成为两个2结点，较小的结点元素与左子树合并成为一个3结点。如果孩子全是3结点了，则较小的结点再次下移，再在对应位置插入

   • 如果当前树是一个满二叉树，此时删除任何一个叶子都会使得整棵树都不能满足2-3树的定义，此时需要向上合并出一些3结点，重新满足2-3树

3. 所删除的元素位于非叶子结点的分支结点，通常将树按中序遍历后得到此元素的前驱或后继，考虑使用它们来补位

3.2 2-3-4树

2-3树概念的扩展，包括了4结点的使用，一个4结点包含小中大三个元素和四个孩子(或没有)。

• 左子树包含小于最小元素的元素
• 第二子树包含大于最小元素，小于第二元素的元素
• 第三子树包含大于第二元素，小于最大元素的元素
• 右子树包含大于最大元素的元素。

3.3 B树

是一种平衡的多路查找树，2-3树和2-3-4树是其特例。结点最大的孩子数目称为B树的阶

一个m阶的B树具有如下属性：

• 如果根结点不是叶子结点，则其至少有两棵子树
• 每一个非根的分支结点都有 k-1 个元素和 k 个孩子，其中 [m/2]<=k<=m 。每一个叶子结点 n 都有 k-1 个元素，其中 [m/2]<=k<=m ( [m/2] 表示不小于 m/2 的最小整数 )
• 所有叶子结点都位于同一层次

3.4 B+树

一棵m阶的B+树和m阶的B树差异在于：

• 有 n 棵子树的结点中包含有 n 个关键字
• 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接
• 所有分支结点可以看成是索引，结点中仅含有其子树的最大 (或最小) 关键字

B+树的随机查找只是用来记录索引，而不提供实际记录的访问

散列表(哈希表)查找

散列表：记录的是存储位置与关键字之间存在的对应关系，根据关键字进行hash函数计算，计算出hashCode即存储位置

Locate( i ) = Hash( key )

eg：

优点：查询效率高

缺点：空间效率低

散列表术语：

1. 散列方法(杂凑法)：选取某个函数，根据该函数按关键码计算元素的存储位置，并按此存放；
   查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行对比，确认查找是否成功

2. 散列函数(杂凑函数)：散列方法中使用的转换函数

3. 散列表：根据散列方法构造的表

4. 散列冲突：不同的关键码映射到同一个散列地址；
   key != key，但 Hash(key) == Hash(key)

5. 同义词：具有相同hashCode的多个关键字

在散列查找中，散列冲突只能尽可能的减少

构造散列表需要解决的问题：

1. 构造好的散列函数

   • 所选函数尽可能简单，以便提高转换速度
   • 所选函数对关键码计算出的地址，应在散列地址集中均匀分布，减少空间浪费
2. 制定好的散列冲突解决方案
   查找时，如果从散列函数计算出的地址中查不到关键码，应当依据解决冲突的规则，有规律的查询其它相关单元

1. 散列函数的构造

构造散列函数需要考虑的因素：

• 执行速度(即计算hashCode所需时间)
• 关键字长度
• 散列表大小
• 关键字的分布情况
• 查找频率

1.1 常见构造方法

构造要求：

1. n个元素仅占用n个地址，使得散列的空间尽可能小
2. 均匀存放元素，减少散列冲突

有以下几个方法进行构造：

• 直接定址法
• 数字分析法
• 平方取中法
• 折叠法
• 除留余数法
• 随机数法

1.1.1直接定址法

Hash( key ) = a*key + b (a，b为常数)

优点：以关键码key的某个线性函数值为散列地址，不会产生冲突

缺点：占用连续地址空间，根据关键码可能会造成空间利用率低

1.1.2除留余数法

Hash( key ) = key mod p ( p为一个整数 )

选取 p 的技巧：设表长为 m，则取 p<=m，且p为素数

2.散列冲突解决方案

常用的处理冲突方法：

• 开放地址法
• 链地址法 (拉链法)
• 再散列法 (双散列函数法)
• 建立一个公共溢出区

2.1 开地址法

基本原理：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将关键码存入

有以下常用三种方法寻找空的散列地址：

• 线性探测法：d为1,2,3,4,… m-1 的线性序列
• 二次探测法 ：d为1，-1，2，-2 … q 的二次方序列
• 伪随机探测法：d 为 伪随机数

2.1.1 线性探测法

每次冲突后从1开始增加进行探测

查找时到相应位置去找，如果找不到就散列函数来探测，直到遍历完不存在或找到或遍历过程中出现空位置

2.1.2 二次探测法

+1，-1，+4，-4…

4k+3的质数可以保证探查不重复

2.1.3 伪随机探测法

2.2 链地址法

基本原理：将具有相同散列地址的记录 (同义词) 链成一条单链表，m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态结构。

eg：

单链表数目取决于 mod 的值，mod 13代表结果可以是从 0~13，所以需要13个单链表

链地址法创建散列表步骤：

1. 取关键字key，计算其hashCode，若该地址对应的表头为空，则将该元素插入此表头作为新链表；若不为空，则进行2解决冲突
2. 根据散列函数解决冲突的方法来计算key的存储地址，若该存储地址对应的表头的链表不为空，则将该key链接到对应链表上

链地址法优点：

• 非同义词不会冲突 ( 开地址法在探测时可能会遇到连续的被占用地址，又与要存入的key不是同义词 )，无聚集现象
• 链表结点动态申请，更适合于表长不确定的情况

3. 散列表的查找

给定查找值k，其查找过程为：

查找其实和散列过程一样emmmm

4.散列表查找效率分析

散列表的ASL取决于：

• 散列函数
• 处理冲突的方法
• 散列表的装填因子αα越大，说明表中记录数越多，表装得越慢，发生冲突的可能性越大，查找时比较次数就越多

总结

• 散列表有良好的平均查找性能
• 链地址法优于开地址法
• 除留余数法作散列函数优于其他方法做函数