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
