查找算法及查找常用数据结构总结_商务服务_资讯

查找算法及查找常用数据结构总结

2024-12-24 22:46 浏览:77

基本方法：
设查找表以一维数组来存储，要求在此表中查找出关键字的值为x的元素的位置，若查找成功，则返回其位置（即下标），否则，返回一个表示元素不存在的下标（如0或-1）。

基本思想： 遍历整个顺序表逐个比较，如果关键字相等则返回其下标，如果没有找到则返回-1。

基本思想： 设查找区域的首尾下标分别用变量low和high表示（初值分别为0和n-1，其中数组的下标从0开始，这与简单顺序查找中略有不同），将待查关键字x和该区域的中间元素 (其下标mid的值为low和high的算术平均值，即(low+high)/2) 的关键字进行比较，并根据比较的结果分别作如下处理：

x==A[mid].key:查找成功，返回mid的值。
x<A[mid].key:说明待查元素只可能在左边区域(下标从low到mid-1)，因此，应在此区域继续查找。
x>A[mid].key:说明待查元素只可能在右边区域(下标从mid+1到high) ，因此，应在此区域继续查找。

若表中存在所要查找的元素，则经过反复执行上述过程可以很快地找到，并返回元素下标，否则，返回-1以表示查找失败。

核心思想是块间有序，块内无序；首先在索引表间查找确定元素所在的块，然后在确定的块中查找；

块间查找：在索引表中查找既可以用简单顺序查找，也可以用二分查找；
块内查找：在块内查找只能用顺序查找；

查找方法平均查找长度最坏查找长度简单顺序查找(n+1)/2n二分查找

注：二分查找平均查找长度计算过程

定义：二叉排序树是一棵二叉树，或者为空，或者满足以下条件：

若左子树不空，则左子树中所有结点的值小于根结点的值；
若右子树不空，则右子树中所有结点的值不小于根结点的值；
左右子树都为二叉排序树。

二叉排序树的构造

核心：从空树出发，依次插入若干个节点；

步骤：

若该值小于根结点的值，则应往左子树中插入 (递归调用插入算法)。
若该值大于等于根结点的值，则往右子树中插入（递归调用）。
按此方式递归调用若干次后，总可以搜索到一个空子树位置，即要插入的位置。

该构造方式的问题是，当输入是一个递增或者递减序列时，则该树是相当倾斜的，即左右子树的深度差距很大；

二叉排序树删除结点

删除只能和删除结点，不能删除以结点为根的子树，且还要保证删除后所得二叉树仍满足二叉排序树的性质不变。

1.被删除的结点是叶子结点：直接删去该结点。
2.被删除的结点只有右子树或者只有左子树，用其右子树或者左子树替换
3.被删除的结点既有左子树又有右子树，找到删除结点的左子树中的最大值，将其替换删除结点（或者找右子树上最小的结点）

定义：

平衡二叉树是一棵二叉排序树，或者为空，或者满足以下条件：

左右子树高度差的绝对值不大于1；
左右子树都是平衡二叉树。

平衡因子：

左子树的高度减去右子树的高度，其值为-1，0或1。

对于一颗有n个结点的AVL树，其高度保持在O（log₂n）数量级，平均查找长度（ASL）也保持在O（log₂n）量级。

如何构造平衡二叉树

在平衡的二叉排序树中插入一个结点，当出现不平衡时，根据不平衡情况分四种调整方法

——假设最低不平衡结点为A，根据新插入结点与A的位置关系来命名调整方法：

LL型：新插入结点在A的左孩子(L)的左子树(L)中；

LR型：新插入结点在A的左孩子(L)的右子树®中；

RL型：新插入结点在A的右孩子®的左子树(L)中；

RR型：新插入结点在A的右孩子®的右子树®中。

红黑树（Red-Black Tree）也是是一种自平衡的二叉搜索树，与AVL树不同的是它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍（最长路径也不会超出最短路径的两倍，因此红黑树的平衡性要求相对宽松，没有AVL树那样严格），从而使搜索树达到一种相对平衡的状态。

红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

按照二叉搜索的树规则插入新节点，除了根节点为黑色，新插入的节点初始为红色；
检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整。但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树进行调整；
调整的总体思路是重新着色或者旋转+重新着色，旋转的思路跟AVL树类似，详见 https://zhuanlan.zhihu.com/p/659174741

红黑树的删除

将红黑树内的某一个节点删除，需要执行哪些步骤呢？ ⑴首先，红黑树是一棵二叉查找树，按照二叉查找树的节点删除规则删除该节点；⑵然后，通过旋转和重新着色操作来修正该树的红黑树特性。详细步骤如下：

第一步：将节点按照二叉查找树的删除规则进行节点删除。

这和“删除常规二叉查找树中的节点方法是一样的”。分3种情况：

Ⅰ.被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。

Ⅱ.被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。

Ⅲ.被删除节点有两个儿子。那么，先找出它的[前驱节点/后继节点]；然后把“它的[前驱节点/后继节点]的内容”复制给“该节点”；之后，删除“它的[前驱节点/后继节点]”。在这里，[前驱节点/后继节点]相当于替身，在将[前驱节点/后继节点]的内容复制给"被删除节点"之后，再将[前驱节点/后继节点]删除。这样就巧妙的将问题转换为“删除[前驱节点/后继节点]”的情况了，下面就考虑[前驱节点/后继节点]。在"被删除节点"有两个非空子节点的情况下，它的[前驱节点/后继节点]不可能是双子非空。既然"[前驱节点/后继节点]"不可能双子都非空，就意味着"该节点的[前驱节点/后继节点]"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况Ⅰ"进行处理；若只有一个儿子，则按"情况Ⅱ"进行处理。

查找效率分析

对于一棵红黑树来说，如果它里面全部的黑色结点一共有N个的话，那它的最短路径长度就差不多是。然后整棵树的节点数量就是在【N，2N】之间。所以最长路径长度就可以认为差不多是所以红黑树的查找最少是次，最多是次，所以红黑树查找的时间复杂度是O()，计算时间复杂度前面的常数项可以省略。而AVL树也是O(），但AVL树是比较严格的O(），而红黑树是省略了常数项。所以严格来说，红黑树的查找效率是比不上AVL树的（但对于计算机来说是没什么差别的），但是它们是同一个数量级的，都是O(）。

红黑树对比AVL树

由于AVL树要求更加严格的平衡，所以在进行插入和删除操作时，可能需要更频繁地进行旋转操作来调整树的结构，以保持平衡。相比之下，红黑树的插入和删除操作需要旋转的次数相对较少，因此在插入和删除操作频繁的情况下，红黑树可能更加高效。
综合来看，红黑树其实更胜一筹，红黑树在实际应用中更为常用，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树实现的；

第二步：通过旋转和重新着色操作来修正该树的红黑树特性。

因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。

注：B树有时候也会写作B-树，是一个意思；

定义：m阶B树(m≥3)满足如下条件：

每一个结点分支数≤m;
根结点分支数≥2(要求此根结点不为叶子结点)；
其余分支结点的分支数≥ m/2 ；
所有叶子结点在同一层；
每一个结点的结构如下：

B+树是B树的变体，也是一种多路搜索树，其定义基本与B-树相同，除了：

B+树的性质：

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统。

B+树比B树更适合操作系统的文件索引和数据库索引的原因：

B+树的磁盘读写代价更低，B+树的内部节点没有指向关键字具体信息的指针，因此内部节点相对B树更小。如果把所有同一内部节点的关键字放在同一块磁盘中，盘块所能容纳的关键字数量也就越多，一次性读入内存中的需要查找的关键字也就越多，相对IO读写次数降低。
B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
所以，B+树只要遍历叶子节点就可以实现整棵树的遍历，支持基于范围的查询，而B树不支持range-query这样的操作（或者说效率太低）。

B∗树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。

B+树的分裂：

当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B∗树的分裂：

当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B∗树分配新结点的概率比B+树要低，空间使用率更高。

特点

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少。

2.5 算法分析

查找方法平均查找长度失败查找长度二叉排序树n二叉平衡树红黑树含义是略差于二叉平衡树，但是远远好于二叉排序树B树 find(m)指的是在m个元素中的查找长度，m一般比较小，采用顺序查找即可B+树 find(m)指的是在m个元素中的查找长度，m一般比较小，采用顺序查找即可

3.哈希表查找

给定关键字key，用一个函数H(key)计算出元素地址，由此而得散列表（Hash表，哈希表），
其中函数H(key)称为散列函数
此函数值称为散列地址。

现实中，会出现k1≠k2但H(k1)=H(k2)的情况，称这种现象为冲突现象，k1,k2为同义词。

针对冲突——如何解决冲突呢？

构造好的散列函数，以免冲突（减少冲突）
妥善处理冲突

直接定址法

H(k)= k 或者 H(k)= ak+b （a，b为任意正整数）

除留余数法

H(k)= k % p 其中p≤m,m为数组规模的最大质数。

平方取中法

例：325在平方后取105625中间两位作为它的散列地址。

折叠法

如身份证号码：40104198805061532
先进行分组：340 104 198 805 061 532

开放地址法

Hi(k)=(H(k) + di ) % m，i=1,2,…,q q<=m

线性探测法：Hi(k)=(H(k)+i)%m，m为表的规模最大质数；
二次探测法：Hi(k) = ( H(k) + i2 ) % m
伪随机数：Hi(k) = ( H(k) + random() ) % m

拉链法

再散列法

→H(k)→H1(k)→H2(k)→ …… →Hi(k)

在散列表中查找元素的过程和构造的过程基本一致：
对给定关键字k，由散列函数H计算出该元素的地址H(k)。

查找算法及查找常用数据结构总结

若表中该位置为空，则查找失败。
否则，比较关键字，若相等，查找成功，否则根据构造表时所采用的处理方法找下一个地址，直至找到关键字等于k的元素（成功）或者找到空位置（失败）为止。

一般在用拉链法构造的表中进行查找，比在用线性探测法构造的表中进行查找，查找长度要小。

查找方法平均查找长度失败查找长度哈希查找11+m (哈希冲突用拉链法处理，命中的地址中链表长度为m)

https://www.cnblogs.com/kongxudeshenghuo/p/16174567.html

https://zhuanlan.zhihu.com/p/477346381

https://zhuanlan.zhihu.com/p/639905710

https://blog.csdn.net/Jay_fearless/article/details/119454973

https://zhuanlan.zhihu.com/p/659174741

以上就是本篇文章【查找算法及查找常用数据结构总结】的全部内容了，欢迎阅览！文章地址：http://w.yusign.com/news/3286.html
资讯企业新闻行情企业黄页同类资讯首页网站地图返回首页述古往 http://w.yusign.com/mobile/ , 查看更多