更为详细内容请参看 《大话数据结构》第 8 章相关内容
多路查找树(multi-way search tree)，其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
在这里，每一个节点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解它的 4 种特殊形式：2-3树，2-3-4树，B树，B+树
2-3 树
- 2-3树是这样的一棵多路查找树：其中的每一个节点都具有两个孩子(我们称它为 2 节点)或三个孩子(我们称它为 3 节点)
- 一个 2 节点包含一个元素和两个孩子(或没有孩子)，且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个 2 节点要么没有孩子，要么就有两个，不能只有一个孩子
- 一个 3 节点包含一大一小两个元素和三个孩子(或没有孩子)，一个 3 节点要么没有孩子，要么具有 3 个孩子。如果某个 3 节点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素
-
并且 2-3 树种所有的叶子都在同一层次上。如下图所示就是一颗有效的 2-3 树
2-3 树实例 - 事实上，2-3 树复杂的地方就在于新节点的插入和已有节点的删除。毕竟每个节点可能是 2 节点也可能是 3 节点，要保证所有叶子都在同一层次，是需要一番复杂操作的。
- 2-3 树的插入实现 ...
- 2-3 树的删除实现 ...
2-3-4 树
- 有了 2-3 树的讲解，2-3-4 树就很好理解了，它其实就是 2-3 树的概念扩展，包括了 4 节点的使用。
- 一个 4 节点包含小中大三个元素和四个孩子(或没有孩子)，一个 4 节点要么没有孩子，要么具有 4 个孩子。
- 如果某个 4 节点有孩子的话，左子树包含小于最小元素的元素；第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素
B 树
B树 (B-tree) 是一种平衡的多路查找树，2-3 树和 2-3-4 树都是 B 树的特例。节点最大的孩子数目称为 B 树的阶(order)，因此，2-3 树是 3 阶 B 树，2-3-4 树是 4 阶 B 树
B+ 树
尽管前面我们已经讲了 B 树的诸多好处，但其实它还是有缺陷的。对于树结构来说，我们都可以通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行的
红黑树 RB-tree
红黑树是另一个被广泛使用的平衡二叉搜索树。 (注意，也是二叉搜索树上通过节点颜色保持平衡)
因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。
红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质：
１、每个结点要么是红的要么是黑的。
２、根结点是黑的。
３、如果一个结点是红的，那么它的两个儿子都是黑的。
４、对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
