[prev] 126 [next]

Red-black Tree Performance

Cost analysis for red-black trees:
  • tree is well-balanced; worst case search is O(log2 n)
  • insertion affects nodes down one path; #rotations+recolourings is O(h)
    (where h is the height of the tree)
Only disadvantage is complexity of insertion/deletion code.

Note: red-black trees were popularised by Sedgewick.