一、簡(jiǎn)單介紹

　　紅黑樹(shù)是一種特定類(lèi)型的二叉樹(shù)，它是在計算機科學(xué)中用來(lái)組織數據比如數字的塊的一種結構。若一棵二叉查找樹(shù)是紅黑樹(shù)，則它的任一子樹(shù)必為紅黑樹(shù)。而由于每一顆紅黑樹(shù)都是一顆二叉排序樹(shù)，因此，在對紅黑樹(shù)進(jìn)行查找時(shí)，可以采用運用于普通二叉排序樹(shù)上的查找算法，在查找過(guò)程中不需要顏色信息。

　　二、行為特征

　　紅黑樹(shù)是每個(gè)節點(diǎn)都帶有顏色屬性的二叉查找樹(shù)，顏色或紅色或黑色。在二叉查找樹(shù)強制一般要求以外，對于任何有效的紅黑樹(shù)我們增加了如下的額外要求:

　　性質(zhì)1. 節點(diǎn)是紅色或黑色。

　　性質(zhì)2. 根節點(diǎn)是黑色。

　　性質(zhì)3.所有葉子都是黑色。（葉子是NUIL節點(diǎn)）

　　性質(zhì)4. 每個(gè)紅色節點(diǎn)的兩個(gè)子節點(diǎn)都是黑色。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續的紅色節點(diǎn)）

　　性質(zhì)5.從任一節點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數目的黑色節點(diǎn)。

　　三、紅黑樹(shù)和AVL樹(shù)

　　紅黑樹(shù)和AVL樹(shù)的區別在于它使用顏色來(lái)標識結點(diǎn)的高度，它所追求的是局部平衡而不是AVL樹(shù)中的非常嚴格的平衡。學(xué)過(guò)數據結構的人應該都已經(jīng)領(lǐng)教過(guò)AVL樹(shù)的復雜，但AVL樹(shù)的復雜比起紅黑樹(shù)來(lái)說(shuō)簡(jiǎn)直是小巫見(jiàn)大巫，紅黑樹(shù)才是真正的變態(tài)級數據結構。