CODEWITHSUNDEEP
algorithmavl-treered-black-tree
Aleeee
Aleeee

Reputation: 2023

AVL tree rotation and red-black tree color flips

As we all know, the insertion and deletion all require O(log n). AVL tree require O(log n), because it need O(log n) to insert and O(log n) to rotation for balance.

RB tree require O(log n), because it need O(log n) to insert, In INTRODUCTION TO ALGORITHMS THIRD EDITION, the RB-INSERT-FIXUP need O(log n) for case 1(color flips), and at most 2 times to rotation. So it seems that AVL require 2O(log n), but RB tree require 2O(log n)+C.

Why we think RB tree is more faster than AVL in insertion? Just because rotation need more time than color flips? A rotation and color flips both require O(1), why rotation is more time-consuming than color flips? Thanks!:)

Upvotes: 0

Views: 946

Answers (1)

max
max

Reputation: 4348

If I understand your question correctly, yes it is true that RB-Trees and AVL-Trees both offer lookup, insertion, deletion in O(logn) time.

AVL-Trees are more rigidly balanced than RB-Trees. To attain this, a lot of rotations are required, which are time consuming. RB-Trees are slightly unbalanced, as they have weaker rules for balancing, thus they need lesser operations for insertion and deletion. As a consequence, lookup in AVL-Trees is faster than RB-Trees, but insertion and deletion is faster in RB-Trees.

EDIT

Please read this blog post. The point is that RB trees balance faster than AVL trees after insertion. Yes, a rotation does take O(1) time in AVL trees, at most two rotations need to be done, but the point of rotation still needs to be found, and the time for rotation becomes O(logn). Whereas in RB trees, rebalancing after insertion runs in amortized constant time. So, O(1) amortized time for color flips, not O(logn).

Upvotes: 2

Related Questions