26考研 | 王道 | 数据结构 | 第七章查找

第七章查找

7.1 查找概念

**查找：**在数据集合中寻找满足某种条件的数据元素的过程称为查找。
**查找表(查找结构)：**用于查找的数据集合称为查找表，它由同一类型的数据元素 (或记录)组成。
**关键字：**数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
对查找表的常⻅操作：
1. 查找符合条件的数据元素
2. 插⼊、删除某个数据元素
- 只需要进行操作1的是静态查找表
- 1和2都需要进行的是动态查找表
**查找长度：**在查找运算中，需要对比关键字的次数称为查找长度。
平均查找长度(ASL，Average Search Length)： 所有查找过程中进行关键字的比较次数的平均值。
ASL的数量级反应了查找算法时间复杂度

7.2 顺序查找

**顺序查找，**又叫“线性查找”，通常用于线性表算法。
**思想：**从头到尾遍历

代码实现：

typedef struct{				//查找表的数据结构（顺序表）
    ElemType *elem;			//动态数组基址
    int TableLen;			//表的长度
}SSTable;
 
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);
    // 查找成功返回数组下标，否则返回-1
    	return i=ST.TableLen? -1 : i;
}

哨兵方式代码实现：

思想：顺序表从下表1开始存储，把key存储在下标为0的地方，从后往前遍历，只要找到key就退出循环。

查找失败的的话那么返回的i值为0，表示查找失败

查找成功则返回对应的下标值

优点是无需判断是否越界，因为遍历到下标为0的时候，它本身肯定和它本身相同，肯定就退出了

typedef struct{				//查找表的数据结构（顺序表）
    ElemType *elem;			//动态数组基址
    int TableLen;			//表的长度
}SSTable;
 
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;
    int i;
    for(i=ST.TableLen;ST.elem[i]!=key;--i)
    // 查找成功返回数组下标，否则返回0
	    return i;
}

圆形是成功，方格是失败

优化要根据具体情况具体分析

7.3 折半查找

如果是左闭右闭区间的话，查找失败循环结束时left=right+1

而如果是左闭右开区间的话，查找失败循环结束时是left=right

除了有序这个条件还必须是顺序存储

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

折半查找代码实现：

typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;
 
// 折半查找
int Binary_Search(SSTable L,ElemType key){
    int low=0,high=L.TableLen,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;
}

如果mid是向上取整，那就是左子树比右子树多一个或者0个结点了

注:折半查找一般都比顺序查找更优秀。但不是一定比顺序查找更优秀。

7.4 分块查找

分块查找所针对的情况：块内无序、块间有序。

这个太复杂了，会模拟就行，一般不会考，考也就是少量的数据

如果每个块中的元素数量都相同的话就比较有规律，如上图所示（注：n=sb,b=n/s带入ASL算出最后的表达式求极值的得到最小值）

最后的结果是，每个块内如果是根号n个元素，那么一共有根号n个块，那么就会得到最小的ASL

如果n=10000，则ASL最小为根号n+1=100+1=101

也就是平均值需要对比101次关键字就可以查找到我们想要的关键字

如果使用折半查找查找块的话，asl如上图所示，有个印象就行不是很重要

这个例子说明了，要具体问题具体分析,删除插入频繁就不用数组而是用链表了

7.5 二叉排序树

**二又排序树，**又称二叉查找树(BST，Binary Search Tree)棵二叉树或者是空二叉树，或者是具有如下性质的二叉树:

左子树上所有结点的关键字均小于根结点的关键字；
右子树上所有结点的关键字均大于根结点的关键字；
左子树和右子树又各是一棵二叉排序树；
左子树结点值< 根结点值< 右子树结点值；
进行中序遍历，可以得到一个递增的有序序列。

【二叉排序树的查找】

若树非空，目标值与根结点的值比较；
若相等，则查找成功；
若小于根结点，则在左子树上查找；
否则在右子树上查找；
查找成功，返回结点指针;查找失败返回NULL 。

非递归实现最坏空间复杂度为O(1)，递归实现最坏空间复杂度为O(h)，为树的高度

typedef struct BSTNode{
   int key;
   struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
 
//在二叉排序树中查找值为key的结点（非递归）
//最坏空间复杂度：O(1)
BSTNode *BST_Search(BSTree T, int key){
   while(T!=NULL && key!=T->key){        //若树空或等于跟结点值，则结束循环
      if(key<T->key)       //值小于根结点值，在左子树上查找
         T = T->lchild;
      else                  //值大于根结点值，在右子树上查找
         T = T->rchild;
   }
   return T;
}
 
//在二叉排序树中查找值为key的结点（递归）
//最坏空间复杂度：O(h) h为树的高度
BSTNode *BSTSearch(BSTree T, int key){
   if(T == NULL)
      return NULL;
   if(Kry == T->key)
      return T;
   else if(key < T->key)
      return BSTSearch(T->lchild, key);
   else 
      return BSTSearch(T->rchild, key);
}

【二叉排序树的插入操作】

若原二叉排序树为空，则直接插入结点;否则；
若关键字k小于根结点值，则插入到左子树；
若关键字k大于根结点值，则插入到右子树。

//在二叉排序树中插入关键字为k的新结点（递归）
//最坏空间复杂度：O(h)
int BST_Insert(BSTree &T, int k){
   if(T==NULL){           //原树为空，新插入的结点为根结点
      T = (BSTree)malloc(sizeof(BSTNode));
      T->key = k;
      T->lchild = T->rchild = NULL;
      return 1;                       //插入成功
   }
   else if(K == T->key)               //树中存在相同关键字的结点，插入失败
      return 0;
   else if(k < T->key)                 
      return BST_Insert(T->lchild,k);
   else 
      return BST_Insert(T->rchild,k);
}

【二叉排序树的构造】

//按照str[]中的关键字序列建立二叉排序树
void Crear_BST(BSTree &T, int str[], int n){
   T = NULL;                     //初始时T为空树
   int i=0;
   while(i<n){
      BST_Insert(T,str[i]);     //依次将每个关键字插入到二叉排序树中
      i++;
   }
}

【二叉排序树的删除】

先搜索找到目标结点:

若被删除结点z是叶结点则直接删除，不会破坏二叉排序树的性质；
若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置；
若结点z有左、右两棵子树，则令z的直接后继 (或直接前驱) 替代z，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一或第二种情况。
- 直接前驱就是中序遍历二叉排序树的要删除结点的前一个结点，即该节点的左子树的最右下的节点
- 直接后继就是中序遍历二叉排序树的要删除结点的后一个结点，即该节点的右子树的最左下的节点

**查找长度：**在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度

7.6 平衡二叉树

平衡二叉树的插入

**平衡二叉树(Balanced Binary Tree)，**简称平衡树(AVL树)–上任一结点的左子树和右子树的高度之差不超过1。
结点的平衡因子 = 左子树高 - 右子树高

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

平衡二叉树的插入

每次调整的对象都是“最小不平衡子树“
在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。

调整最小不平衡子树（LL）：

调整最小不平衡子树（RR）：

左旋右旋的的代码思路：

其实就还是链表的操作，这个指针指到这边，那个指针指到那边，唯一要注意的就是改完指针之后不要忘记还要连接原来的二叉树，即gf的操作

调整最小不平衡子树（LR）：

调整最小不平衡子树（RL）：

n3=4，n4=7，n5=12,n6=20

4层7个节点

5层12结点

做题所得结论（五颗星）：当你用上面的递推公式推出来一个深度为h的最小节点数量nh，深度为h的二叉平衡树只有nh个节点的话，那么所有的非叶子节点的平衡因子都是1或-1，反过来也成立。

平衡二叉树的删除

对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）

7.7 红黑树

可能的考法

7.7.1 为什么要发明红黑树？

红黑树是适度平衡的二叉排序树

平衡二叉树是高度平衡的二叉排序树

所以一般相同结点的话，平衡二叉树的性能会更优秀

7.7.2 红黑树的定义和性质

定义：

叶节点，失败节点，null节点说的是一个东西。也就是说红黑树里面的叶子节点并不是最下面一层

左根右，根叶黑，不红红，黑路同

是二叉排序树，左子树小于根小于右子树，根节点和叶节点都是黑的，不可以有两个相连红色，从一个节点出发到达叶节点的路径上的黑色节点数量一定相同

性质：

红色节点数目最大可以是黑节点数目的两倍

若红黑树所有节点都是黑色的，那肯定是一颗满二叉树（因为根节点到叶节点的所有路径上的黑色节点数量必须相同）

查找：

和BST,AVL一样，从根出发，左小右大，若查找到一个空叶节点，则查找失败

7.7.3 红黑树的插入和删除

`插入`

1.如果插入的新结点不是根，为什么要染成红色呢？因为要保证黑路同，如果染成黑色，那必然导致新增加节点的；路径上的黑色节点数量比其他路径多

2.判断LL还是RR还是其他型都是通过爷节点来判断的而不是父节点

3.图中的染色的意思其实就是取反，只要涉及到x换y的，那么x和y的颜色都要取反，黑的变红的，红的变黑的

4.爷变为新结点是把爷结点看做新结点重新走一遍上述的流程，看爷节点作为新结点有没有破坏红黑树特性，比如：如果爷结点此时是红的，还是根节点，那必然要被染成黑色

5.其实每次插入的如果不是根节点，那么破坏的基本都是不红红这个特性

重点：所以每次插入的如果是非根节点就直接看有没有违背不红红就行，不用管其它特性有没有被违背，因为一定不会被违背

具体的例子

插入20,10,5

插入30

插入40

插入57

插入3

插入2

插入4

插入35,25,18都没有违反不红红，直接插入就好

其实当红黑树越来越大的时候插入很多时间都是直接插入的

插入22

插入23

第一步违反了不红红且叔叔是黑的，判断为LR型

第二步左旋

第三步右旋

第四步儿子和爷染色

插入24

破坏不红红，且是红叔，则染色，爷变为新结点

爷变为新结点后发现违反了不红红，则继续进行之前的对应步骤

左旋

右旋

染色

插入19,18

19没有破坏不红红直接插入，而红黑树中已经有18这个关键字了，那么18插入到哪里就看自己的算法是如何设计的了，可以在18左孩子，也可以去18右孩子

右旋

左旋

染色

到此为止插入完成

`删除`

23,24届考察概率不大，25不好说，还是看看吧

7.8 B树和B+树

7.8.1 B树

如果每个节点的的关键字太少，比如变成1个的话，那就退化为二叉查找树了，所以才要保证节点的最少分叉和最少关键字的数量

如果可以保证每个节点关键字不少，并且所有子树高度都相同，那这个其实就是一个b树

每个节点最多m-1个关键字，第一层1个节点第二层最多m个节点……最多就是1+….m的h-1次方个节点，就是上面这个公式

求最大高度的方法1：

b树的叶子节点代表失败节点，有n个关键字就肯定有n+1个失败的区间，那么就是n+1个叶子

求最大高度的方法2

k是一个节点内最少的分叉数量，减去1就是最少的关键字的数量

7.8.2 B树的基本操作

B树的查找：

B树的查找操作与二叉查找树类似。
B树的查找包含两个基本操作：① 在B树中找结点；② 在结点中找关键字。B树常存储在磁盘上，因此前一个查找操作在磁盘上进行，后一个查找操作在内存中进行。在B树中查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应指针信息到所指的子树中去查找。查找到叶子结点（对应指针为空指针），则说明树中没有对应的关键字，查找失败。

B树的插入：