红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。
它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(lg(n)) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。
伸展树（英语：Splay Tree）是一种能够自我平衡的二叉查找树，它能在均摊 O(log n) 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。
它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。
考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。
ps: 这个思想实际上非常的简单，也非常的实用。我们以前实现的 LFU 的思想是类似的。
2–3树是一种树型数据结构，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。
2–3树由约翰·霍普克洛夫特于1970年发明。
2–3树和AA树是等距同构的，意味着它们是同一种数据结构。
换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。
2–3树是平衡树，意味着右边，左边，中间的子树的元素数量都是相同或接近的。
（1）2-3 树要么为空要么具有以下性质：
在1970年，Bayer＆McCreight发表的论文《ORGANIZATION AND MAINTENANCE OF LARGE ORDERED INDICES》（大型有序索引的组织和维护）中提出了一种新的数据结构来维护大型索引，这种数据结构在论文中称为B Tree。
h：代表树的高度，k 是个自然数，一个B树要么是空的，要么满足以下条件：
所有叶子节点到根节点的路径长度相同，即具有相同的高度；（树是平衡的）
每个非叶子和根节点（即内部节点）至少有 k+1 个孩子节点，根至少有 2 个孩子；（这是关键的部分，因为节点都是分裂而来的，而每次分裂得到的节点至少有 k 个元素，也就有 k+1 个孩子；但根节点在分裂后可能只有一个元素，因为不需要向上融合，中间元素作为新的根节点，因此最少有两个孩子。而叶子节点没有孩子。）
每个节点最多有 2k+1 个孩子节点。（规定了节点的最大容量）
每个节点内的键都是递增的
B+ 树是应文件系统所需而产生的一种B Tree的变形树。
B Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。
与B Tree相比，B+Tree有以下不同点：
每个节点的指针上限为2d而不是2d+1。
内节点不存储data，只存储key；叶子节点不存储指针。
图3是一个简单的B+Tree示意。
B* Tree 是 B+ Tree的变体，在 B+ Tree的非根和非叶子结点再增加指向兄弟的指针；
B* Tree定义了非叶子结点关键字个数至少为 (2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。
给出了一个简单实例，如下图所示：
图是数据结构中最为复杂的一种，我在上大学的时候，图的这一章会被老师划到考试范围之外，作为我们的课后兴趣部分。
但实际上，图在信息化社会中的应用非常广泛。图主要包括：
无向图，结点的简单连接
有向图，连接有方向性
加权图，连接带有权值
加权有向图，连接既有方向性，又带有权值
图是由一组顶点和一组能够将两个顶点相连的边组成。
常见的地图，电路，网络等都是图的结构。
求解单元点的最短路径问题：给定带权有向图G和源点v，求v到G中其他顶点的最短路径
限制条件：图G中不存在负权值的边（这个可以通过弗洛伊德算法，后期将进行讲解）
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。
在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。
从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。
B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。
B+ 树元素自底向上插入，这与二叉树恰好相反。
B+ 树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。
B+ 背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B+ 树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树（常简称为2-3 树）中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。
