wavl based alternative to red-black TreeMap

Raffaello Giulietti raffaello.giulietti at gmail.com
Sun Dec 1 17:49:53 UTC 2019

Not exactly the newest data structure. Wavl trees are with us since 2009 ;-)

HashMap could benefit from wavl trees as well. Afaik, it uses red-black 
trees in presence of collisions, right?


> Nice !
> there is a wikipedia article about WAVL tree [1].
> I did not know this new kind of balanced tree, worth the exploration i believe.
> and TreeMap code really needs some love anyway, unlike ArrayList and HashMap, this code has not be updated since a long time.
> Rémi
> [1] https://en.wikipedia.org/wiki/WAVL_tree
> ----- Mail original -----
>> De: "raffaello giulietti" <raffaello.giulietti at gmail.com>
>> À: "core-libs-dev" <core-libs-dev at openjdk.java.net>
>> Envoyé: Dimanche 1 Décembre 2019 18:00:19
>> Objet: wavl based alternative to red-black TreeMap
>> Hi core librarians,
>> did anybody already explore wavl trees as a drop-in replacement to the
>> red-black based TreeMap?
>> If yes, I'm curious about performance comparisons.
>> If not, I would be glad to invest some time on it as they seem to be
>> never worse than red-black trees and in many application (no deletions,
>> only insertions and searching) even better.
>> No promises about delivery...
>> Greetings
>> Raffaello

More information about the core-libs-dev mailing list