天天看點

泛型的RedBlack Tree的實作,并和STL map 做了簡單的性能比較

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

繼續閱讀