2018年國(guó)家電網(wǎng)考試備考計(jì)算機(jī)之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(8)

3、紅黑樹(shù)

(圖c)

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

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

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

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

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

4、B-樹(shù)

圖d)

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

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

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

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

(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)在同一層次上，且不帶任何信息，也是為了保持算法的一致性。