Comparison about balanced binary search trees

3
votes

I've read some Q&As about self-balancing binary trees, but I'm not quite familiar with all of them.

The first one of them I got to know is AVL, the second is Red-Black tree.

There are something I don't quite understand: according to some books and articles, AVL can perform searching a little bit faster than Red-Black tree, well, this is understandable.

  1. Then what's Red-Black tree's edge over AVL?

  2. In AVL, probably after each insertion, we have to check for balance, but in Red-Black tree we don't have to do something like that frequently, right?

PS: I search SO for something similar, but I didn't get satisfying answer. Hope some friends can give me a detailed comparison of self-balancing trees.

1
data-structurestreered-black-treeavl-tree

1 Answers

2
votes

An AVL tree has the following property: from each node, the difference in height of the left and the right subtree is at most 2.

In a red-black tree, on the other hand, the height of the left or right subtree of any node is at most twice the height of the other tree. That is, they differ at most by a factor of 2.

This shows intuitively that lookup is indeed faster in an AVL tree on average.

However, when inserting or deleting a node, we have to rebalance the AVL tree more often, to preserve the much stricter height invariant (on the other hand, rebalancing in a red-black tree is algorithmically much more complicated). This means that in practice, a red-black tree may perform much better than an AVL tree, in particular when it’s often changed.