7.1 查找的概念

问题：在哪找？

——查找表

查找表是由同一类型的数据元素（或纪律）构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构

什么是查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）

关键字：用来标识一个数据元素（或记录）的某个数据项的值

• 主关键字：可唯一地标识一个记录的关键字是主关键字
• 次关键字：反之，用以识别若干记录的关键字是次关键字

查找表可分为两类：

• 静态查找表：仅作“查询”（检索）操作的查找表
• 动态查找表：作“插入”和“删除”操作的查找表

查找算法的评价指标：关键字的平均比较次数，也称平均查找长度 ASL（Average Search Length）

• n：记录的个数
• pi：查找的第 i 个记录的阿概率（通常认为pi=1/n）
• ci：找到第 i 个记录所需的比较次数

7.2 线性表的查找

7.2.1 顺序查找

应用范围：

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

顺序表的表示：

数据元素类型定义：

typedef struct {
	keyType key;	// 关键字
	// 其他数据域
} ElemType;

typedef struct {
	ElemType* elem;		// 存储空间基址
	int length;			// 当前长度
} SequenSearchList;

举例：

/*******************************************************************************************************************************
 * @description：顺序查找
 * @param：list
 * @param：key
 * @return：找到返回下标，没找到返回0
 */
int searchSequenList(SequenSearchList list, keyType key)
{
	for (int i = list.length; i >= 1; --i) {
		if (list.elem[i].key == key) {
			return i;
		}
	}
	return 0;
}

改进：把待查关键字存入表头（“哨兵”、“监视哨”），从后面逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度

• 时间复杂度：O(n)
• ASL(n) = (n+1)/2
• 空间复杂度：一个辅助空间 O(1)

优点：算法简单，逻辑次序无要求，且不同存储结构均适用

缺点：ASL太长，时间效率太低

7.2.2 折半查找

每次将待查记录所在区间缩小一半

非递归算法

• 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值
• 初始时，令low=1，high=n，mid=(low + high) / 2
• 让k与mid指向的记录比较

• 若list.elem[mid].key == key，查找成功
• 若list.elem[mid].key > key，则high = mid - 1
• 若list.elem[mid].key < key，则low = mid + 1

• 重复上述操作，直至low>high时，查找失败

/*******************************************************************************************************************************
 * @description：折半查找
 * @param：list
 * @param：key
 * @return：
 */
int binarySearchList(SequenSearchList list, keyType key)
{
	int low = 1;
	int high = list.length;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (list.elem[mid].key == key) {
			return mid;
		}
		else if (list.elem[mid].key > key) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	return 0;
}

递归算法

/*******************************************************************************************************************************
 * @description：折半查找--递归算法
 * @param：list
 * @param：key
 * @param：low
 * @param：high
 * @return：找到返回下标，没找到返回0
 */
int binarySearchList_recursion(SequenSearchList list, keyType key, int low, int high)
{
	if (low > high) {
		return 0;
	}
	int mid = (low + high) / 2;
	if (list.elem[mid].key == key) {
		return mid;	// 递归出口
	}
	else if (list.elem[mid].key > key) {
		return binarySearchList_recursion(list, key, low, mid - 1);
	}
	else {
		return binarySearchList_recursion(list, key, mid + 1, high);
	}
}

判定树

折半查找优缺点：

• 优点：效率比顺序查找高，时间复杂度为 O(logn) ASL=log(2, n+1)
• 缺点：只适用于有序表，且受限于顺序存储结构（对线性表无效）

7.2.3 分块查找

条件：

1. 将表分成几块，且表或者有序，或者分块有序，若 i < j，则第j块中所有记录的关键字均大于第 i 块中的最大关键字
2. 建立“索引表”（每个结点含有最大关键字字域和指向本块第一个结点的指针，且按关键字有序）

性能分析

• 优点：插入和删除比较容易，无需进行大量移动
• 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算
• 适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找

7.2.4 三种查找比较

7.3 树表的查找

当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。

改用动态查找表——几种特殊的树

• 二叉排序树
• 平衡二叉树
• 红黑树
• B-树
• B+树
• 键树

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

7.3.1 二叉排序树

二叉排序树（Binary Sort Tree）又称二叉搜索树、二叉查找树

定义：二叉排序树或是空树，或是满足如下性质的二叉树：

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

对二叉排序树中序遍历会的到一个递增序列

存储结构

typedef int keyType;

typedef struct {
	keyType key;	// 关键字域
	// InfoType otherInfo;	// 其他数据域
} elemType;


typedef struct node {
	elemType data;	// 数据域
	struct node* leftChild, * righrChild;	// 左右孩子指针
} BSTNode, * BSTree;

查找

算法思想：

1. 若二叉排序树为空，则查找失败，返回空指针
2. 若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：

1. 若key等于T->data.key,则查找成功，返回根结点地址
2. 若key小于T->data.key,则进一步查找左子树
3. 若key大于T->data.key,则进一步查找右子树

/*******************************************************************************************************************************
 * @description：二叉排序树的查找算法
 * @param：T
 * @param：key
 * @return：
 */
BSTree BSTSearch(BSTree T, keyType key) {
	if (T == NULL) {
		return NULL;
	}
	else if (key == T->data.key) {
		return T;
	}
	else if (key < T->data.key) {
		return BSTSearch(T->leftChild, key);
	}
	else {
		return BSTSearch(T->righrChild, key);
	}
}

查找分析

问题：如何提高形态不均衡的二叉排序树的查找效率

解决方法：做“平衡化”处理，即尽量让二叉树的形状均衡

插入

• 若二叉排序树为空，则插入结点作为根结点插入到空树中
• 否则，继续在其左、右子树上查找

• 树中已有，不再插入
• 树中没有

• 查找直至某个叶子结点的左子树或右子树为空为止，则插入
• 结点应为该叶子结点的左孩子或右孩子

/*******************************************************************************************************************************
 * @description：二叉排序树的插入算法
 * @param：T
 * @param：e
 * @return：
 */
BSTree BSTInsert(BSTree& T, elemType e) {
	if (T == NULL) {
		T = (BSTree)malloc(sizeof(BSTNode));
		T->data = e;
		T->leftChild = T->righrChild = NULL;
	}
	else if (e.key < T->data.key) {
		T->leftChild = BSTInsert(T->leftChild, e);
	}
	else if (e.key > T->data.key) {
		T->righrChild = BSTInsert(T->righrChild, e);
	}
	return T;
}

生成

一个无序序列可通过构造二叉排序树而变为一个有序序列。构造树的过程就是对无序序列进行排序的过程

插入的结点均为叶子结点，故无需移动其它结点。相当于在有序序列上插入记录而无需移动其它记录

不同插入次序的序列生成不同形态的二叉排序树

/*******************************************************************************************************************************
 * @description：二叉排序树的生成算法
 * @param：T
 * @param：a
 * @param：n
 */
void CreateBST(BSTree& T, keyType a[], int n) {
	T = NULL;
	for (int i = 0; i < n; i++) {
		elemType e;
		e.key = a[i];
		BSTInsert(T, e);
	}
}

删除

从二叉排序树中删除一个结点，不能把以该节点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变

由于中序遍历二叉排序树可以得到一个递增有序的序列。那么，在二叉排序树中删除一个结点相当于删去有序序列中的一个结点

• 将因删除结点而断开的二叉链表重新连接起来
• 防止重新链接后树的高度增加

1. 被删除的结点是叶子结点：直接删去该结点
2. 被删除的结点只有左子树或者只有右子树，用其左子树或者右子树替换它（结点替换）
3. 被删结点既有左子树，也有右子树：

1. 以其中序前趋值替换之（值替换），然后再删除该前趋结点。前趋是左子树中最大的结点
2. 也可以用其后继替换之，然后再删除后继结点。后继是右子树中最小的结点

/*******************************************************************************************************************************
 * @description：二叉排序树的删除算法
 * @param：T
 * @param：key
 * @return：
 */
BSTree BSTDelete(BSTree& T, keyType key) {
	if (T == NULL) {
		return NULL;
	}
	else if (key < T->data.key) {
		T->leftChild = BSTDelete(T->leftChild, key);
	}
	else if (key > T->data.key) {
		T->righrChild = BSTDelete(T->righrChild, key);
	}
	else {
		if (T->leftChild == NULL) {
			BSTree p = T;
			T = T->righrChild;
			free(p);
		}
		else if (T->righrChild == NULL) {
			BSTree p = T;
			T = T->leftChild;
			free(p);
		}
		else {
			BSTree p = T->righrChild;
			while (p->leftChild != NULL) {
				p = p->leftChild;
			}
			T->data = p->data;
			T->righrChild = BSTDelete(T->righrChild, p->data.key);
		}
	}
	return T;
}

7.3.2 平衡二叉树

平衡二叉树（balanced binary tree）

• 又称AVL树（Adelson-Velskii and Landis）
• 一棵平衡二叉树或者是空树，或者是具有以下性质的二叉排序树：

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

为了方便起见，给每个结点附加一个数字，给出该节点左子树与右子树的高度差。这个数字称为该节点的平衡因子（BF）

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

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

对于一棵有n个结点的AVL树，其高度保持在O(log(2, n))数量级，ASL也保持在O(log(2, n))量级

判断是否为平衡二叉树

class Solution {
   public:
    // 求树的深度
    int depth(TreeNode* root) {
        if (root == nullptr)
            return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }

    bool isBalanced(TreeNode* root) {
        if (root == nullptr)
            return true;
        return abs(depth(root->left) - depth(root->right)) <= 1 &&
               isBalanced(root->left) && isBalanced(root->right);
    }
};

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于1的结点，如：2、-2

如果在一棵AVL树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡

平衡调整的四种类型

调整原则：

1. 降低高度
2. 保持二叉排序树性质

LL型调整

• B结点带左子树一起上升
• A结点称为B的右孩子
• 原来B结点的右子树作为A的左子树

RR型调整

• B结点带右子树一起上升
• A结点成为B的左孩子
• 原来B结点的左孩子作为A的右孩子

LR型调整

• C结点穿过A、B结点上升
• B结点成为C的左孩子，A结点成为C的右孩子
• 原来C结点的左孩子树作为B的右子树，原来C结点的右子树作为A的左子树

RL型

7.4 散列表的查找

基本思想：记录的存储位置与关键字之间存在对应关系 对应关系——hash函数

Loc(i) = H(keyi)

7.4.1 相关术语

散列方法（杂凑法）：

选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行对比，确定查找是否成功

散列函数（杂凑函数）：散列方法中使用的转换函数

冲突：不同的关键码映射到同一个散列地址

key1 ≠ key2，但是H(key1) = H(key2)

例：有6个元素的关键码分别为：（25，21，39，9，23，11）

• 选取关键码与元素位置间的函数为H(k) = k mod 7
• 地址编码从0-6

7.4.2 散列函数的构造方法

使用散列表要解决好两个问题：

1. 构造好的散列函数

1. 所选函数尽可能简单，以便提高转换速度
2. 所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费

2. 制定一个好的解决冲突的方案

1. 查找时，如果从散列函数计算出的地址中查不到关键码，则应当依据解决冲突的原则，有规律地查询其它相关单元

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

1. 执行速度（即计算散列函数所需的时间）
2. 关键字的长度
3. 散列表的大小
4. 关键字的分布情况
5. 查找频率

根据元素集合的特性构造

• 要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小
• 要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突

构造方法：

1. 直接定址法
2. 数字分析法
3. 平方取中法
4. 折叠法
5. 除留余数法
6. 随机数法

直接定址法

Hash(key) = a·key +b （a、b为常数）

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

缺点：要占用连续地址空间，空间效率低

除留余数法

7.4.3 处理冲突的方法

1. 开放定址法（开地址法）
2. 链地址法（拉链法）
3. 再散列法（双散列函数法）
4. 建立一个公共溢出区

开放定址法

基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入

线性探测法

例：关键码集为{47、7、29、11、16、92、22、8、3}，散列表的长度为 m=11；散列函数为Hash(key) = key mod 11；拟用线性探测法解决冲突。建散列表如下：

平均查找长度ASL= (1+2+1+1+1+4+1+2+2)/9=1.67

二次探测法

链地址法

又称拉链法，基本思想：相同散列地址的记录链成一单链表

链地址法建立散列表的步骤：

• Step1:取数据元素的关键字key,计算其散列函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行Step2解决冲突。
• Step2:根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表。

链地址法的优点：

• 非同义词不会冲突，无“聚集”现象
• 链表上的结点空间动态申请，更适合于表长不确定的情况

7.4.4 散列表的查找

例题：

效率分析

ASL与装填因子α有关！既不是严格的O(1)，也不是O(n)

结论：

• 散列表技术具有很好的平均性能，优于一些传统的技术
• 链地址法优于开地址法
• 除留余数法作散列函数优于其它类型函数