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 ) ?

AVL tree criterion for rotations is stricter than Red black and hence insertions and removals are slower than red black tree. — AdityaKapreShrewsburyBoston, Aug 15 '21 at 23:06

score 24 · Accepted Answer · edited Jul 26 '17 at 00:19

24

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.

edited Jul 26 '17 at 00:19

Rishabh Maurya

1,448
3
22
40

answered Feb 17 '13 at 16:43

Justin

4,196
4
24
48

15

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 : http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types – Nikunj Banka Feb 17 '13 at 16:57
3

Since Java 7 merge-sort was replaced by TimSort http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6804124 – Ondrej Bozek Apr 01 '14 at 20:11

David McManamon · Answer 2 · 2017-11-01T22:52:12.137

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.

score 1 · Answer 3 · answered Feb 17 '13 at 19:12

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.

Why red-black tree based implementation for java TreeMap?

3 Answers3

Linked