顺序查找
略
折半查找
折半查找，也称二分查找，在某些情况下，折半查找比顺序查找效率更高（要求静态查找表中数据必须有序）
折半查找效率为：logN
一般用递归来实现。
总结：
1.折半查找算法只适用于有序表，同时只能查找顺序存储结构。
2.当查找表使用链式存储结构，折半查找无法有效的进行比较操作
分块查找
分块查找，也叫索引顺序查找，算法实现除了需要查找表本身之外，还需要根据查找表建立一个索引表。
image.png
图中，查找表中共 18 个查找关键字，将其平均分为 3 个子表，对每个子表建立一个索引，索引中包含中两部分内容：该 子表部分中最大的关键字以及第一个关键字在总表中的位置，即该子表的起始位置。
建立的索引表要求按照关键字进行升序排序，查找表要么整体有序，要么分块有序。
分块有序指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字，第三个子表的所有关键字都要大于第二个子表中 的最大关键字，依次类推
分块查找的过程分为两步进行：
- 1.确定要查找的关键字可能存在的具体块（子表）
- 2.在具体的块中进行顺序查找
分块查找的性能分析
总体来说，分块查找算法的效率介于顺序查找和折半查找之间。
二叉查找树
二叉查找树BST(binary search/sort tree) ,又叫二叉查找树或者二叉排序树，它首先是一个二叉树，并且满足一下条件：
- 1.若左子树不为空，则左子树上所有节点的值均小于它的根节点的值。
- 2.若右子树不为空，则右子树上所有节点的值均大于它的根节点的值。
-
3.左右子树也分别为二叉排序树
二叉查找树（二叉排序树）
如果二叉树查找树的所有非叶子节点的左右子树节点数据均保持差不多(平衡)，那么二叉查找树搜索性能逼近于二分查找。但它相对于连续内存空间的二分查找的优点是：
插入与删除结点，不需要移动大段的内存，甚至通常是常数开销
但二叉查找树在多次删除插入之后，有可能导致变为链表结构。搜索性能已经是线性的了。
实际使用的二叉查找树都是在原基础上加入了平衡算法。即平衡二叉树。
平衡二叉树（AVL树）
AVL自平衡二叉查找树
平衡二叉树用平衡因子差值来判断是否平衡，并旋转二叉树。平衡因子：左右子树高度差。平衡二叉树里平衡因子不能超过1，否则旋转。（常用平衡二叉树算法有红黑树，AVL，Treap，伸展树等）。
这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
windows对进程地址空间的管理用到了AVL树。
旋转
LL，RR 一次旋转
LR，RL 双旋转(先左后右，先右后左)
红黑树
红黑树（RB-Tree）是一种自平衡的二叉查找树，他的节点为红色和黑色，不像AVL树严格控制左右子树的高度差。红黑树的特性
- 1.节点是红色或黑色。
- 2.根节点是黑色。
- 3.叶子节点是黑色。
- 4.一个红色节点只能有0个到2个黑色节点。
- 5.叶子节点到根节点的路径上黑色节点的数量是相同的。
红黑树
红黑树能以O(logN)的时间复杂度进行搜索，插入和删除操作。红黑树在查找方面与AVL树操作几乎相同。但是在插入和删除操作上，AVL树每次插入删除会进行大量的平衡度计算，红黑树牺牲了严格的平衡为代价，他只要求部分达到平衡要求，降低了对旋转的要求，从而提高了性能。任何不平衡都会在三次旋转之内解决。
红黑树能确保任何一个节点的左右子树高度差不会超过二者中较低那一个的一倍。
红黑树广泛用于TreeMap、TreeSet、以及JDK1.8的hashMap。
B树
B树（Blance-Tree）平衡树，也叫作B-树，是多路查找平衡树（可能是二叉也可能是多叉）。
B树是一个高度平衡树。
一个M阶的B树规定了：
- 1.树中每个节点至多有m棵子树（两棵子树指针夹着一个关键字）
- 2.若根节点不是叶子节点，至少有两棵子树（至少一个关键字）
- 3.除根节点之外的所有非终端节点至少有[m/2]棵子树。（即至少包含有[m/2]-1个关键字）
- 4.所有的叶子节点出现在同一层次上。实际上这些节点都不存在，只想这些节点的指针都为null。
- 5.每个非终端结点中包含有n个关键字信息： (n，A0，K1，A1，K2，A2，……，Kn，An)。其中
- a)Ki (i=1…n)为关键字，且关键字按顺序排序Ki < K(i-1)
- b)Ai为指向子树根的接点，且指针A(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
- c) 关键字的个数n必须满足： [m/2]-1 <= n <= m-1
3阶二叉树示例,蓝色为K（关键字），黄色为A(子树指针)
B树拆入删除 节点分裂合并视频
https://www.bilibili.com/video/av36069871?from=search&seid=10258516047823270671
B树有以下特性：
- 1.关键字集合分布在整棵树中。
- 2.任何一个关键字出现只能出现在一个节点中。
- 3.搜索有可能在非叶子节点结束。
- 4.其搜索性能等价于在关键字全集内做一次二分查找。
- 5.自动层次控制。
- 6.每个节点都存有索引和数据，也就是对应的key和value。
B树对于红黑树的优势很明显了，最明显的就是B树一个结点存放了多个关键字。节点越多，B~树比平衡二叉树所用的操作次数将越少，效率也越高。
B树一般应用于文件管理，或外部存储的地址管理。mongoDB也是用B树索引。
一棵含n个结点的B树的高度为O（lgn），所以，B树可以在O（logn）时间内（没有计算分裂合并的时间），实现各种如插入（insert），删除（delete）等动态集合操作。
，一般用于数据库中做索引，因为它们分支多层数少，因为磁盘IO是非常耗时的，而像大量数据存储在磁盘中所以我们要有效的减少磁盘IO次数避免磁盘频繁的查找。
B树有一些场景不友好，比如范围查找。
B树在提高自盘IO性能的同时，并没有解决元素遍历的效率问题，而B+树可以解决。B+树只要遍历叶子节点就可以实现整个树的遍历。
B+树
B树，B+树：它们特点是一样的，是多路查找树
B+树是B树的变种树，有n棵子树的节点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子节点。是为文件系统而生的。
B+树具有以下特性：
- 1.有n棵子树的节点中含有n个关键字
- 2.所有的非叶子节点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大的顺序进行连接（B树的非叶子节点也包含了数据信息）
- 3.根节点和中间结点 只做索引，不包含数据指针以及数据
- 4.叶子结点包含所有数据，并按照从小到大顺序排列
- 5.叶子结点用指针连在一起
B+树的头指针有两个，一个指向根节点，另一个指向关键字最小的元素，因此B+树有两种遍历的方式：
1.从根节点开始随机查询
2.从最小关键词顺序查询
B+树
B+树相对B树磁盘读写代价更低：因为B+树非叶子结点只存储键值，单个节点占空间小，索引块能够存储更多的节点，从磁盘读索引时所需的索引块更少，所以索引查找时I/O次数较B-Tree索引少，效率更高。而且B+Tree在叶子节点存放的记录以链表的形式链接，范围查找或遍历效率更高。Mysql InnoDB用的就是B+Tree索引。
B+树也需要分裂和合并
Trie树
单词查找树 DFA
Trie树：
又名单词查找树，一种树形结构，常用来操作字符串。它是不同字符串的相同前缀只保存一份。
相对直接保存字符串肯定是节省空间的，但是它保存大量字符串时会很耗费内存（是内存）。
类似的有：前缀树(prefix tree)，后缀树(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree（解决耗费内存问题），以及前面说的double array trie。
前缀树：字符串快速检索，字符串排序，最长公共前缀，自动匹配前缀显示后缀。
后缀树：查找字符串s1在s2中，字符串s1在s2中出现的次数，字符串s1,s2最长公共部分，最长回文串。
trie 树的一个典型应用是前缀匹配，比如下面这个很常见的场景，在我们输入时，搜索引擎会给予提示。
image.png
hash查找法
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
是一种以空间换时间的算法。
布隆过滤器就是一种hash查找法，以空间换时间。存在hash冲突。
散列规则：直接定址法，数字分析法，平方取中法，折叠法，随机数法，储留余数法。
网友评论