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.elemmid.key='= key)' return mid else if list.elemmid.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 分块查找

条件：

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

性能分析

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

7.2.4 三种查找比较

7.3 树表的查找

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

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

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

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

7.3.1 二叉排序树

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

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

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

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

存储结构

typedef int keyType;

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


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

查找

算法思想：

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

若key等于T->data.key,则查找成功，返回根结点地址
若key小于T->data.key,则进一步查找左子树
若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);
	}
}

删除

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

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

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

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

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

/*******************************************************************************************************************************
 * @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 isbalancedroot->left) && isBalanced(root->right);
    }
};

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

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

平衡调整的四种类型

调整原则：

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

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 散列函数的构造方法

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

构造好的散列函数

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

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

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

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

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

根据元素集合的特性构造

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

构造方法：

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

直接定址法

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

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

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

除留余数法

7.4.3 处理冲突的方法

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

开放定址法

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

线性探测法

例：关键码集为{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)

结论：

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

网站首页 > 教程文章正文

数据结构——第7章-查找

7.1 查找的概念

7.2 线性表的查找

7.2.1 顺序查找

7.2.2 折半查找

非递归算法

递归算法

判定树

7.2.3 分块查找

7.2.4 三种查找比较

7.3 树表的查找

7.3.1 二叉排序树

查找

插入

生成

删除

7.3.2 平衡二叉树

LL型调整

RR型调整

LR型调整

RL型

7.4 散列表的查找

7.4.1 相关术语

7.4.2 散列函数的构造方法

直接定址法

除留余数法

7.4.3 处理冲突的方法

开放定址法

链地址法

7.4.4 散列表的查找

猜你喜欢

网站首页 > 教程文章 正文

数据结构——第7章-查找

7.1 查找的概念

7.2 线性表的查找

7.2.1 顺序查找

7.2.2 折半查找

非递归算法

递归算法

判定树

7.2.3 分块查找

7.2.4 三种查找比较

7.3 树表的查找

7.3.1 二叉排序树

查找

插入

生成

删除

7.3.2 平衡二叉树

LL型调整

RR型调整

LR型调整

RL型

7.4 散列表的查找

7.4.1 相关术语

7.4.2 散列函数的构造方法

直接定址法

除留余数法

7.4.3 处理冲突的方法

开放定址法

链地址法

7.4.4 散列表的查找

猜你喜欢

网站首页 > 教程文章正文