CODEWITHSUNDEEP
performancedata-structurestreeavl-treered-black-tree
Uğur
Uğur

Reputation: 47

Comparison of Avl Tree and Red Black Tree

I have an exam tomorrow and there are 3 questions those i can not understand on my notes.

1- #searches >> #insertions and #deletions=0 Which tree is that? (Avl or Red-Black Tree) (Answer is Avl)

2- #insertions>0 and #searches=#deletions=0 Which tree is that? (Avl or Red-Black Tree) (Answer is Red-Black)

3- #insertions=#deletions and #searches=0 Which tree is that? (Avl or Red-Black Tree) (Answer is Red-Black)

Can you explain them please? Thanks for help

Upvotes: 1

Views: 1264

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

AVL trees, compared to red/black trees, usually have smaller height because the AVL invariants give less room for imbalance. However, red/black trees, compared to AVL trees, have faster insertions and deletions (the fixup cost of maintaining the red/black invariants is lower than the fixup cost of maintaining the AVL invariants.)

For case (1), an AVL tree is probably better because the cost of the lookups will be lower and, if the number of lookups is truly much larger than the number of insertions, the AVL tree will have a comparative advantage.

For case (2), the red/black tree will probably be faster because it supports faster insertions.

For case (3), for the same reason as part (2), the red/black tree will probably be faster.

Hope this helps!

Upvotes: 4

Related Questions