An AA tree in computer science is a red-black tree with one additional rule. Unlike red-black trees, RED nodes on an AA tree can only be added as a right subchild. In other words, no RED node can be a left subchild. This results in the simulation of a 2-3 tree instead of a 2-3-4 tree, which greatly simplifies the maintenance operations.
The following code shows how to implement a AA tree in Java:
// AATree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS******...