Why is avl tree faster for searching than red black tree?

Question

I have read it in a couple of places that avl tree search faster, but not able to understand. As I understand : max height of red-black tree = 2*log(N+1) height of AVL tree = 1.44*logo(N+1)

Is it because AVL is shorter?

Churning

Read a book on data structures. But if I remember (off the top of my head) correctly, an AVL tree approximates more closely to being perfectly balanced than does an RB tree, at the cost of an insert to an AVL being considerably more expensive than to a RB. – Fortnightly

Yeah because its shorter and therefore has fewer nodes from top to bottom. Maybe a picture would help: en.wikipedia.org/wiki/File:AVL_Tree_Rebalancing.svg – Cricket

Answer 1

Yes.

The number of steps required to find an item depends on the distance between the item and the root.

Since the AVL tree is packed tighter (i.e. it has a lower max height) it means more items are closer to the root than in the red-black case.

The extra tight packing also means the AVL tree requires more work when inserting elements. The best choice for any app depends on whether it is insert intensive or search intensive...

Thymic

A nice explanation. I can only add some numbers: maximum difference between node's depths in AVL tree is 1, in R-B tree one node can be twice deeper than the other node (depth being the distance between the node and the root). But insertions and deletions in R-B tree require 3 rotations at maximum, while AVL tree might require a number of rotations equal to the tree depth. (rotation is a fundamental operation in balanced trees, I won't describe it here) – Scalariform

Answer 2

AVL tree is better than red-black tree if the input key is almost ascending/descending because then we would have to do single rotation(left-left or right-right case) to add this element. Also, since the tree would be tightly balanced, the search would also be faster.

But for randomly selected input key, RBTree are better since they require less rotation for insertion in comparison to AVL.

Overall, it depends on the input sequence, which would decide how tilted our tree is, and the operation performed.For insert-intensive use Red-Black Tree and for search-intensive use AVL.

Greaten

Answer 3

AVL tree and RBTree do have respective advantages as well as disadvantages. You'll perceive that better if you've already learned how they work.

AVL is slightly faster than RBTree in insert operation because there would be at most one rotation involved in insertion, while there may be two for RBTree.

RBTree only require at most three rotations in deletion, but this is not guaranteed in AVL. So it can delete nodes faster than AVL.

However, above all, they both have strict logarithmic tree height.

Pick up any subtree, the property that makes AVL "balanced" guarantees that the difference of height between two child subtrees is at most one, which is to say, intuitively, the whole tree is rigidly balanced.

But when it comes to an RBTree, the rule becomes likely "looser", since property of RBTree can only guarantee the depth of a tree is not larger than twice as the logarithm of the total number of nodes.

Here're some facts that may be more precise:

An AVL tree's height is strictly less than: 1.44log(n+2)-0.328 (approximately)

A red-black tree's height is at most 2log(n+1)

See https://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures for detailed information.

Scrim