AVL tree implemented in the style of TreeMap for better performance

[David McManamon]

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