数据结构_查找

1. 查找的基本概念

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

查找表(查找结构)：用于查找的数据集合称为查找表，它由同一类型的数据元素组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有4种：

①：查询某个特定的数据元素是否在查找表中；

②：检索满足条件的某个特定的数据元素的各种属性；

③：在查找表中插入一个数据元素；

④：从查找表中删除某个数据元素；

静态查找表：若一个查找表的操作只涉及上述操作的①和②，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态的插入或删除的查找表称为动态查找表。适合静态查找表的的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有二叉排序树的查找、散列查找等。二叉平衡树和B树都是二叉排序树的改进。

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

平均查找长度：在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为

其中，n 是查找表的长度； $P_{i}$ 是查找第 i 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 $P_{i}$ = 1/n； $C_{i}$ 是找到第 i 个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

2. 顺序查找和折半查找

2.1 顺序查找

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

2.1.1 一般线性表的顺序查找

作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定的条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

typedef struct  //查找表的数据结构
{
    ElemType *elem； //元素存储空间基址，建表时按实际长度分配，0号单元留空
    int TableLen；   //表的长度        
}SSTable；

int Search_Seq(SSTable ST，ElemType key)
{
    ST.elem[0]=key；  //哨兵
    for(i=ST.TableLen；ST.elem[i]！=key；--i)；   //从后往前找
    return i； //若表中不存在关键字为 key 的元素，将查找到 i 为 0 时退出 for 循环
}

//在上述的算法中，将ST.elem[0]=key称作哨兵。引入它的目的是使得 Search_Seq内循环不必判断数组是否越界，因为满足 i==0 时，循环一定会跳出。
这是因为初始化 ST.elem[0]=key ，当 i 减至 0 时，判断语句一定会成立。

对于 n 个元素的表，给定值 key 与表中第 i 个元素相等，即定位第 i 个元素时，需进行 n-i+1 次关键字的比较（之所以是 n-i+1 次，是因为算法规定从后往前进行查找，n-i 表示减去前面已经扫描过的关键字，+1 表示数组下标），即 $C_{i}$ = n – i + 1。查找成功时，顺序查找的平均长度为

当每个元素的查找概率相等，即 $P_{i}$ =1 / n 时，有

查找不成功时，与表中各关键字的比较次数显然是 n+1 次，从而顺序查找不成功的平均查找长度为 $ASL_{Default}$ = n + 1

通常，查找表中记录的查找概率并不相同。若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由大至小重新排列。

综上所述，顺序查找的缺点是当 n 较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储均可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。同时还需注意，对线性的链表只能进行顺序查找。

2.1.2 有序表的顺序查找

若在查找之前就已经知道表示关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为 key，当查找到第 i 个元素时，发现第 i 个元素对应的关键字小于 key，但第 i+1 个元素对应的关键字大于 key ，这时就可返回查找失败的信息，因为第 i 个元素之后的元素的关键字均大于 key ，所以表中不存在关键字为 key 的元素。

用下图的判定树来描述有序线性表的查找过程：
树中的圆形结点表示有序线性表中存在的元素；树中的矩形结点称为失败结点（若有 n 个结点，则相应的有 n+1 个查找失败的结点），它描述的是那些不在表中的数据值的集合。若查找到失败结点，则说明查找不成功。
在有序线性表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找结点一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下为
式中， $q_{j}$ 是到达第 j 个失败结点的概率，在相等查找概率的情形下，它为 1/(n+1)； $l_{j}$ 是第 j 个失败结点所在的层数。当 n = 6时，

2.2 折半查找

折半查找又称为二分查找，它是适用于有序的顺序表。（相信下C语言的学习中，已经学习过用二分法查找数组中某个元素了）

折半查找的基本思想：首先将给定值 key 与表中中间位置的元素进行比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分（例如，在查找表升序排列时，若给定值key大于中间元素，则所查找的元素只可能在后半部分）。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

int Binary_Search(SeqList 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
}

//接下来通过一个具体的二分查找来讲解二分查找具体的过程，我们分别查找11和32
int main()
{
	int arr[] = { 7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43 };//初始化数组，显然11不存在，32存在，我们规定：若找到，则返回对应数组的下角标；否则返回-1
	int sz = sizeof(arr) / sizeof(arr[0]);  //计算数组中所含元素的个数
	int i = 0;
	int k = 11;
	int l = 32;
	int left = 0; //对应二分查找，指向数组中第一个元素
	int right = sz - 1; //对应二分查找，指向数组最后一个元素，sz-1 是要以下标的方式进行表示
	while (left <= right)
	{
		int mid = (left + right) / 2; //定义二分查找的中间值
		if (arr[mid] > l) //中间值大于你要找的元素，意味着要找的元素位于前半部分
		{
			right = mid - 1; //修改右边界，缩小整体的范围
		}
		else if (arr[mid] < l) //中间值小于你要找的元素，意味着要找的元素位于后半部分
		{
			left = mid + 1; //修改左边界，缩小整体的范围
		}
		else //否则意味着随着范围的缩小，找到了所要找的值
		{
			printf("找到了，下角标为%d ", mid); //打印下角标，结束
			break;
		}
	}
	if (left > right)
	{
		return -1;
	}
	return 0;
}

折半查找的过程可用下图所示的二叉树来描述，称为判定树
树中，每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左孩子结点值，均小于其右孩子结点值。
若有序序列有 n 个元素，则对应的判定树有 n 个圆形的非叶结点和 n+1 个方形的叶结点。
显然，判定树是一个平衡二叉树（也就是任意结点的左孩子和右孩子的高度不超过1，或者是说平衡因子不超过1）。

由上述分析可知，用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时，查找成功的平均查找长度为

式中，h 是树的高度，并且元素个数为 n 时树高为 h = $log_{2}$ (n+1) 。所以，折半查找的时间复杂度为 O( $log_{2}$ n)，平均情况下比顺序查找的效率高。

因为折半查找需要方便的定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存取结构，且要求元素按关键字有序排列。

2.3 分块查找

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

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

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

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为 $L_{1}$ ， $L_{s}$ ，则分块查找的平均查找长度为

ASL= $L_{1}$ + $L_{s}$

将长度为 n 的查找表均匀的分为 b 块，每块有 s 个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为

2.4 相关练习

1. 顺序查找适合于存储结构为 顺序存储结构或链式存储结构 的线性表。

2. 对长度为 n 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为 (n+1)/2。

3. 树型查找

3.1 二叉排序树

3.1.1 二叉排序树的定义

二叉排序树也称为二叉查找树，或者是一颗空树，又或者是具有以下特性的二叉树：

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

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

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

根据对二叉树的定义，左子树结点值 < 根结点值 < 右子树结点值，所以对二叉树进行中序遍历，可以得到一个递增的有序序列。

3.1.2 二叉排序树的查找

算法思想：二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功；若不等，如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。

//二叉排序树的非递归查找算法

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;
}

举个例子：上图二叉排序树中查找4；首先 4 和根结点进行比较，4<6，去左子树查找，4和2进行比较，4>2，去右子树进行查找，查找成功；

3.1.3 二叉排序树的插入

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

插入结点的过程如下：若原二叉排序树为空，则直接插入结点；否则，若关键字 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;   //返回，插入成功
    }
    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)
    }
}

3.1.4 二叉排序树的构造

从一颗空树出发，依次输入元素，将它们插入到二叉排序树中的合适位置。设查找的关键字序列为{45,24,53,45,12,24}

//构造二叉排序树的算法

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

3.1.5 二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。

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

②：若结点 z 只有一个左子树或者右子树，则让 z 的子树成为 z 父结点的子树，代替 z 的位置。

③：若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）代替 z，然后从二叉排序树中删除这个直接前驱（或直接后继），转换成第一、第二种情况。

3.1.6 二叉排序树的查找效率分析

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

在等概率的情况下，图7.8 a 的查找成功的平均查找长度为

ASL=(1*1+2*2+3*4+4*3)/10=2.9

图 b 查找成功的平均查找长度为

ASL=(1+2+3+4+5+6+7+8+9+10)/10=5.5

当有序表是静态查找表时，宜用顺序表作为其存储结构，采用二分查找实现其查找操作；

若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

3.2 平衡二叉树

3.2.1 平衡二叉树的定义

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，保证任意结点的左、右子树高度差的绝对值不超过 1 ，将这样的二叉树称为平衡二叉树（Balanced Binary Tree），简称平衡树。定义结点左子树和右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只能是 -1、0 或 1。

平衡二叉树可定义为或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。结点中的值为该结点的平衡因子。

3.2.2 平衡二叉树的插入

二叉排序树保持平衡的基本思想如下：

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

注意：每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。归纳如下：

LL 平衡旋转（右单旋转）：

由于在结点 A 的左孩子 L 的左子树 L 上插入了新结点， A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去了平衡，需要一次向右的旋转操作。将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。

这里解释一下：
平衡因子由1变为2是因为原本只有A和B两个结点，在加入BL结点后，结点A的平衡因子由1变为2；
注意理解上图中的 而 B 的原右子树则作为 A 结点的左子树。

RR 平衡旋转（左单旋转）：

由于在结点 A 的右孩子 R 的右子树 R 上插入了新结点， A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去了平衡，需要一向左的旋转操作。将 A 的右孩子 B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树。

注意：LR 和 RL 旋转时，新结点究竟是插入 C 的左子树还是插入 C 的右子树不影响旋转过程。

LR 平衡旋转（先左后右双旋转）：

由于在 A 的左孩子 L 的右子树 R 上插入新结点， A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后把该C结点向右上旋转提升到/结点的位置。

RL 平衡旋转（先右后左旋转）：

由于在 A 的右孩子(R)的左子树(L)上插入新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后把该C结点向左上旋转提升到 A 结点的位置。

下面通过一个例子具体来看序列生成二叉树的例子：
假设关键字序列为{15，3，7，10，9，8}，首先插入 7 后导致不平衡，最小不平衡子树的根为 15 ，插入位置为其左孩子的右子树，执行 LR 旋转，先左后右双旋转；插入 9 后导致不平衡，最小不平衡子树的根为 15 ，插入位置为其左孩子的左子树，故执行 LL 旋转，右单旋转；插入 8 后导致不平衡，最小不平衡子树的根为 7，插入位置为其右孩子的左子树，执行 RL 旋转，先右后左双旋转；

3.2.3 平衡二叉树的删除

与平衡二叉树的插入操作类似，以删除结点 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 为根的子树进行平衡调整，如果调整后子树的高度减 1，则可能需要对 z 的祖先结点进行平衡调整，甚至回溯到根结点（导致树高减 1 ）

删除结点32：
由于结点32是叶子结点，所以直接删除即可，向上回溯到第一个不平衡结点44，即 z；
z 的高度最高的孩子结点为 78，即 y；
y 的高度最高的孩子结点为 50，即 x；
满足 RL 情况，先右后左双旋转；

3.2.4 平衡二叉树的查找

在查找过程中，与给定值进行比较的关键字个数不超过树的深度。假设以 $n_{h}$ 表示深度为 h 的平衡树中含有的最少结点数。

显然， $n_{0}$ =0， $n_{1}$ =1， $n_{2}$ =2……，并且有 $n_{h}$ = $n_{h-1}$ + $n_{h-2}$ +1。

含有 n 个结点的平衡二叉树的最大深度为 O(log2n)，平衡二叉树的平均查找长度为 O(log2n)；

4. 红黑树

4.1 红黑树的定义

为了保持 AVL 树的平衡性，插入和删除操作后，非常频繁地调整全树整体的拓扑结构，代价较大。为此在 AVL 树的平衡标准上进一步放宽条件，引入红黑树。

为什么要发明红黑树？
平衡二叉树的插入/删除很容易破坏 “平衡” 特性，需要频繁调整树的形态。比如说：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树，再进行LL/RR/LR/RL调整。
而红黑树的插入和删除很多时候不会破坏 “红黑” 特性，并不需要频繁的调整树的形态。即便需要调整，一般都可以在常数级时间内完成。

一棵红黑树是满足如下红黑性质的二叉排序树：
①：每个结点或是红色，或是黑色的。
②：根结点是黑色的。
③：叶结点（虚构的外部结点、NULL结点）都是黑色的。（注意：这里说的叶子结点不是最下面的结点，而是最下面的结点延伸出来的结点；比方说下图方框中表示的就是叶子结点）。
④：不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）。
⑤：对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。

为了便于对红黑树的实现和理解，引入 n+1 个外部结点，保证红黑树的每个结点的左孩子和右孩子均非空。

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

结论一：从根到叶结点的最长路径不大于最短路径的两倍。
结论二：有 n 个内部结点的红黑树的高度 h <= 2log2(n+1)。

4.2 红黑树的插入

红黑树插入新结点后需要进行调整（主要通过重新着色或旋转操作进行），以满足红黑树的性质。

结论三：新插入红黑树中的结点初始着为红色。

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

1. 用二叉查找树插入法插入，并将结点 z 着为红色。若结点 z 的父结点是黑色的，无须做任何调整，此时就是一棵标准的红黑树。

2. 如果结点 z 是根结点，将 z 着为黑色（树的黑高增加 1），结束。

3. 如果结点 z 不是根结点，并且 z 的父结点是红色的，则分为下面三种情况，区别在于 z 的叔结点 y 的颜色不同，因为 z 的父结点是红色的，插入之前树是合法的，爷结点必然存在且为黑色。

情况1：z 的叔结点（也就是父结点的兄弟结点）y 是黑色的，且 z 是一个右孩子。
情况2：z 的叔结点 y 是黑色的，且 z 是一个左孩子。
每棵子树 $T_{1}$ 、 $T_{2}$ 、 $T_{3}$ 和 $T_{4}$ 都有一个黑色根结点，且具有相同的黑高。
情况1（LR，先左旋，再右旋），即z是爷结点的左孩子的右孩子。先做一次左旋将此情形转变为情况2 （变为情况2后再做一次右旋），左旋后z和父结点z.p交换位置。
情况2（LL，右单旋），即z是爷结点的左孩子的左孩子。做一次右旋，并交换z的原父结点和原爷结点的颜色，就可以保持性质⑤，也不会改变树的黑高。这样，红黑树中也不再有连续两个红结点，结束。
若父结点是爷结点的右孩子，则还有两种对称的情况：RL（先右旋，再左旋）和 RR（右单旋）。

情况3：如果 x 的叔结点 y 是红色。
情况3（z 是左孩子或右孩子无影响），z的父结点z.p和叔结点y都是红色的，因为爷结点z.p.p是黑色的，将z.p和y都着为黑色，将z.p.p着为红色，以在局部保持性质④和⑤。然后，把z.p.p作为新结点z来重复循环，指针z在树中上移两层。
若父结点是爷结点的右孩子，还存在两种对称的情况。

下面举个例子，先后插入5，4，12：
插入5,为情况3,将5的父结点3和叔结点10着为黑色，将5的爷结点变为红色，此时因为7已是根，故着为黑色，树的黑高加1,结束。插入4,为情况1的对称情况（RL）,此时特别注意虚构黑色空叶结点的存在，先对5做右旋；转变为情况2的对称情况（RR）,交换3和4的颜色，再对3做左旋，结束。插入12,父结点是黑色的，无须任何调整，结束。

囊括所有红黑树插入可能的例子：（细细品）

4.3 红黑树的删除

删除操作和插入操作进行对比：

红黑树的插入操作容易导致连续的两个红结点，破坏性质④。而删除操作容易造成子树黑高的变化（删除黑结点会导致根结点到叶结点间的黑结点数量减少），破坏性质⑤。

删除过程也是先执行二叉查找树的删除方法。若待删结点有两个孩子，不能直接删除，而要找到该结点的中序后继（或前驱）填补，即右子树中最小的结点，然后转换为删除该后继结点。由于后继结点至多只有一个孩子，这样就转换为待删结点是叶结点或仅有一个孩子的情况。

最终，删除一个结点有以下两种情况：

待删结点没有孩子。
待删结点只有右子树或左子树。

1. 如果待删结点只有右子树或左子树，如下：

2. 如果待删结点没有孩子，若该结点是红色的，直接删除，无须做任何调整。

3. 如果待删结点没有孩子，并且该结点是黑色的。假设待删结点为y, x是用来替换y的结点（注意，当y是终端结点时，x是黑色的NULL结点）。删除y后将导致先前包含y的任何路径上的黑结点数量减1,因此y的任何祖先都不再满足性质⑤，简单的修正办法就是将替换y的结点x视为还有额外一重黑色，定义为双黑结点。也就是说，如果将任何包含结点x的路径上的黑结点数量加1,在此假设下，性质⑤得到满足，但破坏了性质①。于是，删除操作的任务就转化为将双黑结点恢复为普通结点。分以下四种情况：

情况一：x 的兄弟结点 w 是红色的。
        情况1, W必须有黑色左右孩子和父结点。交换W和父结点x.p的颜色，然后对x.p做一次左旋，而不会破坏红黑树的任何规则。现在，X的新兄弟结点是旋转之前W的某个孩子结点，其颜色为黑色，这样，就将情况1转换为情况2、3或4处理。
情况二：x 的兄弟结点 w 是黑色的， w 的左孩子是红色的，w 的右孩子是黑色的。
        情况2 （RL,先右旋，再左旋），即红结点是其爷结点的右孩子的左孩子。交换w和其左孩子的颜色，然后对w做一次右旋，而不破坏红黑树的任何性质。现在，x的新兄弟结点w的右孩子是红色的，这样就将情况2转换为了情况3。
情况三： x 的兄弟结点 w 是黑色的，且 w 的右孩子是红色的。
        情况3 （RR,左单旋），即红结点是其爷结点的右孩子的右孩子。交换w和父结点x.p的颜色，把w的右孩子着为黑色，并对x的父结点x.p做一次左旋，将x变为单重黑色，此时不再破坏红黑树的任何性质，结束。
情况四：x 的兄弟结点 w 是黑色的，且 w 的两个孩子结点都是黑色的。
        情况4中，因w也是黑色的，故可从x和w上去掉一重黑色，使得x只有一重黑色而w变为红色。为了补偿从x和w中去掉的一重黑色，把x的父结点x.p额外着一层黑色，以保持局部的黑高不变。通过将x.p作为新结点x来循环，x上升一层。如果是通过情况1进入情况4的，因为原来的x.p是红色的，将新结点x变为黑色，终止循环，结束。

归纳总结：在情况4中，因x的兄弟结点w及左右孩子都是黑色，可以从x和w中各提取一重黑色（以让x变为普通黑结点），不会破坏性质④，并把调整任务向上“推”给它们的父结点x.p。在情况1、2和3中，因为x的兄弟结点w或w左右孩子中有红结点，所以只能在x.p子树内用调整和重新着色的方式，且不能改变x原根结点的颜色（否则向上可能破坏性质④）。情况1虽然可能会转换为情况4,但因为新x的父结点x.p是红色的，所以执行一次情况4就会结束。情况1、2和3在各执行常数次的颜色改变和至多3次旋转后便终止，情况4是可能重复执行的唯一情况，每执行一次指针X上升一层，至多O（log2n）次。

下面举个例子，依次删除结点5和15：
删除5,用虚构的黑色NULL结点替换，视为双黑NULL结点，为情况1,交换兄弟结点12和父结点8的颜色，对8做一次左旋；转变为情况4,从双黑NULL结点和10中各提取一重黑色（提取后，双黑NULL结点变为普通NULL结点，图中省略，10变为红色），因原父结点8
是红色，故将8变为黑色，结束。删除15,为情况2的对称情况（LR）,交换8和10的颜色，对8做左旋；转变为情况2的对称情况（LL）,交换10和12的颜色（两者颜色一样，无变化），将10的左孩子8着为黑色，对12做右旋，结束。

4.4 相关练习

5. B 树和 B+ 树

5.1 B 树及其基本操作

B树，又称为多路平衡查找树，B树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 m 表示。一棵 m 阶 B树或为空树，或为满足如下特性的 m 叉树：

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

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

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

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

其中， $k_{i}$ 为结点的关键字，满足 $k_{1}$ < $k_{2}$ <…… $k_{n}$ ； $p_{i}$ 为指向子树根结点的指针，且指针 $p_{i-1}$ 所指子树中所有结点的关键字均小于 $k_{i}$ ， $p_{i}$ 所指子树中所有结点的关键字均大于 $k_{i}$ ，n 为结点中关键字的个数。

5. 所有的叶结点都出现在同一层次上，并且不带信息（可以认为这些结点不存在，指向这些结点的指针为空）。

B 树是所有结点的平衡因子均为 0 多路平衡查找树。

如下图所示为一个 5 阶 B 树，按照 B 树的定义，5 阶 B 树中所有结点的最大孩子数 m=5。
1. 结点的孩子个数等于该结点中关键字个数加1。
2. 如果根结点没有关键字就没有子树，此时B树为空；如果根结点有关键字，则其子树必然大于等于两棵，因为子树个数等于关键字个数加1。
3. 除根结点外的所有非终端结点至少有|m/2] =「5/2| 向上取整= 3棵子树（即至少m/2 – 1 = 5/2 – 1=2个关键字），至多有5棵子树（即至多有4个关键字）。
4. 结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。或者看成下层结点关键字总是落在由上层结点关键字所划分的区间内，如第二层最左结点的关键字划分成了 3个区间：（负无穷,5）, （5, 11）, （11,正无穷）,该结点3个指针所指子树的关键字均落在这3个区间内。
5. 所有叶结点均在第 4 层，代表查找失败的位置。

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

B树中的大部分操作所需的磁盘存取次数与 B 树的高度成正比。B树的高度不包括最后的不带任何信息的叶结点所处的那一层。

若 n $\geq$ 1，则对任意一棵包含 n 个关键字、高度为 h、阶数为 m的 B树：
高度的范围是：
logm(n+1) $\leq$ h $\leq$ log m/2向上取整为底的 ((n+1)/2)+1。
例如：假设一棵 3 阶 B 树共有 8 个关键字，则其高度为 2 $\leq$ h $\leq$ 3.17.

5.1.2 B 树的查找

在 B 树上进行查找与二叉排序树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。

B树的查找包含两个基本操作：①在B树中找结点；②在结点内找关键字。由于B树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。

在B树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找（例如，在下图中查找关键字42,首先从根结点开始，根结点只有一个关键字，且42 >22,若存在，必在关键字22的右边子树上，右孩子结点有两个关键字，而36 则若存在，必在36和45中间的子树上，在该子结点中查到关键字42,查找成功）。查找到叶结点时（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

5.1.3 B 树的插入

与二叉查找树的插入操作相比，B树的插入操作要复杂得多。在二叉查找树中，仅需查找到需插入的终端结点的位置。但是，在B 树中找到插入的位置后，并不能简单地将其添加到终端结点中，因为此时可能会导致整棵树不再满足 B 树定义中的要求。将关键字 key 插入B树的过程如下∶

1. 定位。利用前述的B树查找算法，找出插入该关键字的最低层中的某个非叶结点（在B树中查找key时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。注意：插入位置一定是最低层中的某个非叶结点）。
2. 插入。在 B 树中，每个非失败结点的关键字个数都在区间 [(m/2向上取整-1)，m-1] 内。插入后的结点关键字个数小于 m，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于 m-1 时，必须对结点进行分裂。
分裂的方法是：
取一个新结点，在插入key后的原结点，从中间位置（m/2 向上取整）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（m/2 向上取整）的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

定义比较抽象，我们拿例子具体来看：
对于 m=3 的 B树，所有结点中最多有 m-1=2 个关键字，若某结点中已有两个关键字，则结点已满，比如说下图a 根结点的右孩子。插入一个关键字 60 后，结点内的关键字个数超过了 m-1，此时需要对结点进行分裂；

5.1.4 B 树的删除

B 树的删除和插入面临这一个类似的问题。插入的时候，当结点中关键字的个数大于 m/2 时，需要对结点进行分裂；

同理，删除时，如果结点中关键字个数小于 m/2-1，会涉及合并的问题。

当被删关键字 k 不在终端结点（最低层非叶结点）中时，可以用 k 的前驱（或后继）k’ 来替代 k，然后在相应的结点中删除 k’，关键字 k 必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。在图7.30 的 4 阶 B 树中，删除关键字 80，用其前驱 78 替代，然后在终端结点中删除 78 。因此只需讨论删除终端结点中关键字的情形。

当被删除关键字在终端结点（最低层非叶结点）中时，有下列三种情况：
1. 直接删除关键字。若被删除关键字所在结点的关键字个数 $\geq$ m/2 向上取整，表明删除该关键字后仍满足 B 树的定义，则直接删去该关键字。 $\geq$ m/2 的意思是原本的下限是 m/2 向上取整 -1 ，此时删除一个结点，正好抵达下限，仍满足 B 树的定义；
2. 兄弟够借。若被删除关键字所在结点删除前的关键字个数=「m/2]-1,且与此结点相邻的右（或左）兄弟结点的关键字个数则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到新的平衡。
如下图，删除 4 阶 B树中的关键字65，右兄弟关键字个数 $\geq$ m/2 向上取整 = 2，将 71 取代原 65 的位置，将 74 调整到 71 的位置。
3. 兄弟不够借。若被删除关键字所在结点删除前的关键字个数=「m/2]- 1,且此时与该结点相邻的左、右兄弟结点的关键字个数均=「m/2]- 1,则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。
如下图，删除 4 阶 B 树的关键字 5，它及其右兄弟结点的关键字个数 = m / 2 向上取整 -1 = 1，故在 5 删除后将 60 合并到 65 结点中。

注意：关键字的个数范围为 m/2 向上取整-1 ——–> m/2 向上取整 ；其中 m 为 B树的阶数。

在合并过程中，双亲结点中的关键字个数会减 1。若其双亲结点是根结点且关键字个数减少至 0（根结点关键字个数为 1 时，有 2 棵子树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 m/2 向上取整 -2 ，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述操作，直至符合 B 树的要求为止。

5.2 B+ 树的基本概念

B+ 树是应数据库所需而出现的一种 B 树的变形树。

一棵 m 阶的 B+ 树需要满足：
1. 每个分支结点最多有 m 棵子树（孩子结点）。
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有 m/2 向上取整 棵子树。
3. 结点的子树个数和关键字个数相等。
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

m 阶的 B+ 树与 m 阶的 B 树的主要差异如下：
1. 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树;而在 B树中，具有n个关键字的结点含有n＋1棵子树。
2. 在B+树中，每个结点（非根内部结点）的关键字个数 n 的范围是 m/2 向上取整—>m；在 B 树中，每个结点（非根内部结点）的关键字个数 n 的范围是 m/2 向上取整-1 ——–> m-1；
3. 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4. 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的。

如下图是一棵 4 阶B+树。可以看出，分支结点的某个关键字是其子树中最大关键字的副本。通常在B+树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此，可以对 B+ 树进行两种查找运算：一种是最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。

5.3 相关练习

6. 散列表

6.1 散列表的基本概念

在之前，我们已经学习了线性表和数表的查找，记录在表中的位置与记录的关键字之间不存在确定关系，因此，在这些表中查找记录时需进行一系列的关键字比较。这类查找方法建立在“比较”的基础上，查找的效率取决于比较的次数。

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr (这里的地址可以是数组下标、索引或内存地址等)。（在学习C语言的文件管理过程中，曾经有提及散列表的概念，这里我们引用当时的例子，深入理解散列表：在C语言中，有一个关键字叫extern，我们都知道它是外部声明函数；也就是说采用模块式编程时，不需要在 .c 文件中都定义同一个变量；潇洒一点的说就是：我们在一个文件中定义该变量，其余文件使用到该变量时，直接extern外部声明即可，至于程序怎么找到这个变量，就是程序自己的事了；事实上，宏定义产生的变量都是存储在散列表中的，散列表中每个关键字对应确定的地址，extern外部声明时，会直接通过指针在散列表中找到外部声明的变量，这也是为什么可以在大量文件中迅速找到外部声明变量的原因；以上均是个人学习后的理解，如有问题，欢迎留言更正！）

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

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

理想情况下，对散列表进行查找的时间复杂度为0(1),即与表中元素的个数无关。

6.2 散列函数的构造方法

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

6.2.1 直接定址法

直接取关键字的某个线性函数值为散列地址，散列函数为

H(key) = key 或 H(key) = a * key + b

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

6.2.2 除留余数法

假定散列表表长为m，取一个不大于m但最接近或等于m的质数P，利用以下公式把关键字转换成散列地址。散列函数为

H(key) = key % p

除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

6.2.3 数字分析法

设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等;而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

6.2.4 平方取中法

顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

不同散列函数具有不同的性能；目标都是尽量降低产生冲突的可能性。

6.3 处理冲突的方法

应该注意到，任何设计出来的散列函数都不可能绝对地避免冲突。为此，必须考虑在发生冲突时应该如何处理，即为产生冲突的关键字寻找下一个”空”的 Hash 地址（也就是两个元素产生冲突，那么第二个就要去选择下一个空的 Hash 地址）。用 $H_{i}$ 表示处理冲突中第 i 次探测得到的散列地址，假设得到的另一个散列地址 $H_{1}$ ，仍然发生冲突，只得继续求下一个地址 $H_{2}$ ，以此类推，直到 $H_{k}$ 不发生冲突为止，则 $H_{k}$ 为关键字在表中的地址。

6.3.1 开放定址法

所谓开放定址法是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为

$H_{i}$ = (H(key)+ $d_{i}$ )%m

式中，H(key)为散列函数；i = 0,1,2,3,4,5，……k；m 表示散列表表长； $d_{i}$ 为增量序列；

1. 线性探测法：
        当 $d_{i}$ = 0,1,2,…，m-1时，称为线性探测法。这种方法的特点是：冲突发生时，顺序查看表中下一个单元(探测到表尾地址时，下一个探测地址是表首地址0),直到找出一个空闲单元(当表未填满时一定能找到一个空闲单元)或查遍全表。线性探测法可能使第 i个散列地址的同义词存入第 i+ 1个散列地址，这样本应存入第 i +1个散列地址的元素就争夺第 i + 2个散列地址的元素的地址……从而造成大量元素在相邻的散列地址上“聚集”(或堆积)起来,大大降低了查找效率；
2. 平方探测法：
        当a = $0^{2}$ ， $1^{2}$ ， $-1^{2}$ ， $2^{2}$ ， $-2^{2}$ …… $k^{2}$ ， $-k^{2}$ 时，称为平方探测法，其中散列表长度 m 必须是一个可以表示成 4k+3 的素数，又称二次探测法。平方探测法是一种处理冲突的较好方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
3. 双散列法：
        当 $d_{i}$ = $Hash_{2}$ (key)时，称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数 $Hash_{2}$ (key)计算该关键字的地址增量。它的具体散列函数形式如下：
$H_{i}$ = (H(key) + i * $Hash_{2}$ (key)) % m
初始探测位置 $H_{0}$ = H(key) % m。i 是冲突的次数，初始为0。在再散列法中，最多经过 m-1 次探测就会遍历表中所有位置，回到 $H_{0}$ 位置。
双散列法就是说：采用不只一个散列函数，一个散列函数无法解决冲突，就使用下一个散列函数，直到解决冲突为止；
4. 伪随机序列法：
        当 $d_{i}$ = 伪随机数序列时，称为伪随机序列法。
伪随机序列法就是说：给定一个随机数，按照这个随机数在散列表中进行存储。

注意：
在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记,进行逻辑删除。但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

6.3.2 拉链法（chaining）

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

例如上图：关键字序列为{19,14,23,01,68,20,84,27,55,11,10,79}；散列函数 H(key) = key % 13，用拉链法处理冲突，建立的表如上图；

6.4 散列查找及性能分析

散列表的查找过程与构造散列表的过程基本一致。对于一个给定的关键字key，根据散列函数可以计算出其散列地址，执行步骤如下：

初始化：Addr = Hash(key) ；
①：检测查找表中地址为 Addr 的位置上是否有记录，若无记录，返回查找失败；若有记录，比较它与 key 的值，若相等，则返回查找成功的标志，否则执行步骤②。
②：用给定的处理冲突方法计算 “下一散列地址” ，并把 Addr 置为此地址，转入步骤 ①。

例如：
关键字序列{19, 14, 23, 01,68,20, 84, 27, 55, 11, 10, 79}按散列函数 H(key) = key % 13 和线性探测处理冲突构造所得的散列表 L如下：
给定值 84 的查找过程：首先求得散列地址 H(84) = 6，因 L[6] 不空且 L[6] ≠ 84，则找第一次冲突处理后的地址 $H_{1}$ = (6+1) %16 = 7，而L[7]不空且 L[7] ≠ 84，则找第二次冲突处理后的地址 $H_{2}$ = (6+2) %16 = 8，L[8] 不空且 L[8] = 84，查找成功，返回记录在上表中的序号 8；
给定值 38 的查找过程：先求散列地址 H(38) = 12，L(12) 不空且 L[12] ≠ 38，则找下一地址 $H_{1}$ = (12+1) % 16 = 13，由于 L[13] 是空记录，故表中不存在关键字为 38 的记录。
查找各关键字的比较次数如下：
平均查找长度 ASL 为
ASL = (1*6+2+3*3+4+9)/12 = 2.5

从散列表的查找过程可见：

1. 虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于”冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量。

2. 散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

装填因子：散列表的装填因子一般记为a ,定义为一个表的装满程度，即

散列表的平均查找长度依赖于散列表的装填因子 a ，而不直接依赖于 n 或 m 。直观地看，a 越大，表示装填的记录越满，发生冲突的可能性越大，反之发生冲突的可能性越小。

6.5 相关练习

文章出处登录后可见！

已经登录？立即刷新