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.
|