3、紅黑樹

(圖c)

紅黑樹是一種自平衡二叉樹，在平衡二叉樹的基礎上每個節(jié)點又增加了一個顏色的屬性，節(jié)點的顏色只能是紅色或黑色。具有以下性質：

(1)根節(jié)點只能是黑色;

(2)紅黑樹中所有的葉子節(jié)點后面再接上左右兩個空節(jié)點，這樣可以保持算法的一致性，而且所有的空節(jié)點都是黑色;

(3)其他的節(jié)點要么是紅色，要么是黑色，紅色節(jié)點的父節(jié)點和左右孩子節(jié)點都是黑色，及黑紅相間;

(4)在任何一棵子樹中，從根節(jié)點向下走到空節(jié)點的路徑上所經(jīng)過的黑節(jié)點的數(shù)目相同，從而保證了是一個平衡二叉樹。

4、B-樹

圖d)

B-樹是一種平衡多路查找樹，它在文件系統(tǒng)中很有用。一棵m階B-樹(圖d為4階B-樹)，具有下列性質：

(1)樹中每個節(jié)點至多有m棵子樹;

(2)若根節(jié)點不是葉子節(jié)點，則至少有2棵子樹;

(3)除根節(jié)點之外的所有非終端節(jié)點至少有棵子樹;

(4)每個節(jié)點中的信息結構為(A0,K1,A1,K2......Kn,An)，其中n表示關鍵字個數(shù)，Ki為關鍵字，Ai為指針;

(5)所有的葉子節(jié)點都出現(xiàn)在同一層次上，且不帶任何信息，也是為了保持算法的一致性。