top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Which is better AVL tree or Red Black tree??

+6 votes
583 views
Which is better AVL tree or Red Black tree??
posted Oct 1, 2013 by Vikas Upadhyay

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+2 votes

RB-Trees are, as well as AVL trees, self-balancing. Both of them provide O(log n) lookup and insertion performance.

The difference is that RB-Trees guarantee O(1) rotations per insert operation. That is what actually costs performance in real implementations. Simplified, RB-Trees gain this advantage from conceptually being 2-3 trees without carrying around the overhead of dynamic node structures. Physically RB-Trees are implemented as binary trees, the red/black-flags simulate 2-3 behavior.

As far as my own understanding goes, AVL trees and RB trees are not very far off in terms of performance. An RB tree is simply a variant of a B-tree and balancing is implemented differently than an AVL tree.

answer Oct 1, 2013 by anonymous
+2 votes

The height of an AVL tree is at most ~1.44log(N), lower than the maximum height of a red-black tree, ~2log(N). However, upon insertion, AVL tree may need O(log(N)) operations to re-balance the tree, but red-black tree requires O(1). This means AVL tree is probably faster on searching but slower on insertion. In addition, red-black tree is easier to be implemented as a persistent data structure.

answer Oct 1, 2013 by Salil Agrawal
Similar Questions
...