The balanced tree

The AA tree is the 'cool' alternative to the red-black balanced tree. Balanced trees are a great way to guarantee the minimal run-time impact when searching for a particular node in your binary tree. The typical run-time complexity of a binary tree is O log(n) but if the tree is unbalanced, a worst case scenario could mean that your tree has linear run-time or O (n). A balanced tree means O log (n) insert, search, and delete. Technically, because an average is the most likely scenario, the typical run-time is O log(n)/2, but complexity measurements usually ignore constant multiples.

This AA tree is very fast, and lightweight. It is also more cache friendly because of the fact that it operates almost entirely in one function when adding nodes to the tree and when removing nodes. In addition, it is quite small. I have included a copy-and-paste solution below for this slick algorithm. Have fun with it.

template <typename type>
struct AABinaryNode
{
type Data;
AABinaryNode* Left;
AABinaryNode* Right;

int Level;

AABinaryNode () : Left (NULL), Right (NULL), Level (0)  {}
AABinaryNode (const type& e) : Data (e), Left (NULL), Right (NULL), Level (0)  {}
AABinaryNode (const type& e, AABinaryNode* l, AABinaryNode* r) : Data (e), Left (l), Right (r), Level (0)  {}
~AABinaryNode () {}

};
template <typename type>
AABinaryNode <type>*
RotateWithLeftChild (AABinaryNode <type>* k2)
{
AABinaryNode <type>* k1 = k2->Left;
k2->Left = k1->Right;
k1->Right = k2;
return k1;
}
template <typename type>
AABinaryNode <type>*
RotateWithRightChild (AABinaryNode <type>* k1)
{
AABinaryNode <type>* k2 = k1->Right;
k1->Right = k2->Left;
k2->Left = k1;
return k2;
}

//*******************************************************
//*******************************************************

template <typename type>
class AATree
{
public:
AATree ();
~AATree () {FreeTree (Root); delete NullNode;}

bool  Insert  (const type& x) {return Insert (x, Root);}
bool  Remove  (const type& x) {return Remove (x, Root);}

const type& FindMin  () const;
const type& FindMax  () const;

const type& Find  (const type& t);
bool  WasFound () const {return CurrentNode != NullNode;}

void  Clear  () {FreeTree (Root); Root = NullNode;}
void  IsEmpty  () const {return Root == NullNode;}

void  Display  (bool WithLevels = false) const;
private:
AABinaryNode <type>* Root;
AABinaryNode <type>* NullNode;
AABinaryNode <type>* CurrentNode;// result of the last search

void  Skew (AABinaryNode <type>* & t);
void  Split (AABinaryNode <type>* & t);

void  FreeTree (AABinaryNode <type>* t);
bool  Insert (const type& x, AABinaryNode <type>* & t);
bool  Remove (const type& x, AABinaryNode <type>* & t);

const AATree& operator = (const AATree& );// disable the operator
};

//*******************************************************

template <typename type>
AATree <type> :: AATree ()
{
NullNode = new AABinaryNode <type> ();
NullNode->Left = NullNode->Right = NullNode;
NullNode->Level = 0;

Root = NullNode;
}

//*******************************************************

template <typename type>
const type& AATree <type> :: FindMin  () const
{
AABinaryNode <type>* Walker = Root;

while (Walker->Left != NullNode)
{
 Walker = Walker->Left;
}
return Walker->Data;
}

//*******************************************************

template <typename type>
const type& AATree <type> :: FindMax  () const
{
AABinaryNode <type>* Walker = Root;

while (Walker->Right != NullNode)
{
 Walker = Walker->Right;
}
return Walker->Data;
}

//*******************************************************

template <typename type>
const type& AATree <type> :: Find  (const type& x)
{
NullNode->Data = x;
CurrentNode = Root;

while (CurrentNode->Data != x)
{
 if (x < CurrentNode->Data)
 {
  CurrentNode = CurrentNode->Left;
 }
 else
 {
  CurrentNode = CurrentNode->Right;
 }
}
return CurrentNode;
}

//*******************************************************

template <typename type>
void
AATree <type> :: Display  (bool WithLevels) const
{
const int MaxLevels = 24;
AABinaryNode <type>* Stack [MaxLevels];
int StackTop = 0;

Stack[StackTop++] = Root;
while (StackTop > 0)
{
 --StackTop;// reduce the stack
 AABinaryNode <type>* Node = Stack[StackTop];// pop
 if (Node->Right != NullNode)
 {
  Stack[StackTop++] = Node->Right;
 }
 if (Node->Left != NullNode)
 {
  Stack[StackTop++] = Node->Left;
 }
 if (WithLevels)
 {
  cout << Node->Data << " - " << Node->Level << ", ";
 }
 else
 {
  cout << Node->Data << " ";
 }
}
cout << endl;
}

//*******************************************************

template <typename type>
void
AATree <type> :: Skew (AABinaryNode <type>* & t)
{
if (t == NullNode)
 return;

if (t->Left->Level == t->Level)
{
 t = RotateWithLeftChild (t);
}
}

//*******************************************************

template <typename type>
void
AATree <type> :: Split (AABinaryNode <type>* & t)
{
if (t == NullNode)
 return;

if (t->Right->Right->Level == t->Level)
{
 t = RotateWithRightChild (t);
 t->Level++;
}
}

//*******************************************************

template <typename type>
void
AATree <type> :: FreeTree (AABinaryNode <type>* t)
{
if (t != NullNode)
{
 FreeTree (t->Left);
 FreeTree (t->Right);
 delete t;
}
}

//*******************************************************

// insert item x into aatree rooted at t
// if x is duplicate, return false

template <typename type>
bool
AATree <type> :: Insert (const type& x, AABinaryNode <type>* & t)
{
if (t == NullNode)
{
 t = new AABinaryNode <type> (x, NullNode, NullNode);
 t->Level = 1;

 return true;
}
else if (x < t->Data)
{
 Insert (x, t->Left);
}
else if (x > t->Data)
{
 Insert (x, t->Right);
}
else
{
 return false;
}

Skew (t);
Split (t);
return true;
}

//*******************************************************

template <typename type>
bool
AATree <type> :: Remove (const type& x, AABinaryNode <type>* & t)
{
bool ItemFound = false;
AABinaryNode <type>* DeletePtr;
AABinaryNode <type>* LastPtr;

if (t != NullNode)
{
 LastPtr = t;
 if (x < t->Item)
 {
  Remove (x, t->Left);
 }
 else
 {
  DeletePtr = t;
  Remove (x, t->Right);
 }
 // remove if at bottom of tree
 if (t = LastPtr)
 {
  if (DeletePtr != NullNode && x == DeletePtr->Item)
  {
   DeletePtr->Item = t->Item;
   DeletePtr = NullNode;
   t = t->Right;
   delete LastPtr;
   ItemFound = true;
  }
  else
   ItemFound = false;
 }
 else if ((t->Left->Level < t->Level - 1) ||
    (t->Right->Level < t->Level - 1 ))
 {
  --t->Level;
  if (t->Right->Level > t->Level)
  {
   t->Right->Level = t->Level;
   Skew (t);
   Skew (t->Right);
   Skew (t->Right->Right);
   Split (t);
   Split (t->Right);
  }
 }
}
return ItemFound;
}

//*******************************************************
//*******************************************************