（1）每个节点或者是黑色，或者是红色；（2）根节点是黑色；（3）如果一个节点是红色的，则它的子节点必须是黑色的；（4）从一个节点到NULL节点的任意路径上包含相同数目的黑节点（确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接衡的二叉树）；
着色法则的一个推论是，红黑树的高度最多是 2log(N + 1)。经验指出，平均红黑树大约和平均AVL树一样深，从而查找时间一般接近最优，红黑树的优点是执行插入所需要的开销相对于AVL较低，再有就是实践中发生的旋转相对较小。但是，红黑树的具体实现是复杂的，不仅因为有大量可能的旋转，而且还因为一些子树可能是空的，以及处理根的特殊情况（尤其是根没有父节点）。
两种方法都会涉及单旋转与双旋转的操作，类似AVL树，但注意还要变换颜色。
AVL 树和红黑树的比较：1）如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。2）其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。3）map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。
**B＋tree **是一个n叉树，每个节点有多个叶子节点，一颗B+树包含根节点，内部节点，叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上叶子节点的节点。
1.n棵子tree的节点包含n个关键字，不用来保存数据而是保存数据的索引。
2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的非终端结点可以看成是索引部分，结点中仅含其子树中的最大（或最小）关键字。
B 树 通常我们所说的 B树 或 B-树，其实指的是一种树，这里我将其称为 B树。一颗 M 阶的 B树具有以下特点：1）树的根或者是一片叶子，或者其儿子数在 2 和 M 之间；2）除根外，所有非树叶节点的儿子数在 ⌈M/2⌉ 和 M 之间；3）所有的树叶都在相同的深度上。B...
B树的定义 一棵m阶的B树满足下列条件： 树中每个结点至多有m个孩子。 除根结点和叶子结点外，其它每个结点至少有m/2个孩子。 根结点至少有2个孩子（如果B树只有一个结点除外）。 所有叶结点在同一层，B树的叶结点可以看成一种外部节点，不包含任何信息。 有k个关键字(关键字按...