AVL tree implemented in the style of TreeMap for better performance

[Martin Buchholz]

Another thing to keep in mind is that someday Java might have value types,
which will make "inline objects" possible, which will make us reconsider
all the data structure implementations.

On Wed, Oct 18, 2017 at 3:35 PM, David McManamon <dmcmanam at gmail.com> wrote:

> If the BBST performance numbers from Ben Pfaff's c language research in
> 2004
> https://benpfaff.org/papers/libavl.pdf
> are correct then it seems the red-black tree implementations that are so
> popular in the JDK might be worth another look.  However, when I surveyed
> the AVL implementations in the Java world I didn't find the variety I was
> looking for - specifically an implementation similar to that of the
> red-black TreeMap (parent pointers, no recursion), so I wrote insert &
> delete in TreeMapAVL here:
>
> https://github.com/dmcmanam/bbst-showdown
>
> Although an old topic, it may be worth another look in Java since AVL trees
> do much better in some circumstances.
>
> Next week I'll write a WAVL implementation and expand the performance
> testing comparison which so far looks like this:
>
> Results for inserting 262143 random integers (height 18 for a complete BST)
> -
>
>   Mean insertion time: 171ms and 169ms, runs to converge:2. AVL tree of
> size: 262126, height: 21, rotations 183194
>
>   Mean insertion time: 165ms and 169ms, runs to converge:2. Red-black tree
> of size: 262126, height: 22, rotations 152622
>
>   Mean insertion time: 170ms and 167ms, runs to converge:1. BST          of
> size: 262126, height: 46, rotations 0
>
>   Time to copy a red-black tree (sorted insertion via recursion): 44ms.
> Red-black tree of size: 262126, height: 18, rotations 0
>
> Results for inserting integer clusters in sequences of 12 and total size:
> 262143 -
>
>   Mean insertion time: 63ms and 62ms, runs to converge:3. AVL tree of size:
> 262125, height: 21, rotations 325176
>
>   Mean insertion time: 70ms and 72ms, runs to converge:2. Red-black tree of
> size: 262125, height: 24, rotations 320990
>
> --David
>