摘要: 紅黑樹本質(zhì)是二叉查找樹的一種，它的性能高于普通的二叉查找樹，即使是在最壞的情況下也能保證時(shí)間復(fù)雜度為O(lgn)。紅黑樹在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色（或紅或黑，故稱紅黑樹）。通過對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹可以保證沒有一條路徑會(huì)比其他路徑長出兩倍，因而是接近平衡的。
紅黑樹的每個(gè)結(jié)點(diǎn)至少包含五個(gè)域：color，key，left，right 和 parent（一般我們都會(huì)在結(jié)點(diǎn)中存儲(chǔ)額外的數(shù)據(jù) data，但前面的五個(gè)域是必不可少的），如果某個(gè)結(jié)點(diǎn)沒有子結(jié)點(diǎn)或者結(jié)節(jié)點(diǎn)，則將相應(yīng)的指針設(shè)置為空值（NIL，注意不是 NULL，NIL是一個(gè)特定的空結(jié)點(diǎn)對(duì)象，類似于Obj-C 中 Nil對(duì)象）。我們將這些 NIL 當(dāng)作葉子結(jié)點(diǎn)（在實(shí)際處理過程中，往往將最底層的孩子結(jié)點(diǎn)和根結(jié)點(diǎn)的父親都指向同一個(gè) NIL 結(jié)點(diǎn)，以便于處理紅黑樹代碼中的邊界條件），而將其它結(jié)點(diǎn)當(dāng)作內(nèi)結(jié)點(diǎn)。
閱讀全文