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