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