Why red-black tree based implementation for java TreeMap?

Question

The third paragraph of wikipedia's article on AVL trees says: "Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications."

So, shouldn't TreeMap be implemented using AVL trees instead of red-black trees(as there will be more look up intensive applictions for a hashing based data structure ) ?

Hedveh

AVL tree criterion for rotations is stricter than Red black and hence insertions and removals are slower than red black tree. – Attalie

Answer 1

Red-Black trees are more general purpose. They do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove. Java's general policy is to provide the best general purpose data structures. It's also the same reason Java's default Array.sort(Object[] a) implementation is stable,adaptive ,iterative merge sort instead of quicksort.

Kaffiyeh

Java uses quicksort for primitive objects as it is faster than merge sort in the average case . It uses merge sort for sorting objects as merge sort is a stable sorting algorithm. SEE : #3707690 – Hedveh

Since Java 7 merge-sort was replaced by TimSort bugs.java.com/bugdatabase/view_bug.do?bug_id=6804124 – Ulane

Answer 2

Historically, number of rotations was thought to be very important so red-black trees were chosen over AVL because red-black perform slightly fewer rotations with random inserts - .6 vs .7 average rotations per insert.

In hindsight, AVL trees probably would have been a better choice. You can see a performance comparison of AVL & red-black trees in Java here: https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/

With random insertions the performance is similar. With sequential data AVL trees perform much better - 30% or more.

Lorinalorinda

Answer 3

The Wikipedia article is wrong (or at least, there is no supporting citation to back up the claim). It is true that the worst-case height of an AVL tree (1.44 lg n) is better than the worst-case height of a red-black BST (2 lg n), but this is worst case and may not have much to do with real-world performance.

Kevel