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 ) ?
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With