数据结构-查找

数据结构
发布日期:   2023-10-25
更新日期:   2023-11-03
文章字数:   9.7k

查找表的基本概念

  1. 查找：在数据集合中寻找满足某种条件的数据元素的过程叫查找。
  2. 查找表（查找结构）：用于查找的数据集合称为查找表，由同一类型的数据元素组成。
  3. 静态查找表：若查找表只涉及搜索和插入操作，无需动态的修改查找表，则称此类表为静态查找表。
  4. 关键字：数据元素中唯一标识该元素的某个数据项的值。
  5. 平均查找长度：在查找过程中，进行关键字比较次数的平均值，数学定义为：

$$
ASL=\sum_{i=1}^{n}P_iC_i
$$

n是查找表的长度；$P_i$是查找第i各数据元素的概率，一般认为每个数据元素的查找概率相等，即$P_i=\frac{1}{n}$；$C_i$是找到第i各元素所需进行的比较次数。

顺序查找和折半查找

顺序查找

顺序查找又称线性查找，它对于顺序表和链表都适用。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，可通过next来依次扫描每个元素。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找。

一般线性表的顺序查找

作为最直观的查找方法，基本思想就是从一端逐个检查关键字是否满足给定的条件。

算法实现：

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

//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0; ST.TableLen && ST.elem[i]!=key; ++i);
    
    //查找成功返回元素下标
    return i==ST.TableLen ? -1 : i;
}

ASL计算

对于有n各元素的表，给定值key与表中的第i各元素相等，即定位第i各元素时，需进行$n-i+1$次关键字的比较，即$C_i=n-i+1$。查找成功时，顺序查找的平均长度为
$$
ASL_{成功}=\sum_{i=1}^n P_i(n-i+1)
$$
当每个元素的查找概率相等，即$P_i=\frac{1}{n}$时，有
$$
ASL_{成功}=\sum_{i=1}^n P_i(n-i+1)=\frac{n+1}{2}
$$
上方式子实际也就是：
$$
ASL_{成功}=\sum_{i=1}^n P_i \frac{i}{n}=\frac{n+1}{2}
$$
若查找不成功时，与表中关键字比较的次数显然是n+1次，**即$ASL_{不成功}=n+1$**。

有序表的顺序查找

若在查找之前就知道表是有序的，则查找失败时可以不用再进行后序的遍历到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

设有一个表L[6]={7,13,19,29,37,43}，若要查找的key=21，当顺序查找到29时，$key=21<29$，因为表是顺序递增，所以就可以终止查找从而来增加查找效率。

1-1

根据上方表即可绘制出图1-1的查找树。

一个成功结点的查找长度=自身所在层数。

一个失败结点的查找长度=其父结点所在层数。

ASL计算

对于有n各元素的表，给定值key与表中的第i各元素相等，即定位第i各元素时，需进行$n-i+1$次关键字的比较，即$C_i=n-i+1$。查找成功时，顺序查找的平均长度为
$$
ASL_{成功}=\sum_{i=1}^n P_i \frac{i}{n}=\frac{n+1}{2}
$$
而若查找失败，设每次查找的概率相同，即$P_i=\frac{1}{n+1}$，则有
$$
ASL_{不成功}=\frac{1+2+3+\dots +n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}
$$

折半查找

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

折半查找的基本思想：首先将给定值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;	//查找失败
}

在折半查找判定树的构造中，如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等。

如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素。

折半查找的判定树中，若mid=[(low + high)/2]，则对于任何一个结点，必有：右子树结点数-左子树结点数=0或1

ASL计算

通过上方的折半查找判定树，设在等概率的情况下查找时，查找成功的查找平均长度为：
$$
ASL_{成功}=\frac{11+22+34+44}{11}=3
$$
树从上往下看，第一层元素进行一次对比，第二层元素进行两次对比，第三层元素进行四次对比，第四层元素也进行四次对比，从而再乘上概率得出ASL。

若查找失败，则有
$$
ASL_{失败}=\frac{34+48}{12}=\frac{11}{3}
$$
同样地树从上往下看，第三层失败进行了四次对比，第四层失败进行了八次对比，从而再乘上概率得出ASL。

折半查找的判定树中，只有最下面一层是不满的，因此可以通过平衡二叉树得元素个数为n时树高$h=[\log_2(n+1)]$。

从树高可得折半查找成功的$ASL\leqslant n$，同样的查找失败的$ASL\leqslant n$。

从而在查找等概率情况下有查找成功的平均长度为
$$
ASL=\frac{1}{n}(1\times 1 + 2\times 2 + \dots + h \times 2^{h-1})= \frac{n+1}{2}\log_2(n+1)-1\approx \log_2(n+1)-1
$$

分块查找

分块查找的基本思想：将查找表分为若干子块。块内的元素可以无序，但块间的元素是有序的，即第一块中的最大关键字小于第二块中的所有记录的关键字，第二个块中的最大关键字小于第三块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

例：

1-2

在图中将要查找的表进行分块，然后取出每个块中最大的元素。然后依次来将要查找的关键字和每个块中的最大元素进行比较。按顺序查找，若关键字大于当前块中最大的元素，则往后与下一个块的最大元素进行比较，直到关键字小于等于块的最大元素。

然后再到分块中进行顺序查找，直到找到相匹配的关键字，若找不到则为查找失败。

若在分块查找中使用折半查找，有可能会出现low>high，而当前查找元素却存在于分块的元素中，就有可能出现查找错误。

例：

1-3

此时上方折半查找low==high==mid，由于key<mid，所以按照折半查找的规则会让high--，导致成图1-4的结果，此时就会判定为查找失败。

1-4

然而查找元素就在20的分块中，所以需要而外的查找，每当索引表最终停在low>high时，要在low所指分块中查找（因为此时只有low所指向的分块中key<mid，所以要是能查找到必定是在low所指向的分块中）。

1-5

ASL计算

设索引查找和块内查找的平均查找长度分别为$L_1,L_S$，则分块查找的平均查找长度为
$$
ASL=L_1+L_S
$$
将长度为n的查找表均匀地分为b块，每块有s个记录，在等概率情况下，若在块内和索引表中均用顺序查找，则平均查找长度为
$$
L_1=\sum_{i=1}^b \frac{i}{b}= \frac{b+1}{2}\
L_1=\sum_{i=1}^s \frac{i}{s}= \frac{s+1}{2}\
ASL= \frac{b+1}{2} + \frac{s+1}{2}
$$
而基于查找表为b，每块记录为s，可得长度$n=sb$，则有$b=\frac{n}{s}$，带入到ASL的式子中，有
$$
ASL=\frac{s^2+2s+n}{2s}
$$
当$s=\sqrt{n}$（可用求导求最值证明），则平均查找长度取最小值$\sqrt{n}+1$。

树型查找

二叉排序树（BST）

构造一棵二叉排序树的目的并不是为了排序，而是为了提高查找、插入和删除关键字的速度，二叉排序树这种非线性结构也有利于插入和删除的实现。

二叉排序树的特性：

  1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
  2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
  3. 左、右子树也分别是一颗二叉排序树。

对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树的查找

查找是从根节点开始，然后沿某个分支逐层向下比较。

二叉排序树查找实现

//二叉排序树数据结构
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;

//二叉排序树查找
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 = (BiTree)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)			//关键字小于当前结点的值，递归插入到左子树中
        return BST_Insert(T->lchild,k);
    else 							//关键字大于当前结点的值，递归插入到右子树中
        return BST_Insert(T->rchild,k);
}
二叉排序树的构造

从一棵空树出发，一次输入元素并将他们插入到二叉排序树中的合适位置。、

二叉排序树插入实现

//T为要构造的树 str为元素  n为元素的个数
void Creat_BST(BiTree &T, KeyType str[], int n){
    T = NULL;		//初始时T为空树
    int i = 0;
    while(i < n){	//一次将关键字插入到二叉排序中
        BST_Insert(T,str[i]);
        i++;
    }
}

例：

若按照序列str={50,66,60,26,21,30,70,68}建立BST，得图2-1：

2-1

而若按照序列str={26,21,30,50,60,66,68,70}建立BST，得图2-2：

2-2

二叉排序树的删除

在二叉排序中删除一个结点，若该结点有子树，则需要把被删除结点从存储二叉排序树的链表上摘下，后再删除结点并再和原先树连接起来。

删除操作的实现有3种情况：

  1. 若被删除结点为叶结点，直接删除。
  2. 若结点z只有一棵左子树或右子树，则让z的子树称为z父结点的子树，代替z的位置。
  3. 若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树种删除这个直接后继（或直接前驱），转换成第一或第二种情况。

例（讨论第三种情况）：

2-3

图2-3中若要删除z结点，则以直接后继来替代z，则需要右子树中值为最小的数，即右子树通过中序遍历（二叉排序数可通过中序遍历来获得一个递增的有序序列）可得结点p为最小值。所以以p来替换z的位置，后再填补上p的位置，可得结果图2-4。

2-4

而若使用直接前驱来替换z结点的话，则需要通过中序遍历获得左子树中最大的结点，后再替换z再进行同样的操作，可得图2-5

2-5

二叉排序树查找效率分析

二叉排序的查找效率，主要取决于树的高度。若二叉排序树左右子树的高度之差的绝对值不超过1，它的平均查找长度为$O(\log_2n)$。若二叉排序树是一个只有右（左）子树的单支树，则其平均查找长度为$O(n)$。

平衡二叉树（AVL）

平衡二叉树就是保证任意结点的左、右子树高度差的绝对值不超过1。

在此定义结点左子树与右子树的高度差为该结点的平衡因子，结点的平衡因子=左子树高-右子树高，所以平衡二叉树结点的平衡因子的值只可能是-1、0或1.

平衡二叉树的结构

typedef struct AVLNode{
    int key;		//数据域
    int balance;	//平衡因子
    struct AVLNode *lchild,*rchild;
}AVLNode, *AVLTree;
平衡二叉树的插入

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

注：每次调整的对象都是离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。

平衡二叉树在调整时可归纳为下列四种情况：

LL平衡旋转（右单旋转）：由于在结点A的左孩子（L）的左子树（L）上插入了新结点，导致A的平衡因子由1增长到2，导致以A为根的子树失去平衡，需要进行一次右转操作来重新保持平衡。

2-6

右旋即让图2-6中B称为根节点，A成B的右子结点，而B的原右子树则作为A结点的左子树。（$AR>A>BR>B>BL$）

2-7

RR平衡旋转（左单旋转）：由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2。导致以A为根的子树失去平衡，需要进行一次向左旋转操作。

2-8

左旋即让B成为根结点，A结点成为B的左子树根节点，而B的原左子树则作为A结点的右子树。（$BR>B>BL>A>AL$）

2-9

LR平衡旋转（先左后右双旋转）：由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。

2-10

假设BR为结点C，设新结点插入到C结点的右子树中，先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把C结点向右上旋转提升到A的位置，如图2-11所示。（BL<B<CL<C<CR<A<AR）

2-11

RL平衡旋转（先右后左双旋转）：由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。

2-12

假设BL为结点C，设新结点插入到C结点的左子树中（左右的结果都是相同），先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把C结点向左上旋转提升到A的位置。（AL<A<CL<C<CR<B<BR）

查找效率分析

若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找插座的时间复杂度不可能超过O(h)。

由于平衡二叉树的左子树和右子树高度之差不超过1。

假设$n_h$表示深度为h平衡树中含有最少结点树。

则高度为h的结点数量$n_h=n_{h-1}+n_{h-2}+1$，基于这公式可得树最大高度$h_{max}=O(\log_2n)$，即为平衡二叉树的平均查找长度。

.

平衡二叉树的删除

平衡二叉树的删除有以下几个步骤（以删除结点w为例）：

  1. 用二叉排序树的方法对结点w执行删除操作。
  2. 若导致了不平衡，则从结点w向上开始回溯，找到第一个不平衡的结点z（即最小不平衡子树）；y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点。
  3. 然后对以z为根的子树进行平衡调整，其中x、y和z可能的位置有四种情况：
  • y是z的左孩子，x是y的左孩子（LL，右单旋转）；
  • y是z的左孩子，x是y的右孩子（LR，先左后右旋转）；
  • y是z的右孩子，x是y的右孩子（RR，左单旋转）；
  • y是z的右孩子，x是y的左孩子（RL，先右后左旋转）；

四种情况操作基本和插入操作调整方式一样。不同之处在于，插入仅需要对z以根的子树进行平衡调整；则删除操作需要，先对以z为根的子树进行平衡调整，如果调整后以后上方二叉树中存在不平衡，则需要对z的祖先结点进行平衡调整。

例：

2-13

若要删除图2-13的第32位置的结点，会导致第44位置的结点成为最小不平衡子树，需要对44位置的结点进行平衡调整，将50结点先右旋到78结点位置再左旋到50位置即可成功调整会平衡二叉树。

2-14

而此时又导致了33结点出现的不平衡，所以需要再对33结点进行平衡调整。在33结点的子树中找到高度最高的孩子10结点，然后再找到高度最高的孙结点20。对20结点进行左旋后右旋就可以再次调整回平衡二叉树。

2-15

红黑树（Red-Black Tree,RBT）

红黑树的定义

为了保持AVL树的平衡性，插入和删除操作需要频繁地调整树的拓扑结构，代价较大，所以引入了红黑树。

一棵红黑树，如图2-16，是满足如下红黑性质的二叉排序树（$左子树结点值\leqslant 根结点值 \leqslant 右子树结点值$）：

  1. 每个结点是红色或黑色。
  2. 根结点是黑色的。
  3. 叶结点（虚构的外部结点、NULL结点）都是黑色的。
  4. 不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）。
  5. 对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。

2-16

从某结点出发（不含该结点）到达一个叶结点的任意一个简单路径上的黑结点总数称为该结点的黑高（记为bh），根节点的黑高称为红黑树的黑高。

根据性质可得出结论：

结论1：从根到叶结点的最长路径不大于最短路径的2倍。

结论2：有n个内部结点的红黑树的高度$h\leqslant 2\log_2(n+1)$，即查找操作时间复杂度为$O(log_2n)$

红黑树的查找

与BST、AVL相同，从根出发，左小右大，若查找到空叶结点，则查找失败。

红黑树的插入

红黑树的插入过程和二叉查找树的过程基本类似，不同在于红黑树中插入新结点后需要调整（通过重新着色或旋转操作），以满足红黑树的性质。

若新节点是根结点染为黑色，若是非根染为红色。

设结点z为新插入的结点。插入过程如下：

  1. 用二叉查找树插入法插入，并将结点z染为红色。若结点z的父节点是黑色，无须做任何调整，此时就是标准的红黑树。
  2. 如果z结点的父节点z.p是红色，则分为三种情况，区别在于z的叔结点y（父节点的兄弟结点）的颜色不同，因父节点z.p为红色，所以爷结点z.p.p必然为黑色。所以分情况需要进行旋转或染色：

若叔结点为黑色，需要旋转加染色。

  • LL型：右单旋，父换爷+染色。
  • RR型：左单旋，父换爷+染色。
  • LR型：左、右双旋，儿换爷+染色。
  • RL型：右、左双旋，儿换爷+染色。

若叔结点为红色，需要把叔结点、父结点、爷结点都染色（即红变黑，黑变红），再把爷结点视为新结点，以新节点给规则再做判断。

叔父爷染色，爷变为新结点。

例：

2-14

在图2-14再插入结点5，先染为红色，再看父节点10的兄弟结点为黑色，且新插入的结点为LL型（即插入到爷结点的左孩子的左孩子中）。

2-15

对于LL型处理方法：需要进行右单旋，父结点和爷结点交换并染色。

2-16

然后最后再把10结点染为黑色，20结点染为红色，如图2-17。

2-17

红黑树的删除

红黑树的插入操作容易导致连续的两个红结点，会导致破环红黑树的性质。而删除操作容易造成子树黑高的变化，导致从一个结点到任意叶结点的简单路径上，黑结点数量不同。（后续再补充）

B树和B+树

B树及其基本操作

所谓m阶B树是所有结点的平衡因子均等于0的m路平衡查找树。

一颗m阶B树或为空树，或为满足如下特性的m叉树：

  1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字。

  2. 若根结点不是叶结点，则至少有两棵子树。

  3. 除根结点外的所有非叶结点至少有[m/2]棵子树，即至少含有[m/2]-1个关键字。

  4. 所有非叶结点的结构如下：

    3-1

    其中，Ki(i=1,2,…,n)为结点关键字，且满足$K1<K2<\dots<Kn$；Pi(i = 0,1,…,n)为指向子树根结点的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki，Pi所指子树中所有结点的关键字均大于Ki，n（$[m/2]-1\leqslant n\leqslant m-1$）为结点中关键字的个数。

  5. 所有的叶结点都出现再同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点）。

3-2

B树的高度（磁盘存取次数）

设B树的高度不包括最后的不带任何信息的叶结点所处的那一层，若$n\geqslant 1$，则对任何一棵包含n个关键字、高度为h、阶数为m的B树：

  1. 因为B树种每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足$n\leq (m-1)(1+m+m^2+\dots +m^{h-1})=m^h-1$，因此有
    $$
    h\geq \log_m(n+1)
    $$

  2. 若让每个结点中的关键字个数最少，则容纳同样多关键字的B树的高度达到最大。第一层至少有1个结点；第二层至少有2个结点；除根节点外的每个非叶结点至少有[m/2]棵子树，则第三层至少有2[m/2]个结点……..第h+1层至少有$2([m/2])^{h-1}$个结点，注意到第h+1层是不包含任何信息的叶结点。对于关键字个数为n的B树，叶结点的个数为n+1，由此有$n+1\geq 2([m-2])^{h-1}$，即$h\leq \log_{[m/2]}((n+1)/2)+1$。

B树的插入

B树的插入有以下步骤：

  1. 定位。利用B树的查找算法（查找和二叉查找树基本一致），找出插入该关键字的最底层中的某个非叶结点（在B树种查找key时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的位置。注意：插入位置一定是最底层中的某个非叶结点）。
  2. 插入。在B树种，每个非失败结点的关键字个数都在区间$[[m/2]-1,m-1]$内。插入后的关键字个数小于m，可直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于m-1时，必须对结点进行分裂。

分裂的方法是：取一个新结点，在插入key后原结点中，右部分包含的关键字放到新结点中，中间位置([m/2])的结点插入原结点的父节点。若此时导致父节点关键字个数也超过上限，则继续分裂操作。

例：

在5阶B树中，如图3-3，已经插入{25,38,49,60}，后再想插入80，则要进行分裂操作。

3-3

3-4

如图3-4所示中间49关键字为第[m/2]个结点就作为原结点的父节点，右结点包含的关键字就放到新结点中。

再一个例子：

3-5

若在图3-5中插入75则会导致需要B树在此进行分裂，此时就应该将73关键字放到父节点中。

3-6

此时就会导致父节点的关键字也超过了m-1个，需要再次进行分裂。

3-7

最后就会让第[m/2]个关键字成为根结点中唯一的关键字。

B树的删除

B树的删除要使删除后的结点中的$关键字个数\geq [m/2]-1$，因此将涉及结点的合并问题。

当被删关键字k不在终端结点（最底层的非叶结点）中时，可以用k的前驱（或后继）k’来替代k，然后在相应的结点中删除k’，关键字k’必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。

例：

3-8

若要删除80，则需要用直接前驱或直接后继来替代80的位置，此时80的直接前驱为77，所以就用77来替代80。

3-9

此时就把非终端结点删除转换成了对终端节点的删除操作（直接后继同理）。

当被删关键字在终端结点中时，有下列三种情况：

  1. 直接删除关键字。若被删关键字所在结点的$关键字个数\geq [m/2]$，表明删除该关键字后仍满足B树的定义，则直接删去该关键字。

  2. 兄弟够借。若被删关键字所在结点删除前的关键字个数=[m/2]-1，且与该结点相邻的右（或左）兄弟结点的关键字个数$\geq[m/2]$，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到平衡。

    例：

    3-10

    若要删除图3-10的第38个关键字。此时会导致结点低于下限[m/2]，所以需要向兄弟结点借关键字，但不能直接将70移到38所在的结点中，会导致不满足B树的定义，所以需要将父结点的49移到38所在的结点中，再将70移到父节点中，就会产生下图3-11。

    3-11

    此时再次满足B树的定义。

  3. 兄弟不够借。若被删关键字所在结点删除前的关键字个数=[m/2]-1，且此时该结点与相邻的左、右兄弟结点的关键字个数均=[m/2]-1，则将关键字删除后和左（或右）兄弟结点及双亲结点中的关键字进行合并。

例：

3-12

若要删除图3-12中4+关键字，会导致49所在结点结点个数小于[m/2]，而此时右兄弟同样关键字也不够填补，则需要进行合并操作，即将右兄弟结点合并，并将父节点中所指向这两结点的关键字一并合并到其中，如图3-13。

3-13

而此时又导致父节点的关键字也不满足B树的定义，则需要对父节点也进行合并，即得到图3-14。

3-14

此时根结点中没有任何关键字，则可进行删除，得到最终结果：

3-15

B+树的基本概念

B+树是应数据库所需而出现的一种B树的变形树，如图3-16。

一棵m阶的B+树需满足下列条件：

  1. 每个分支结点最多有m棵子树（孩子结点）。
  2. 非叶根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树。
  3. 结点的子树个数与关键字个数相等。
  4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互连接起来（支持顺序查找）。
  5. 所有分支结点（可视为索引的索引）中包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子节点的指针。

3-16

m阶的B+树和m阶的B树的主要差异：

  1. 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树种，具有n个关键字的结点含有n+1棵子树。
  2. 在B+树中，每个结点的关键字个数n的范围是$[m/2]\leq n \leq m(而根结点:1\leq n\leq m)$；而在B树种，每个结点（非根内部结点）的关键字个数n的范围是$[m/2]-1\leq n \leq m-1(根结点:1\leq n \leq m-1)$。
  3. 在B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中；而在B树中，最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
  4. 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用。而在B树中，叶结点和非叶结点均包含信息。

散列表

散列表的基本概念

散列表（哈希表， Hash Table）：是一种可以根据数据元素的关键字计算出它在散列表的存储地址。

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

例：

4-1

若想将19、14、23插入到散列表中，需要将值代入到散列函数，即19%13=6插入到6的位置，14%13=1插入到1的位置，23%13=10插入到10的位置。

4-2

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这样发生碰撞的不同关键字称为同义词。

散列函数的构造方法

在构造散列函数时（核心目标：尽量减少冲突），需注意以下几点：

  1. 散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
  2. 散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。
  3. 散列函数应尽量简单，能够在较短的时间内计算出任意一个关键字对应的散列地址。
常用的散列函数构造方法

除留余数法—H（key）= key % p：

设散列表表长为m，取一个不大于m但最接近或等于m的质数p

注：质数又称素数。指除了1和此整数自身外，不能被其他自然数整除的数。

适用场景：关键字是整数即可。

直接定址法—H（key）= key 或 H（key）= a*key + b：

其中，a和b是常数。这种方法计算最简单，且不会产生冲突。若关键字分布不连续，空位较多，则会造成存储空间的浪费。

适用场景：关键字分布基本连续。

数字分析法—选取数码分布较为均匀的若干位作为散列地址

设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选区数码分布较为均匀的若干位作为散列地址。

适用场景：关键字集合已知，且关键字的某几个数码位分布均匀

平方取中法—取关键字的平方值的中间几位作为散列地址

这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀。

适用场景：关键字的每位取值都不够均匀。

散列表处理冲突的方法

拉链法（链接法，chaining）

把所有“同义词”存储在一个链表中。

散列表（拉链法解决冲突）插入一个新元素：

  1. 结合散列函数计算新元素的散列地址。
  2. 将新元素插入散列地址对应的链表（可用头插法，也可用尾插法）。

例：

若散列表长度为13，散列函数H（key） = key % 13，当列表中已经插入14,19,23。

4-3

而此时若想再插入1时，必定会和14冲突。所以则需要将14和1以链表形式连接（默认使用头插法）。

4-4

根据拉链法，再将{68,20,84,27,55,11,10,79}都插入到散列表中，即有：

4-5

散列表拉链法查找操作

若以图4-5来查找27，则会先通过散列函数H（key） = key % 13来搜寻到目标元素存储地址：27%13=1，后再通过链表来搜寻到目标元素。

4-6

删除和查找操作几乎相同就不再赘述。

开放地址法

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

如果发生“冲突”，就给新元素找另一个空闲位置。发生第i次冲突时，数学递推公式：
$$
H_i=(H(key)+d_i)%m
$$
$H_i$：发生第i次冲突时的散列地址；H(key)：初始散列地址；$d_i$：偏移量；m：散列表表长。（**注：$0\leq i \leq m-1 $**）

四种常用构造探测序列$d_i$的方法：

  1. 线性探测法

    线性探测法就是按从左到右的顺序进行探测，当个发生冲突时，顺序查看表中下一个单元（探测到表尾m-1时，下一个探测地址是表首0），直到找到一个空闲单元。

    例：

    4-7

    图4-7中若根据散列函数$H(key)=key%13$，插入元素1为第地址1的位置，此时和14冲突，根据线性探测法从左往右查找到4号地址为空闲，则插入到4号地址中。

  2. 平方探测法

    当$d_i=0^2,1^2,-1^2,\dots,k^2,-k^2$时，称为平方探测法，其中$k\leq m/2$，散列表长度m必须是一个可以表示成4k+3的素数，又称二次探测法。

    例：

    4-8

    根据散列函数$H(key)=key%13$，插入元素1为第地址1的位置，此时和14冲突，根据平方探测法（以此时要查找的单元为基准进行探测），先探测$1^2$位置，有元素2，则探测$-1^2$的位置，有元素13，后再探测$2^2$，为空单元，则将元素1放入其中。

  3. 双散列法

    当$d_i=Hash_2(key)$时，称为双散列法。需要使用两个散列函数，当通过第一个散列函数$H(key)$发生冲突时，则利用第二个散列函数$Hash_2(key)$计算该关键字的地址增量。具体形式如下：
    $$
    H_i=(H(key)+i\times Hash_2(key))% m
    $$

  4. 伪随机序列法

​ 当$d_i=伪随机数序列$时，称为伪随机法，伪随机序列为人为设计的序列。

注：在开放定址的情况下，删除元素应该逻辑删除，而非物理删除，即删除一个元素可给flag来标记已经删除，而真实物理内存中并没有删除此元素，以至于下次查找不会出错。

文章作者: LsWorld
文章链接: http://example.com/2023/10/25/shu-ju-jie-gou-cha-zhao/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 LsWorld !
数据结构
评论
  目录