一、簡單介紹
紅黑樹是一種特定類型的二叉樹，它是在計(jì)算機(jī)科學(xué)中用來組織數(shù)據(jù)比如數(shù)字的塊的一種結(jié)構(gòu)。若一棵二叉查找樹是紅黑樹，則它的任一子樹必為紅黑樹。而由于每一顆紅黑樹都是一顆二叉排序樹，因此，在對(duì)紅黑樹進(jìn)行查找時(shí)，可以采用運(yùn)用于普通二叉排序樹上的查找算法，在查找過程中不需要顏色信息。
二、行為特征
紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹我們?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)。
三、紅黑樹和AVL樹
紅黑樹和AVL樹的區(qū)別在于它使用顏色來標(biāo)識(shí)結(jié)點(diǎn)的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴(yán)格的平衡。學(xué)過數(shù)據(jù)結(jié)構(gòu)的人應(yīng)該都已經(jīng)領(lǐng)教過AVL樹的復(fù)雜，但AVL樹的復(fù)雜比起紅黑樹來說簡直是小巫見大巫，紅黑樹才是真正的變態(tài)級(jí)數(shù)據(jù)結(jié)構(gòu)。