Search code examples
algorithmtreeavl-treered-black-tree

How is insertion and deletion more faster in red black tree than AVL tree?


I would like to understand the difference bit better, but haven't found a source that can break it down to my level.

I am aware that both trees require at most 2 rotations per insertion. Then how is insertion faster in red-black trees?

And how insertion requires O(log n) rotations in avl tree while O(1) in red-black?


Solution

  • Well, I don't know what your level is, exactly, but to put it simply, red-black trees are less balanced than AVL trees. For red-black trees, the path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf, while for AVL trees there is never more than one level difference between two neighboring subtrees. This makes insertions and deletions slightly more costly in AVL trees but lookup faster. The asymptotic and worst-case behavior of the two data structures is identical though (the runtime (not number of rotations) is O(log n) for insertions in both cases, the O(1) you mentioned is the so-called amortized runtime).

    See this paragraph for a short comparison of the two data structures.