3、紅黑樹

(圖c)

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

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

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

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

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

4、B-樹

圖d)

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

(1)樹中每個(gè)節(jié)點(diǎn)至多有m棵子樹;

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

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

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

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