3、红黑树
(图c)
红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：
(1)根节点只能是黑色;
(2)红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色;
(3)其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间;
(4)在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。
4、B-树
图d)
B-树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B-树(图d为4阶B-树)，具有下列性质：
(1)树中每个节点至多有m棵子树;
(2)若根节点不是叶子节点，则至少有2棵子树;
(3)除根节点之外的所有非终端节点至少有棵子树;
(4)每个节点中的信息结构为(A0,K1,A1,K2......Kn,An)，其中n表示关键字个数，Ki为关键字，Ai为指针;
(5)所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。
