一、簡(jiǎn)單介紹
紅黑樹(shù)是一種特定類(lèi)型的二叉樹(shù)，它是在計(jì)算機(jī)科學(xué)中用來(lái)組織數(shù)據(jù)比如數(shù)字的塊的一種結(jié)構(gòu)。若一棵二叉查找樹(shù)是紅黑樹(shù)，則它的任一子樹(shù)必為紅黑樹(shù)。而由于每一顆紅黑樹(shù)都是一顆二叉排序樹(shù)，因此，在對(duì)紅黑樹(shù)進(jìn)行查找時(shí)，可以采用運(yùn)用于普通二叉排序樹(shù)上的查找算法，在查找過(guò)程中不需要顏色信息。
二、行為特征
紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹(shù)，顏色或紅色或黑色。在二叉查找樹(shù)強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹(shù)我們?cè)黾恿巳缦碌念~外要求:
性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。
性質(zhì)2. 根節(jié)點(diǎn)是黑色。
性質(zhì)3.所有葉子都是黑色。（葉子是NUIL節(jié)點(diǎn)）
性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）
性質(zhì)5.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
三、紅黑樹(shù)和AVL樹(shù)
紅黑樹(shù)和AVL樹(shù)的區(qū)別在于它使用顏色來(lái)標(biāo)識(shí)結(jié)點(diǎn)的高度，它所追求的是局部平衡而不是AVL樹(shù)中的非常嚴(yán)格的平衡。學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的人應(yīng)該都已經(jīng)領(lǐng)教過(guò)AVL樹(shù)的復(fù)雜，但AVL樹(shù)的復(fù)雜比起紅黑樹(shù)來(lái)說(shuō)簡(jiǎn)直是小巫見(jiàn)大巫，紅黑樹(shù)才是真正的變態(tài)級(jí)數(shù)據(jù)結(jié)構(gòu)。