Clever Geek Handbook

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

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

I know that each tree needs at most 2 rotations for each insert. Then how quickly does it integrate into red-black trees?

And how does insertion require O (log n) rotations in the avl tree, and O (1) in red-black?

+3


source to share


2 answers


Well, I don't know what your level is, exactly, but in simpler terms, red-black trees are less balanced than AVL trees. For red-black trees, the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf, whereas for AVL trees, there is no more than one level difference between two adjacent subtrees. This makes insertions and deletions a little more expensive in AVL trees, but searches are faster. The asymptotic and worst behavior of the two data structures is identical (the execution time (not the number of rotations) is O (log n) for inserts in both cases, the mentioned O (1) is the so called amortized execution time ).



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

+4


source


Insertion and deletion is not faster in red-black trees. This is a common ASSUMPTION, and the assumption is based on the fact that red-black trees, on average, perform slightly less revolutions per insert than AVL (0.6 versus 7).
You can test yourself in Java by comparing TreeMap (red-black) to this implementation of TreeMapAVL, and you can get exact numbers instead of the usual but incorrect assumptions. https://github.com/dmcmanam/bbst-showdown



+1


source






More articles:


All Articles