更多算法汇总网站参考：

博哥玩算法：https://wansuanfa.com/

散列算法

不同编程语言实现的常见散列算法：

https://github.com/danharper/hmac-examples

二叉树

经过排序后的二叉查找树在动态插入、删除节点时表现出远优于线性链表的性能，使其非常适合于查找的数据结构。但这个数据结构存在一个最大的问题就是在最坏的情况下，有可能退化成一个链表。为了解决这个问题，便诞生很多二叉树变种。

B树

binary search tree，中文翻译为二叉搜索树、二叉查找树或者二叉排序树。简称为BST。

  1. 所有非叶子结点至多拥有两个儿子（Left和Right）；
  2. 所有结点存储一个关键字；
  3. 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

B-树

B-树是一种平衡的多路查找树。B-树中所有结点孩子结点个数的最大值称为B-树的阶，通常用m表示，从查找效率考虑，要求m >= 3

一颗m阶的B-树，或者为空树，或为满足下面特性的m叉树：

  1. 树中每个结点至多有m课子树。
  2. 若根结点不是叶子结点，则至少有两颗子树。
  3. 除根之外的所有非叶子结点至少有m/2（向上取整）颗子树。
  4. 所有的非叶子结点内关键字互不相等，且从小到大排列。
  5. 所有叶子结点都出现在同一层次上，并且不带信息（可以用空指针表示），可以看做查找失败到达的位置。

B+树

‌B树和B+树‌是最早被发明的，它们主要用于数据库索引，能够高效地处理大量的数据存储和检索。B树是一种自平衡的多路搜索树，而B+树是B树的变种，主要用于数据库系统，其中B+树的叶子节点形成了一个链表，便于进行范围查询。

B+树的特点

  • 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

  • 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接（每一个叶子节点都带有指向下一节点的指针）。

  • 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。（最大元素在根节点）

  • 如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。

B+树优于B树的几点内容：

  • 【IO次数更少】单一节点存储更多的元素，相同数据量时，比B树“矮胖”（查询时，IO操作少，性能更优）
  • 【查询性能稳定】 B+ 树每一次查找都到叶子节点，性能稳定；B树最好情况为只查根节点，最坏为查到叶子节点。
  • 【范围查询简便】 叶子节点形成有序链表，B+树范围查询时只需在链表上遍历即可。

B*树

二叉树小结

  • **B树：**二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
  • **B-树：**多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
  • **B+树：**在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
  • **B*树：**在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

AVL（平衡二叉树）

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。

一棵AVL树满足以下的条件:

  1. 它的左子树和右子树都是AVL树
  2. 左子树和右子树的高度差不能超过1

平衡的过程

  1. 在所有的不平衡情况中，都是按照先寻找最小不平衡树，然后寻找所属的不平衡类别，再根据 4 种类别进行固定化程序的操作。
  2. LL , LR ，RR ，RL其实已经为我们提供了最后哪个结点作为新的根指明了方向。如 LR 型最后的根结点为原来的根的左孩子的右孩子，RL 型最后的根结点为原来的根的右孩子的左孩子。只要记住这四种情况，可以很快地推导出所有的情况。
  3. 维护平衡二叉树，最麻烦的地方在于平衡因子的维护。建议读者们根据小吴提供的图片和动图，自己动手画一遍，这样可以更加感性的理解操作。

红黑树

二叉平衡树的严格平衡策略以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN) 的查找时间复杂度。但是这样做是否值得呢？能不能找一种折中策略，即不牺牲太大的建立查找结构的代价，也能保证稳定高效的查找效率呢？ 答案就是：红黑树。

红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构，能够做到一步旋转之内达到平衡。但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。

当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。

一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

RBT 的操作代价分析：

(1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。

(2) 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。

(3) 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。

RBT 效率总结 :

查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。

插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。

应用

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是 O(lgn)，效率非常之高。例如：

1.C++ STL 包括set、multiset、multimap、map，C++ 关联容器 ，Java容器中的TreeMap；

2.IO多路复用的epoll，内部用红黑树来维持我们想要监控的socket，以支持快速的插入和删除；

3.nginx中定时器是用红黑树来维持的，因为红黑树是有序的，每次从红黑树内部取出最小的定时器即可；

4.linux内核中用红黑树来管理进程的内存使用，进程的虚拟地址空间块都以虚拟地址为key值挂在这棵红黑树上。

MySQL中索引数据结构

分三类

  • B+树索引
  • Hash索引
  • 全文索引

hash索引查找时间复杂度为O(1)，如果只选一条数据，hash索引更优，但数据库常选多条数据，这时由于B+有序且链表相连，查询效率更高。数据库的索引一般存在磁盘上，数据量较大无法一次加载进内存时，B+树允许分批加载，同时树的高度较低，提高了查找效率。

参考阅读：

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

跳表（SkipList）

跳表的定义

  1. 跳表，又叫做跳跃表、跳跃列表，在有序链表的基础上增加了“跳跃”的功能
  2. 跳表在原来的有序链表上加上了多级索引，通过索引来快速查找；可以支持快速的删除、插入和查找操作。
  3. 跳表实际上是一种增加了前向指针的链表，是一种随机化的数据结构
  4. Redis中 的 SortedSet、LevelDB 中的 MemTable 都用到了跳表
  5. 对比平衡树, 跳表的实现和维护会更加简单, 跳表的搜索、删除、添加的平均时间复杂度是 O(logn)

跳表的性质

  1. 跳表由很多层结构组成，level是通过一定的概率随机产生的；
  2. 每一层都是一个有序的链表，默认是升序 ；
  3. 最底层(Level 1)的链表包含所有元素；
  4. 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现；
  5. 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

Redis为什么大量采用跳表

Redis 之所以使用跳表（Skip List），而不使用平衡树（如 AVL 树、红黑树等），是因为跳表在实现上比平衡树更加简单，而且在绝大多数情况下，跳表的效率和平衡树相当，甚至更优。具体来说，跳表的优点有：

  1. 实现简单：跳表的实现比平衡树简单，代码量少，易于理解和维护。
  2. 查询效率高：跳表的查询效率与平衡树相当，甚至更优。跳表的查询时间复杂度为 O(log n)，而平衡树的查询时间复杂度也为 O(log n)。但是，跳表的常数因子比平衡树小，因此在实际应用中，跳表的查询效率可能更高。
  3. 支持高效的插入和删除操作：跳表的插入和删除操作比平衡树更加高效。平衡树的插入和删除操作需要进行旋转操作，而跳表只需要修改相邻节点的指针即可。
  4. 空间利用率高：跳表的空间利用率比平衡树更高。跳表的节点只需要存储一个指针，而平衡树的节点需要存储两个指针和一个平衡因子。

参考阅读：

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

https://baijiahao.baidu.com/s?id=1710441201075985657

（完）