数据结构与算法

1整理一些不熟悉的常见数据结构和算法

数据结构

BST

二叉查找树（Binary Search Tree），也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（orted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 没有键值相等的节点

优点：有序 缺点：极端条件下会退化成链表，降低查找效率

AVL

AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）,平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。

平衡二叉树也是一种特殊的二叉查找树，满足二叉查找树的特性

并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。 AVL树的查找稳定，查找、插入、删除的时间复杂度都为O（logN） 但是由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。

优点：有序，解决了BST会退化成线性结构的问题 缺点：进行插入和删除结点操作的时候，需要对结点进行频繁的旋转

红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，是一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性: （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树在查找方面和AVL树操作几乎相同。但是在插入和删除操作上，AVL树每次插入删除会进行大量的平衡度计算，红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，在插入和删除中AVL树所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。

红黑树广泛用于TreeMap、TreeSet，以及jdk1.8后的HashMap。

虽然红黑树是一种已经被性能优化了的自平衡的二叉查找树，插入修改效率和查找销量得到了平衡，但他依然存在一些问题。

1. 依旧在插入和删除时需要对节点进行旋转，频繁修改数据的场景影响效率。
2. 红黑树毕竟是一种二叉树，当数据量很大时，树的高度会变得很大，查找时经过的节点过多，效率变低。
3. 红黑树在内存中表现，但因为树的高度的问题，当使用磁盘等辅助存储设备读写数据时（如MySQL等数据库），会导致数据在磁盘中散布分散，并且IO次数过多，效率变低。
4. 适合单个查询，对于数据查询中常见的范围查询场景，无法很好支持。

针对于上述问题，有了天生为磁盘存储而生的B树。

以上三种树都是基于二叉树

二叉树每一个节点只能存放一个元素，并且每个节点只有两个子节点。当进行查找时，就需要多次磁盘IO 在实际应用中，数据是存放在磁盘中的，每次查询是将磁盘中的一页数据加入内存，树的每一层节点存放在一页中，不同层数据存放在不同页。 这样如果需要多层查询就需要多次磁盘IO。为了解决这个问题，就出现了B树

B-树

B树也是一种自平衡的树，在进行插入和删除操作时也需要对结点进行旋转等操作。 但是与AVL树和红黑树相比每个节点包含的关键字增多了，从而减小了树的深度，可以相对减少磁盘IO的次数。 特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度，因此B树被广泛用于文件系统及数据库中

弊端： B树的查找不稳定，最好的情况就是在根节点查到了，最坏的情况就是在叶子结点查到。 B树在遍历方面比较麻烦，由于需要进行中序遍历，所以也会进行一定数量的磁盘IO。

除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。

为了解决这些问题，出现了B+树。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B树的优势除了树高小，还有对访问局部性原理的利用。

所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。

在数据库应用中，B树的每个节点存储的数据量大约为4K, 这是因为考虑到磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次对磁盘进行IO数据读取时，同一个磁盘块的数据会被一次性读取出来，所以每一次磁盘IO都可以读取到B树中一个节点的全部数据。

对于顺数插入的数据，B树的结构优势可以使其在内存中顺序排列，存贮到同一个磁盘页中，顺序插入对磁盘的利用率和读取效率都非常友好。

场景：MySQL的InnbDB 索引。

B树虽然解决了磁盘存储的问题，但是在查询范围数据时依旧不够，比如你要查询1-5的数据，必须按照树的中顺遍历来访问各个节点。

对于这个问题，B+树对其进行了优化。

B+树

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。 2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树的优点：

1. B+树的层级更少：非叶子结点中存放的元素不存放数据，所以每一层可以容纳更多元素，比B-树更加“矮胖”，也就是磁盘中的每一页可以存放更多元素。这样在查找时，磁盘IO的次数也会减少
2. B+树查询速度更稳定：每次查找都必须匹配到叶子节点，因此每一次查找都是稳定的。B-树由于中间节点也携带数据，因此只需要匹配到要查找的元素即可，最好的情况是在根节点就结束查找，最坏的情况是在叶子节点结束查找，查找性能不稳定
3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在范围查询数据时候更方便，数据紧密性很高，缓存的命中率也会比B-树高。
4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描

关键区别总结

1. 平衡性：
   • AVL树：最严格平衡，查找效率最高，但维护成本高。
   • 红黑树：牺牲严格平衡换取插入/删除效率。
   • B树/B+树：通过多路分支降低树高，适合外存（如数据库/文件系统）。
2. 适用场景：
   • 内存操作：红黑树（Java TreeMap）、AVL树（查找密集型）。
   • 磁盘存储：B树（文件系统）、B+树（数据库索引）。
3. 退化风险：
   • 只有 BST 可能退化成 O(n)，其他均为平衡树。
4. 范围查询：
   • B+树 的叶子节点链表支持高效范围查询，优于B树。

堆

算法