**For small data**:

**insert**: RB tree & avl tree has constant number of max rotation but RB tree will be faster because on average RB tree use less rotation.

**lookup**: AVL tree is faster, because AVL tree has less depth.

**delete**: RB tree has constant number of max rotation but AVL tree can have O(log N) times of rotation as worst. and on average RB tree also has less number of rotation thus RB tree is faster.

**for large data**:

**insert**: AVL tree is faster. because you need to lookup for a particular node before insertion. as you have more data the time difference on looking up the particular node grows proportional to O(log N). but AVL tree & RB tree still only need constant number of rotation at the worst case. Thus the bottle neck will become the time you lookup for that particular node.

**lookup**: AVL tree is faster. (same as in small data case)

**delete**: AVL tree is faster on average, but in worst case RB tree is faster. because you also need to lookup for a very deep node to swap before removal (similar to the reason of insertion). on average both trees has constant number of rotation. but RB tree has a constant upper bound for rotation.

3Asking to understand concept better. Both avl tree and Red Black tree have atmost two rotations per insertion. So, how can you say AVL trees are slow?

Thanks in advance! – user2626445 – 2014-09-01T12:53:17.303

@larsmans! Is the performance difference so much that a new concept is created? – Shashwat – 2014-10-30T16:40:49.693

@Shashwat I don't get what you mean. New concept? – Fred Foo – 2014-10-30T17:00:41.623

2@larsmans! I mean why do we have the concept of Red-Black tree so famous when we have AVL tree, though there are only slight differences in their insertion, deletion and update performances. Is there anything major which makes Red-Black tree different from AVL tree? – Shashwat – 2014-10-30T22:15:55.927

The algorithms to maintain them are different, so they get different names. AFAIK, they support the same set of operations with the same big-O time bounds. – Fred Foo – 2014-10-31T09:25:24.330