Ch6Search/

Table of Contents

• 6 查找
  • 6.1 查找的基本概念
    • 三种基本的搜索算法:
      • 1. 线性搜索.
      • 2. 二分搜索
      • 3. 散列法
    • 基本术语:
      • 1. 查找表
      • 2. 关键字
      • 3. 动态查找表与静态查找表
      • 4. 平均查找长度
  • 6.2 线性表的查找
    • 6.21 线性查找
    • 6.22 二分搜索
    • 6.23 分块查找
  • 6.3 树表的查找
    • 6.3.1 二叉搜索树
      • 1.二叉搜索树的概念
      • 2.二叉搜索树的查询
        • 1.查找
        • 2.最大和最小关键字元素
        • 3.后继和前驱
      • 3.插入和删除
        • 1.插入
        • 2.删除
    • 6.3.2 平衡二叉树
      • 1.平衡二叉树的定义
      • 2.平衡二叉树的插入
    • 6.3.3 B树
      • 1.B树的定义
      • 2.B树的基本操作
        • 搜索B树
        • 创建一颗空B树
        • B树中插入一个关键字
  • 6.4 散列法

6 查找

6.1 查找的基本概念

搜索或称查找: 是指从数据集合里找出目标的算法.

三种基本的搜索算法:

1. 线性搜索.

线性搜索指从数据集合的开头顺次访问各元素, 若找到就返回该元素或位置,并结束搜索,若无则返回一个特殊值表明没有搜索到值. 线性搜索效率低, 但是适用于各种数据形式

2. 二分搜索

也称为二分查找法, 在基于已经排序好的数据集合基础上进行的搜索,搜索思路如下:

1. 先把整个集合区域作为搜索范围(数据集合升序排列)
2. 检查数据集合中央的元素,若与目标关键字一致则结束,若小于关键字则对前半部分做第二部的操作.
3. 若检查到数据返回数据或者数据位置,否则返回特殊值表明未查询到值.

3. 散列法

散列是一种数据结构也是一种散列表的算法.此算法只需要将元素的关键字带入函数即可找出结果.

基本术语:

1. 查找表

查找表是同一类型的数据元素构成的集合. 数据元素之间存在完全松散的关系,因此查找表示一种非常灵活的数据结构, 可以使用线性表, 树表及散列表实现等

2. 关键字

关键字是数据元素中某个数据项的值, 用它可以标识一个数据元素.

若此关键字可以唯一的标识一个记录, 称为主关键字, 反之可以识别若干记录的称为次关键字.

3. 动态查找表与静态查找表

查找的同时进行修改操作,相应的表称为动态查找表,反之为静态查找表

动态查找表的表结构本身实在查找过程中动态生成的, 即创建表时,对于给定值, 若表中存在其关键字匹配到给定值的记录,则查找成功返回; 否则插入关键字等于给定值的记录

4. 平均查找长度

为确定记录在查找表中的位置, 需和给定值进行进行比较关键字个数的期望值, 称为查找成功时的平均查找长度(Average Search Length, ASL)

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑PiCi (i=1,2,3,…,n),可以简单以数学上的期望来这么理解。其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。

查找算法的基本运算是关键字之间的比较操作, 所以可以用平均查找长度来衡量查找算法的性能.

6.2 线性表的查找

线性查找又称顺序查找(Linear Search/Sequential Search) 是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的Key值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。

6.21 线性查找

算法描述:

1. 顺序搜索

   LINEAR-SERACH(A, key)
       for each i in A
           if i == key
            return i
       return NOT_FOUND
   

2. 设置监视哨的顺搜索 将上面的算法引入标记之后可以将效率提高数倍. 所谓标记, 就是在数组等数据结构中设置一个拥有特殊值的元素.线性搜索中, 我们可以把元素放置在最后一个单元中, 然后只通过比较一次即可继续迭代.

   LINEAR-SERACH(A, key)
       i = 0
       A[n] = key
       while A[i] != key 
           i++
       if i = n
           return NOT_FOUND
       retrun i
   

   两个算法的区别在于主循环中的比较次数, 算法1需要比较两次, 一次是for循环里 , 一次是key和元素的比较, 而算法二 只需要一次不等价运算即可, 由于标记的作用可以确保不陷入死循环, 所以可以去掉结束循环条件

算法分析

算法二是程序设计技巧的改进, 通过设置观察哨, 去除查找过程里每次迭代都要判断是否已经搜索完整张表. 当数据量大时, 能减少近乎一半的运行时间.

两个算法的时间复杂度均为O(n).

优点: 适用于顺序结构和链式结构, 无论元素顺序均可以使用

缺点: 平均查找长度过大时, 效率低.

6.22 二分搜索

Binary Search 称二分查找或折半查找, 先决条件是线性表必须使用顺序存储结构并且元素按照关键字有序排列,下列讨论中, 默认有序表是有序递增的.

算法步骤:

二分查找过程为: 从表的中间记录开始,若给定值和中间记录的关键字相等,则查找成功; 若给定值大于或者小于中间记录的关键字,则在表中大于或小于中间记录的那一半中查找, 重复执行,直到查找到元素或者区间为空(这时查找失败)

算法描述:

1. 循环写法

   BINARY-SEARCH(A, key)
       left = A's first index
       right = A's last index
       while left <= right
           mid = (right+left)/2
   		if key < A[mid]
               right = mid
   		else if key > A[mid]
               left = mid
           else
               return mid
       return NOT_FOUND
   

2. 递归写法

   BINARY-SEARCH(A, left, right, key)
   	if left > right
   		return NOT_FOUND
   	 mid = (right+left)/2
   	if key < A[mid]
       	return BINARY-SEARCH(A, key, left, mid-1)
   	else if key > A[mid]
       	return BINARY-SEARCH(A, key, mid+1, right)
       else
       	return mid
   

算法分析

二分搜索过程可以用二叉树描述. 树中每个结点对应表中的一个记录, 但节点值不是记录的关键字, 而是记录在表中的位置序号. 把mid位置作为树根, 左子表与右子表分别作为树的左子树与右子树, 得到的二叉树称为二分搜索的判定树.

在查找成功时进行比较的次数不超过树的深度.具有n各结点的判定树的深度为$log_2n + 1$ , 即查找成功时和给定值比较的关键字数最多为$log_2n + 1$

因此算法的时间复杂度为$O(log_2n)$.

优点:比较次数少查找效率高

缺点: 对表结构要求高, 只能用于顺序存储的有序表. 排序费时, 排序时需要进行元素的移动. 二分搜索不适合用于数据元素经常变动的线性表

6.23 分块查找

分块查找(Blocking Search)/索引顺序查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。

需要建立一个索引表, 其中包括两项内容:

• 关键字项, 其值为该子表的最大关键字
• 指针项, 指示该子表的第一个记录在表中的位置

索引表按关键字有序, 则表或者有序或者分块有序. 分块有序是指第任意的子表$i$中所有记录的关键字均大于$i-1$中的子表中的最大关键字.

查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。

算法步骤

1. 先选取各子表中的最大关键字构成一个索引表
2. 先在索引表中查找到范围, 在进入该索引表指示的子表中进行搜索

算法描述

ADT index
	key
	left
	right

BLOCK-SEARCH(A,index[],key)
	//Get the block location which conatins the key
	i = BINARY-SEARCH(index[],key)
	//Search key in block i
	return LINEAR-SERACH(A, index[i].left,index[i].right, key)

算法分析

$ASL=L_b+L_w, L_b为查找索引表确定所在快的平均查找长度,L_w为在块中查找元素的平均查找长度$

分块查找是折半查找和顺序查找的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求，但查找效率很低。如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。

分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

6.3 树表的查找

线性表更适用于静态查找表, 索要对动态查找表惊醒高效率的查找, 可采用集中特殊的二叉树作为查找白哦的的组织形式, 统称为树表.

6.3.1 二叉搜索树

二叉搜索树/二叉搜索树是一种可以进行插入, 搜索, 删除等操作的数据结构了可以用做字典优先级队列.

1.二叉搜索树的概念

二叉排序树或者一颗空树,或者是具有下列性质的二叉树

• 左子树不空, 左子树上的所有节点值小于其根节点的值
• 右子树不空, 右子树上的所有节点值大于其根节点的值
• 左右子树也为二叉搜索树

二叉搜索树可以使用一个链表数据结构表示, 每一个结点就是一个对象, 如下

ADT NODE
	parent
	left,right
	key

• key: 为每个节点存储的信息
• left, right: 左右子节点的指针地址
• parent:节点的父节点

与二叉树相同的思路, 二叉搜索树也有三种简单的按序输出来访为所有的关键字:

1. 前序遍历:

   PREORDER-TREE-WALK(x)
   	if x != NIL
   		output x.key
   		PREORDER-TREE-WALK(x.left)
   		PREORDER-TREE-WALK(x.right)
   

2. 中序遍历:

   INORDER-TREE-WALK(x)
   	if x != NIL
   		INORDER-TREE-WALK(x.left)
   		output x.key
   		INORDER-TREE-WALK(x.right)
   

3. 后序遍历:

   POSTORDER-TREE-WALK(x)
   	if x != NIL
   		POSTORDER-TREE-WALK(x.left)
   		POSTORDER-TREE-WALK(x.right)
   		output x.key
   

2.二叉搜索树的查询

查存储在二叉搜索树中的关键字.

使用下列过程在二叉搜索树中查找给定的关键字.

输入一个指向树根的指针和一个关键字k, 若结点存在, 返回一个指向关键字k的结点指针,否则返回NIL

RECURSIVE-TREE-SEARCH(x, k)
	if x == NIL or k == x.key
		return NIL
	if k < x.key
		return TREE-SEARCH(x.left, k)
	else
		return TREE-SEARCH(x.right, k)

可以使用循环展开递归, 对于大部分计算机可以提高效率

ITREATIVE-TREE-SEARCH(x, k)
	while x != NIL and k != x.key
		if k < x.key
			x = x.left
		else
			x = x.right
		return x

两个的运行时间都为O(h), h为树的高度.

根据二叉搜索树的性质, 分别沿着根的左指针和右指针,直到遇到NIL可以找到最小元素和最大元素

TREE-MINIMUM(x)
	while x.left != NIL
		x = x.left
	return x

TREE-MAXIMUM(x)
	while x.right != NIL
		x = x.right
	return x

二叉搜索树的性质保证两个算法都是正确的. 他们都在在一棵高度为h的树上以O(h)的时间内执行完

给定一棵二叉搜索树中的一个结点, 有时候需要按中序遍历的次序寻找他的后继. 若所有的关键字互不相同, 则一个结点x的后继时大于x.key的最小关键字的结点.

一颗二叉搜索树的的结构允许我们通过没有任何关键字的比较来确定一个结点的后继.若后继存在, 下面的过程将返回一个x节点的后继,若x是这棵树的最大关键字, 则返回NIL

TREE-SUCCESSOR(x)
	if x.right !=  nil
		return TREE-MINIMUM(x)
	y = x.parent
	while y != NIL and x == y.right
		x = y
		y = y.parent
	reutrn y

上面的伪代码分为两种情况:

1. 若结点x的右子树非空, 那么x的后继恰是x右子树中的最左结点, 通过调用TREE-MINIMUM(x)即可得到
2. 若结点x的右子树为空, 那么x是x的父节点y的左子节点则返回y, 否则返回x的有左孩子的最底层祖先

在一颗高度为h的树中, 该算法运行时间为O(h), 因为该过程或者遵从一条简单路径沿树向上或者遵从简单路径沿树向下

3.插入和删除

插入和删除会引起二叉搜索树表示的动态集合的变化. 一定要修改数据结构来反应这个变化, 但修改要保持二叉搜索树的性质的成立

要将一个新值v插入到一颗二叉搜索树T中, 需要调用TREE-INSEART.

z作为输入, 其中z.key = v, z.left = NIL, z.right = NIL. 过程中要修改T和z的某些属性把z插入到合适的位置

TREE-INSEART(T,z)
	y = NIL
	x = T.root
	whlie x != NIL
		y = x
		if z.key < x.key
			x = x.left 
		else
			x = x.right
	z.parent = y
	if y == NIL
		T.root = z
	elseif z.key < y.key
		y.left = z
	else
		y.right = z

RECURSIVE-TREE-INSEART(T,z)
	if T.root == NIL
		T.root = z
		return 
	if z.key < T.root.key
		if T.root.left == NIL
			T.root.left = z
			return
		RECURSIVE-TREE-INSEART(T.root.left,z)
	else
		if T.root.right == NIL
			T.root.right = z
			return
		RECURSIVE-TREE-INSEART(T.root.right,z)

在一颗高度为h的树中, 该算法运行时间为O(h)

从一颗二叉搜索树中删除结点x的整个策略分三种情况:

1. 若z没有子节点, 简单删除, 并修改其父节点的用NIL替换z
2. 若z只有一个孩子, 则将这个孩子提升到树种z的位置上, 并修改z的父节点, 用z的孩子来替换z
3. 若z有两孩子,则照z的后继y, 并让y占据树中z的位置. z的原来右子树部分称为y的新的右子树, 并且z的左子树称为y的新左子树.

算法的过程与概况的情况有些许不同

1. 若z没有左子节点, 则用右子树替换z, 无论右子树是否为空
2. 有且仅有一个左子节点, 则直接替换z
3. z的两个子节点都存在. 需要寻找z'的后继y, y位于z的右子树种并且没有没有左孩子, 则将y替换z, z的左子树变为y的左子树.
4. 若y是z的右子树, 那么用y替换z, 并仅留下的右孩子. 否则, y位于z的右子树中但并不是z的右孩子.在这种情况下,先用y的右孩子替换y, 再用y替换z

定义一个子过程,用于另一棵子树替换一颗子树并成为其双亲的孩子结点. 当此过程用一颗以v为根的子树来替换一颗以u为根的子树时, 结点u的双亲就变为结点v的双亲, 并且最后v成为u的双亲的相应孩子.

TRANSPLANT(T,u,v)
	if u.parent == NIL
		T.root = v
	elseif u == u.parent.left
		u.parent.left = v
	else 
		u.parent.right = v
	if V != NIL
		v.parent = u.parent

利用TRANSPLANT过程, 实现T中删除结点

TREE-DELETE(T,z)
	if z.left  == NIL
		TRANSPLANT(T,z,z.right)
	elseif z.right == NIL
		TRANSPLANT(T,z,z.left)
	else
		y = TREE-MINIMUM(z.right)
		if y.parent != z
			TRANSPLANT(T,y,y.right)
			y.right = z.right
			y.right.parent = y
		TRANSPLANT(T,z,y)
		y.left = z.left
		y.left.parent = y

在一颗高度为h的树中, 该算法运行时间为O(h)

6.3.2 平衡二叉树

二叉搜索树的性能取决于树的结构，而其结构又取决于数据集。 若是线性排列， 则时间复杂度为$O(n)$, 若是合理的结构则复杂度可以降低为$log_2n$ .树的高度越小， 查找速度越快。因此平衡二叉树可以很好的让二叉排序树的结构更合理。

平衡二叉树的基本操作与二叉搜索树类似， 只是插入有些不同。

1.平衡二叉树的定义

Balanced Binary Tree ,Height-Balanced Tree or AVL TREE

平衡二叉树或者是空树, 或者是满足下列条件的二叉排序树

• 左子树和右子树的深度差的绝对值小于1
• 左子树右子树也是平衡二叉树

将二叉树上结点的**平衡因子(Balanced Factor)**定义为该结点的左子树和右子树的深度之差， 则平衡二叉树上所有结点的的平衡因子只可能为-1，0和1.若平衡因子绝对值大于1 则该树不是平衡二叉树。由此特点可知，其深度和$log_2n$是同数量级的，n为结点数，故查找时间复杂度为$O(log_2n)$

2.平衡二叉树的插入

BBST上插入一个结点x的算法描述如下：

1. 若BBST为空树，将x作为树的根节点，树深度加一
2. 若x的关键字与树根的关键字相等， 不进行插入
3. 若x的关键字小于BBST的根结点，且在左子树中不存在和x相同关键字的结点, 则可以将x插入到树的左子树上， 并且当插入之后的左子树深度加一的时候，有下列几种情况
   • 树的根节点的平衡因子为-1(右子树深度大于左子树的深度):则根结点的平衡因子改为0, 树深度不用改变
   • 树根节点的平衡因子为0(左右子树深度相等):则树根结点平衡因子改为1, 树的深度+1
   • 树根节点平衡因子为1（左子深度大于右子树）需要进行单向向右旋平衡处理, 并且在右旋处理之后, 将根节点和其右子树的根节点的平衡因子改为0
   • 若BBST的左子树的根节点平衡因子为-1， 则需要先进行先向左在向右的双向旋转平衡处理， 并且在旋转处理之后。修改根节点和其左，右子树的平衡因子， 树的深度不变。
4. 若x的关键字大于树的根节点关键字， 并且在树的右子树中不存在和x相同的关键字结点，则将x插入到右子树中， 并且当插入之后的右子树深度增加时，分别就不同情况处理之， 操作和步骤三相似。

6.3.3 B树

B树是为磁盘或其他直接存取辅助设备而设计的一种平衡二叉树.

1.B树的定义

一棵B树是具有如下性质的有根树(根为T.root):

ADT NODE
	n
	leaf
	key[]
	c[]*NODE

1. 每个结点x属性
   • x.n 表示存储在x中的关键字个数
   • x.n个关键字以非降序排列,$x.key_1 <= x.key_2 <=...<=x.key_{x.n+1}$
   • x.leaf,bool类型的值,表示x是否为叶节点
2. 每个内部节点x还包含x.n+1个指向其他孩子的指针$x.c_1,x.c_2,..,x.c_{x.n+1}$,因为叶节点没有孩子，所以没有这个属性
3. $x.key_i$对存储在各子树中的关键字范围加以分割:如果$k_i$为任意一个存储在以$c.c_i$为根的子树中的关键字, 那么$k_1 <= x.key_1 <=k_2 <=x.key_2<=...<=x.key_{x.n}<=k_{x.n+1}$
4. 每个叶节点的深度都相同且为树高度h
5. 每个结点所包含的关键字个数有上界和下界.用一个被称为B树的最小度数(minimum degree)的固定度数t>=2来表示这些界:
   • 除根节点之外的每个结点必须至少有t-1个关键字. 若树非空,根节点至少有一个关键字
   • 每个结点最多可以包含$2t-1$个关键字,当一个结点存满这么多关键字是称该满结点

2.B树的基本操作

输入一个指向一个某子树根结点x的指针, 以及要在该子树中搜索的一个关键字k.

顶层调用方式为B-TREE-SEARCH(T.root,k), 若k在树中,算法返回的是结点y和使得$y.key_i=k$的下标i组成的有序对(y,i)否则返回NIL

算法描述

B-TREE-SEARCH(x,k)
	i = 1
	//找最小下标i满足 k<= x.keyi 找不到则 i = x.n+1
	while i <= x.n and k > x.keyi
		i = i + 1
	if i <= x.n and k == x.keyi	//找到了关键字返回
		return (x,i)
	elseif x.leaf	//若x为叶节点则返回空
		return NIL
	else DISK-READ(x.ci)//对存储器读取一次子树,递归搜索
		return B-TREE-SEARCH(x.ci,K)

算法分析

递归过程中是一条从树根向下的简单路径. 因此, 由B-TREE-SEARCH过程访问的磁盘页面次数为$O(h) =O(log_tn),h为树高度,n为树中所含的关键字个数$,由于$x.n<2t$,所以循环在每个结点中花费的时间为$O(t)$总CPU时间为$O(th) =O(tlog_tn)$

要创建一棵空B树, 先调用B-TREE-CREATE创建一个空的根节点,在我调用插入算法添加关键字.其中ALLOCATE-NODE在$O(1)$时间内为一个新结点分配一个磁盘页, .

B-TREE-CREATE(T)
	x = ALLOCATE-NODE()
	x.leaf =TRUE
	x.n = 0
	DISK-WRITE(x)
	T.root = x

分裂B树的结点

输入一个非满的内部节点x和其一个满子结点x.ci. 过程将这个子节点分裂为两个,并调整x使之包含新分裂的结点.要分裂一个满的根, 先让根称为一个新的空根节点的子节点, 这样在分裂一次树高加1即可, 分裂是树长高的唯一途径.

B-TREE-SPILT-CHILD(x,i)
	z = ALLOCATE-NODE()
	y = x.ci
	z.leaf = y.leaf
	z.n = t - 1
	if j = 1 to t - 1
		z.key[i] = y.key[j+t]
	if not z.leaf
		for j = 1 to t
			z.c[i] = y.c[i+t]
	y.n = t - 1
	for j = x.n+1 downto i+1
		x.c[j+1] = x.[j]
	x.c[i+1] = z
	for j = x.n downto i
		x.key[j+1] = x.key[j]
	x.key[i] = y.key[i]
	x.n = x.n+1
	DISK-WRITE(y)
	DISK-WRITE(z)
	DISK-WRITE(x)

B-TREE-INSERT(T,k)
	r = T.root
	if r.n == 2t-1
		s = ALLOCATE-NODE()
		T.root = s
		s.leaf = FALSE
		s.n = 0
		s.c[1] = r
		B-TREE-SPILT-CHILD(s,1)
		B-TREE-INSERT-NOTFULL(s,k)
	else
		B-TREE-INSERT-NOTFULL(r,k)

B-TREE-INSERT-NOTFULL(x,k)
	i = x.n
	if x.leaf
		while i >= 1 and k < x.key[i]
			x.key[i+1] = x.key[i]
			i = i - 1
		x.key[i+1] = k
		x.n = x.n + 1
		DISK_WRITE(x)
	else
    	while i >= 1 and k < x.key[i]
			i = i -1
		i = i + 1
		DISK-READ(x.c[i])
		if x.c[i].n == 2t - 1
			B-TREE-SPILT-CHILD(x,i)
			if k > x.key[i]
				i = i + 1
		B-TREE-INSERT-NOTFULL(x.c[i],k)

6.4 散列法

1. 相关定义:

   • 散列表: 散列表是一种数据结构, 由一个存储元素的结构以及决定元素位置的函数组成.
   • 散列函数(哈希函数Hash): 根据给定的关键字计算出元素在散列表中位置的函数.
   • 冲突: 哈希函数计算出来的位置发生了重复就为冲突.

2. 算法描述:

   • 散列表的简单实现:

     insert(data)
     	T[h(data.key)] = data
     
     search(data)
     	return T[h(data.key)]
     

     h(k)是根据$k$值求数组$T$的下标的函数,为散列函数.比如

     $h(k) = k\ mod\ m$

     就是一种散列函数, 指 $k除以m所得的余数$.

     • 开放地址法是解决单一函数过于简单导致冲突的常用手段之一, 如下是双散列结构中使用的开方地址法.

       $H(k) = h(k,i) = (h_1(k) + i \times h_2(k))$

       $i$是冲突之后计算下一次散列的次数

   • 使用开放地址法的散列法:

     h1(key) 
     	return k mod m
     
     h2(key)
     	return 1 + key mod m
     
     h(key, i)
     	return (h1(key) + i * h2(key)) mod m
     
     insert(T, key)
     	i = 0
     	while true
     		j = h(key, i)
     		if T[j] == NIL
     			T[j] = key
     			return j
     		else 
     			i++
     search(T, key)
     	i = 0
     	while true 
     		j = h(key, i)
     		if T[j] == key
     			return j
     		else if T[j] == NIL || i >= m
     			return NIL
     		else 
     			i++
     

   • 散列函数根据不同用途会有不一样的算法, 上述用的是求余数法.