1.redblack tree是一種簡單的自平衡樹。它通過屬性限制來實作樹的平衡,保證在樹上沒有一條路是别的路的2倍長。
2. 它有以下五條屬性限制:
1) 每個node是紅色或者黑色;
2) 每個葉子node是黑色;
3)根node是黑色;
4)若一個node是黑色,則它的兩個孩子node是紅色;
5) 對每個node,若有從這個node到它的子孫葉子(node)的路上包含有相同數目的黑色節點;
3. 本文的實作是參考introduction to algorithm 書中的講述;
4. 本文和stl map做了簡單的性能比較,結果基本上不相上下;
compile and run in visual studio 2005