top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Which is better AVL tree or Red Black tree??

+6 votes
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