2018年国家电网考试备考计算机之数据结构与算法(8)

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)所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。