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博客
平衡二叉树插入:
- LL 型:插入左孩子的左子树,被破坏节点右旋
- RR 型:插入右孩子的右子树, 被破坏节点左旋
- LR 型:插入左孩子的右子树,先左旋被破坏节点的左子节点0,再右旋被破坏节点
- 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 红黑树
红黑树是一种自平衡的二叉搜索树,它的每个节点都存储着数据以及一个表示颜色的位(红色或黑色)。这种数据结构通过以下特定的规则来保持其平衡性:
- 节点颜色:红黑树中的每个节点只能是红色或黑色,不能为其他颜色。这条规则的作用是区分红色节点和黑色节点,并且保证红黑树的平衡性。
- 根节点颜色:根节点必须是黑色。如果根节点是红色的,可能会导致红黑树的高度增加,从而影响查找、插入和删除的性能。
- 红色节点子节点颜色:如果一个节点是红色的,则它的两个子节点(如果存在)必须是黑色的。也就是说,任意一条路径上不会有两个连续的红色节点。这条规则进一步限制了红色节点的分布,有助于保持树的平衡。
- 路径上黑色节点数量:对于任意节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。这里的叶节点通常指的是指向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博客