[prev] [index] [next]

Red-black Tree Performance

Cost analysis for red-black trees:
  • tree is well-balanced; worst case search is O(log2N)
  • insertion affects nodes down one path; max rotations is 2d
    (where d is the depth of the tree)
Only disadvantage is complexity of insertion/deletion code.

Note: red-black trees were popularised by Sedgewick.