AA-Tree Java Implementation

The next data structure presented is called AA tree.
Briefly this is a self balancing binary tree.Its performance is comparable with the performance of red-black trees though it is slightly slower during tests.


The wikipedia article explains this type of trees well enough:
AA-Tree

AA Tree demo


The Java implementation I offer follows the algorithms explained in the article above so I didn't prepare any additional documentation. The standard search/insert/delete functionality is provided. The tests provided in the package compare this implementation with Java's TreeSet which keeps elements in red-black tree. The performance tests show that both implementations have similar running times:
- searching is similar(barely noticeable advantage for aa-tree)
- insert is slightly faster for red-black trees
- delete is faster for red-black trees(my tests show about two times advantage for TreeSet)

So as you can see Red-Black Tree is clearly the winner here.
This is not surprising - after all this is one of the most popular trees in many libraries in different languages.

So what is the advantage of AA tree over Red-Black tree?
Besides the slight advantage in searching maybe the biggest advantage is that AA trees are simple to implement.The implementation I offer is about 170 lines which is less than any red-black tree implementation I've seen so far.

Java source + tests