python算法学习笔记之查找算法

一、基本概念

1.1 平均查找长度

查找算法可以分为比较式查找算法（基于线性表的查找算法和基于树的查找法）和计算式查找算法 （散列查找(Hash查找法)）

1.2 每种算法的复杂度分析

如何理解复杂度为 O(logn)：

参考链接7

二、基于线性表的查找法

2.1 顺序查找法

顺序查找法也成为线性查找，属于无序查找。

2.2 折半查找法

该算法只适合有序数列，其关键在于不断与区间的中间元素进行对比。首先需要构建满二叉树

序列0，5，8，11，15，19，30，55，60，62，67，90.

一共有12个元素所以12/2，第6个元素是根节点。在第六个元素的左边1+5/2=3，所以第二层的左子树为第3个元素8，在3的左边1+2/2=1.5，[1.5]=1,所以第三层左子树是第一个元素0.第二个元素是该节点的左子树。

失败节点

黄色框表示失败节点，一共有13个失败节点，所示失败查找长度=（3*3+4*10）/13。

2.3 插值查找法

插值查找，是二分查找算法的改进，按照数据分布，利用公式预测键值所在位置。

middle = left+(target-data[left])/(data[right]-data[left])*(right-left)

2.4 分块查找法

该算法将一个大的线性表分解成若干块，每块中的节点可以任意存放，块之间必须排序。与此同时，还要建立一个索引表，把每块中最大值作为索引表的索引值，此索引表需要按块的顺序存放到一个辅助数组中。查找时首先在索引表中进行查找，确定要找的节点所在块，可以采用二分查找算法或顺序查找算法，然后在块中采用顺序查找算法。

结构：

平均查找长度：

三、基于树的查找法

3.1 二叉排序树（BST）

算法简介

    二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。 

 算法思想

　　二叉查找树（BinarySearch Tree）或者是一棵空树，或者是具有下列性质的二叉树：
　　    1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
　　    2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
　　    3）任意节点的左、右子树也分别为二叉查找树。

　　二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

复杂度分析 

     它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。

构建二叉搜索树：依次插入就可以

删除操作：如果删除叶子节点删除就可以，如果删除的是只有左子树或者右子树的节点，先找到节点的位置，让这个子树替代这个节点然后删除这个子树的节点，如果删除的节点有左右子树，找到这个节点的左子树中最大的节点，代替这个节点，然后删除这个最大的节点，或者找右子树中最小的去替代这个节点去代替他。

3.2 平衡二叉树（AVL树）

1.使树在结构上左右分支平衡，所有节点的（左子树高度-右子树高度）的绝对值<=1。

2.平衡因子=左子树高度-右子树高度，所有节点的平衡因子的绝对值都小于等于1就是平衡二叉树。

3.也是二叉搜索树，只是操作后需要检查是否失衡，发现失衡后需要进行调整。

数据结构之——平衡二叉树（内容详解）-CSDN博客

平衡二叉树插入：

1. LL 型：插入左孩子的左子树，被破坏节点右旋
2. RR 型：插入右孩子的右子树， 被破坏节点左旋
3. LR 型：插入左孩子的右子树，先左旋被破坏节点的左子节点0，再右旋被破坏节点
4. RL 型：插入右孩子的左子树，先右旋被破坏节点的右子节点0，再左旋被破坏节点

平衡二叉树删除：

删除的节点在右子树，即在右边删除而导致树失衡，此时左子树高度会大于右子树，右子树删除有三种调节方式。

第一种：删除后被破坏节点的左节点的左边高度大于右边高度。右旋被破坏节点。

第二种：删除后被破坏节点的左节点的左边高度小于右边高度。先对被破坏节点的L（左）节点进行L（左）旋，再对被破坏节点进行R（右）旋即可。

第三种：删除后被破坏节点的左节点的左边高度等于右边高度。对被破坏节点进行右旋。

删除的节点在左子树：

第一种：删除后被破坏节点的左节点的左边高度小于右边高度。进行左旋。

第二种：删除后被破坏节点的右节点的左边高度大于右边高度。先对被破坏节点的R（右）节点进行R（右）旋，再对被破坏节点进行L（左）旋。

第三种：删除后被破坏节点的左节点的左边高度等于右边高度。对被破坏节点进行左旋。

3.3 B树（平衡多路查找树）

访问节点是在硬盘上进行的。节点内的数据操作是在内存中进行的。降低树高可以降低硬盘访问次数，因为硬盘速度很慢。B树就是一个节点可以拥有多于两个子节点的二叉查找树。

B树的叶子节点：内部节点的最后一层为叶子节点。

查找

因为是有序的所以可以顺序查找和折半查找

插入

先通过查找方法找到要插入的位置，如果插入的节点超过了B树的节点数量限制就需要调整。

上取整

上移之后继续判断是否有溢出，如果一直到根节点都有上溢出，根节点分裂后创建新的根节点。

构建

删除

插入可能会上溢出，删除容易出现下溢出的情况。

以如下树为例：

删除非叶节点用直接前驱和直接后继直接代替删除，删除45，可以用44或者46替代他。

删除68叶子节点，出现了下溢出，尝试和左右兄弟借元素，如果借60就将65下移到72，然后60上移，如果借76，就将74下移，76上移。

删除86，叶节点，左右兄弟都不够借，可以与其他兄弟合并。比如合并左兄弟。将76下移，然后83合并。

或者合并右兄弟，将90下移然后将83合并到右兄弟。 

删除30为非叶节点，用后驱40替代他，然后41节点下溢，但是左右兄弟都不够借，就需要合并，42下移，然后合并41，42，43，44.这时40在的节点下溢出，需要看40的右兄弟够不够，需要将46下移，然后51上移，还需要将47，50在的节点移动到左边。

删除57

删除53 ，下溢出，右兄弟不够，需要合并，这个时候76节点也会下溢，需要与兄弟合并。这个时候就会没有根节点需要删除

3.4 B+树

一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4.更适合文件索引系统；

3.5 红黑树

红黑树是一种自平衡的二叉搜索树，它的每个节点都存储着数据以及一个表示颜色的位（红色或黑色）。这种数据结构通过以下特定的规则来保持其平衡性：

1. 节点颜色：红黑树中的每个节点只能是红色或黑色，不能为其他颜色。这条规则的作用是区分红色节点和黑色节点，并且保证红黑树的平衡性。
2. 根节点颜色：根节点必须是黑色。如果根节点是红色的，可能会导致红黑树的高度增加，从而影响查找、插入和删除的性能。
3. 红色节点子节点颜色：如果一个节点是红色的，则它的两个子节点（如果存在）必须是黑色的。也就是说，任意一条路径上不会有两个连续的红色节点。这条规则进一步限制了红色节点的分布，有助于保持树的平衡。
4. 路径上黑色节点数量：对于任意节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。这里的叶节点通常指的是指向NULL节点的“外部节点”或“空节点”。这条规则保证了红黑树的平衡性，从而保证了其查找、插入和删除的时间复杂度为O(log n)。

此外，有些资料还会提到第五条规则，即每个叶子节点（最后一个节点）都是黑色的，这其实是第四条规则的一个推论，因为在红黑树中，叶子节点通常被视为指向NULL的节点，而所有这样的节点都被视为黑色。

红黑树中叶子节点的定义

黑路同：

7的右子树到叶节点的节点数量比左子树多了一个节点12，违反了黑路同

插入

插入元素：默认为插入红色，因为插入红色节点代价更小，只会出现违反根叶黑和不红红的要求，

如果插入后红黑树的性质被破坏处理方法：

1.插入节点是根节点：直接将这个节点变黑。

2.插入节点的叔叔是红色：

处理方法，对cur的父亲、叔叔和爷爷都进行变色

3.插入节点的叔叔是黑色：

（1）LL型

按照AVL树对被破坏的节点7右旋然后对旋转中心点和旋转点进行变色

（2）RR型

左旋被破坏的节点7然后对7和9变色

（3）LR型 

旋转后的结果

最后对旋转中心点和旋转点进行变色

第四种情况RL型

旋转后结果

最后对旋转中心点和旋转点进行变色

红黑树构建，依次插入每个节点，每插入一个节点都需要判断是否破坏了红黑树的性质。

删除

删除容易破坏黑路同的性质。

红黑树的删除与二叉搜索树一致，分类讨论

1.删除的节点没有孩子

删除红色不需要调整

删除黑色节点必然会破坏黑路同

红黑树旋转：插入是对被破坏的节点进行旋转，删除是对父节点的父节点进行旋转

2.删除的节点只有左子树或者只有右子树-直接代替

只会有黑-红的情况，因为黑-红-红违反不红红规则，黑-红-黑违反同黑规则。

也不会右红-黑的情况，因为违反黑路同。

例子：比如要删除节点17，只有右子节点19，用19代替他。这个时候会违反黑路同的性质，所以需要将19变色。

3.左右子树都有-直接前驱或者直接后驱替代，然后删除（转换成前两种情况）

3.6 2-3查找树

四、散列法

4.1基本概念

散列表（哈希表）：是一种数据结构。目标元素和存储位置的对应表格，被称为哈希表。要构造哈希表，就需要指定哈希函数。。在Python中，字典（dict）就是一种实现哈希表的数据结构。字典使用键值对来存储数据，其中键是唯一的标识符，而值可以是任何类型的数据。通过键可以直接访问对应的值，无需遍历整个数据结构。

散列函数（哈希函数）：用来建立目标元素和存储位置（槽位）映射关系的函数。映射关系的函数多种多样，所以哈希函数也是多种多样。

冲突：计算出来的地址已经存储出来其他元素。

同义词：散列函数算出来的同一地址的关键字成为同义词。

  在Python中，散列查找算法是一种高效的数据检索方法，它利用哈希表、哈希集合和哈希映射等数据结构来实现。这些数据结构基于哈希函数，将数据元素映射到固定大小的整数，以便快速查找、插入和删除操作。

4.2散列函数构造方法

定义域和值域的约束、尽可能减少冲突和尽可能简单

4.2.1除留余数法

4.2.2 直接定址法

 4.2.3 数据分析法

以电话号码后四位连续但不均匀的值作为散列函数

 

4.2.4平方取中法

 

 4.3 处理冲突的方法

4.3.1拉链法

把所有“同义词”存储在一个链表中，进行排序

4.3.2开放地址法

如果发生“冲突”，就给新元素找一个空闲位置。

线性探测法

 探测覆盖率：100%

平方探测法

探测覆盖率：至少可以探测到一半的位置 ，m为4j+3的质数时，可以探测100%。

双散列法

探测覆盖率：未必能探测到所有位置，主要取决于第二个散列位置是否合理。 

伪随机序列法

删除只能逻辑删除，不能物理删除。，需要定期整理进行物理删除。

装填因子=记录数/表长。越大表示越满，越容易冲突，效率越低。

五、斐波那契查找法

5.1 斐波那契数列

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。

斐波那契查找原理与二分查找相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近。

步骤

斐波那契查找的整个过程可以分为：

• 构建斐波那契数列；

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

• 计算数组长度对应的斐波那契数列元素个数；

[1, 2, 4, 6, 7, 9, 13,16, 17, 21, 23, 25, 27, 31, 45, 56, 58, 61, 65, 67, 73, 75, 88, 93, 102]

可知上述数据共25个元素，不对应斐波那契数列中任何F(n)，这种情况是很常见的。此时，策略是采用“大于数组长度的最近一个斐波那契数值”。比如当前数组长度为25，斐波那契数列中大于25的最近元素为34。 

• 对数组进行填充；

确定了斐波那契数值后，就要进行数值填充，即将数组从25个元素填充到34个。填充时，将第26到34个元素均采用第25个元素值进行填充，即最大值填充。

• 循环进行区间分割，查找中间值；

mid=left+F（n-1）-1

此时数组被分割为左右两个区间，左边区间含有F(n-1)个元素，-1是因为下标从0开始（比如F(1)表示两个元素）。 

• 判断中间值和目标值的关系，确定更新策略；

中间值和目标值有三种大小关系，分别对应三种处理方式：

• 相等，则查找成功，返回中间位置即可；
• 中间值小于目标值，则说明目标值位于中间值到右边界之间（即右区间），右区间含有F(n-2)个元素，所以n应该更新为n=n-2；
• 中间值大于目标值，这说明目标值位于左边界和中间值之间（即左区间），左区间含有F(n-1)个元素，所以n应更新为n=n-1；

终于学完了！！要吐了

参考说明

以下作者都讲解的非常好！！！！建议想学习透彻的复习的时候反复听

1.折半查找判定树画法与ASL_哔哩哔哩_bilibili

2.数据结构34-分块查找及平均查找长度_哔哩哔哩_bilibili

3.七大查找算法（Python） - ls秦 - 博客园 (cnblogs.com)

4.红黑树 - 定义, 插入, 构建_哔哩哔哩_bilibili

5.斐波那契查找原理——附python和C++实现 - 知乎 (zhihu.com)

6.[Day71] 散列查找处理冲突的方法，装填因子_哔哩哔哩_bilibili

7.算法复杂度O(logn)详解-CSDN博客