# AA Tree Implementation Variation and Concepts

• 11-01-2008, 03:30 AM
Peter_APIIT
AA Tree Implementation Variation and Concepts
Hello to all expect pogrammer, i wonder there are how many methods of AA Tree implmentation.

AFAIK, some using link[2], [0] = left and [1] = right and leftNode or rightNode.

Which one is easier and better ?

Some balanced tree contain level in its node and some are not. Please clarify on this.

I did a huge amount of research but not really understand it.

I know that AA Tree is a 2-3 tree which means

If a node contains 1 data, then got two children.
If a node contains 2 data, then got three children.

Besides that, AA Tree also doesn't have red node at left child. How this can coded in programming ? What this means ?

Skew = right notation
split = left rotation and increase root level

Every leaf node has level 1.

I hope you all can help me out.

• 11-21-2008, 01:48 AM
Peter_APIIT
I have tried to code the AA Tree but encounter some problem.

The tree is not balanced as it should.

I couldn't know what problem even though i try to debug.

Below is my code:

Quote:

#ifndef TreeNode
#define TreeNode

#ifdef WIN32
// Windows Function

template <typename T>
class treeNode
{
public:

T key;
T value;
int level;

treeNode<T> *leftNode;
treeNode<T> *rightNode;

treeNode();
treeNode(const T& aKey);
treeNode(const T& aKey, const T& aValue);

~treeNode();

private:
treeNode(const treeNode&);
treeNode& operator=(const treeNode&);

};

// ================================================
template <typename T>
treeNode<T>::treeNode() : key(T()), value(T()),
leftNode(0), rightNode(0),
level(1)
{
}
// ================================================
template <typename T>
treeNode<T>::treeNode(const T& aKey) : key(aKey),
value(T()),
leftNode(0), rightNode(0),
level(1)
{
}
// ================================================
template <typename T>
treeNode<T>::treeNode(const T& aKey, const T& aValue)
: key(aKey), value(aValue),
leftNode(0), rightNode(0),
level(1)
{
}
// ================================================
template <typename T>
treeNode<T>::~treeNode()
{
}
// ================================================

#else
// POSIX Function

#endif

#endif

#ifndef AATREE
#define AATREE

#ifdef WIN32
// Window function

template <typename T>
class AATree
{
private:
treeNode<T>* root;

AATree(const AATree&);
AATree& operator=(const AATree&);

public:
AATree();
~AATree();

void skew(treeNode<T>*);
void split(treeNode<T>*);

void Insert(const T&, const T&);
void RecursiveInsert(treeNode<T>*, treeNode<T>* , const T&);
void Remove(const T&);

bool search(const T&)const;
bool RecursiveSearch(treeNode<T>*, const T&)const;

void destroy()const;
void PostOrderDestroy(treeNode<T>*)const;

// Left->Right->Root
void PostOrder()const;
void RecursivePostOrder(treeNode<T>*)const;

void display(treeNode<T>*)const;
};

// ================================================
template <typename T>
AATree<T>::AATree() : root(0)
{
}
// ================================================
template <typename T>
AATree<T>::~AATree()
{
if (root != 0)
{
destroy();
}
}
// ================================================
template <typename T>
void AATree<T>::skew(treeNode<T>* aTreeNode)
{
if (aTreeNode != 0)
{
treeNode<T>* tempNode = aTreeNode;
if (aTreeNode->leftNode != 0)
{
if (aTreeNode->level == aTreeNode->leftNode->level)
{
treeNode<T>* temp = aTreeNode->leftNode;

aTreeNode->leftNode = temp->rightNode;
temp->rightNode = aTreeNode;
aTreeNode = temp;

if (tempNode == this->root)
{
this->root = aTreeNode;
}
}
}
}
// aTreeNode->rightNode = skew(aTreeNode->rightNode);
}
// ================================================
template <typename T>
void AATree<T>::split(treeNode<T>* aTreeNode)
{
if (aTreeNode != 0)
{
if (aTreeNode->rightNode != 0
&& aTreeNode->rightNode->rightNode != 0)
{
treeNode<T>* tempNode = aTreeNode;
if ((aTreeNode->level
== aTreeNode->rightNode->level)
&& (aTreeNode->rightNode->level
== aTreeNode->rightNode->rightNode->level))
{
treeNode<T>* tempParent = aTreeNode->rightNode;
aTreeNode->rightNode = tempParent->leftNode;
tempParent->leftNode = aTreeNode;
aTreeNode = tempParent;

++aTreeNode->level;
if (tempNode == this->root)
{
this->root = aTreeNode;
}
}
}
}
}
// ================================================
template <typename T>
void AATree<T>::Insert(const T& aKey, const T& aValue)
{
treeNode<T>* newNode = new treeNode<T>(aKey, aValue);

if (this->root == 0)
{
this->root = newNode;
}
else
{
bool notFound = true;

notFound = search(aKey);

if (!notFound)
{
treeNode<T>* iteratorNode = this->root;
if (aKey < iteratorNode->key)
{
if (iteratorNode->leftNode != 0)
{
RecursiveInsert(iteratorNode->leftNode,
newNode, aKey);
}
else
{
iteratorNode->leftNode = newNode;
}
}
else
{
if (iteratorNode->rightNode != 0)
{
RecursiveInsert(iteratorNode->rightNode,
newNode, aKey);
}
else
{
iteratorNode->rightNode = newNode;
}
}

skew(iteratorNode);
split(iteratorNode);
}
}
}
// ================================================
template <typename T>
void AATree<T>::RecursiveInsert(treeNode<T>* iteratorNode,
treeNode<T>* newNode,
const T& aKey)
{
if (iteratorNode != 0)
{
if (aKey < iteratorNode->key)
{
if (iteratorNode->leftNode != 0)
{
RecursiveInsert(iteratorNode->leftNode, newNode, aKey);
/* skew(iteratorNode);
split(iteratorNode);*/
}
else
{
iteratorNode->leftNode = newNode;
/* skew(iteratorNode);
split(iteratorNode);*/
}
}
else
{
if (iteratorNode->rightNode != 0)
{
RecursiveInsert(iteratorNode->rightNode, newNode, aKey);
}
else
{
iteratorNode->rightNode = newNode;
}
}
}
}
// ================================================
template <typename T>
void AATree<T>::Remove(const T& key)
{
}
// ================================================
template <typename T>
bool AATree<T>::search(const T& aKey)const
{
bool found = false;
if (this->root != 0)
{
found = RecursiveSearch(this->root, aKey);
}

return found;
}
// ================================================
template <typename T>
bool AATree<T>::RecursiveSearch(treeNode<T>* aTreeNode,
const T& aKey)const
{
bool found = false;
if (aTreeNode != 0 || !found)
{
if (aKey < aTreeNode->key)
{
if (aTreeNode->leftNode != 0)
{
RecursiveSearch(aTreeNode->leftNode, aKey);
}
}
else
{
if (aTreeNode->rightNode != 0)
{
RecursiveSearch(aTreeNode->rightNode, aKey);
}
}
}

return found;
}
// ================================================
template <typename T>
void AATree<T>::destroy() const
{
PostOrderDestroy(this->root);
}
// ================================================
template <typename T>
void AATree<T>::PostOrderDestroy(treeNode<T> *aTreeNode) const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
PostOrderDestroy(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
PostOrderDestroy(aTreeNode->rightNode);
}

delete aTreeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
aTreeNode = 0;
}
}
// ================================================
template <typename T>
void AATree<T>::PostOrder() const
{
if (root != 0)
{
cout << "Post Order Display \n";
RecursivePostOrder(this->root);
}
}
// ================================================
template <typename T>
void AATree<T>::RecursivePostOrder(treeNode<T> *aTreeNode) const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
RecursivePostOrder(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
RecursivePostOrder(aTreeNode->rightNode);
}

display(aTreeNode);
}
}
// ================================================
template <typename T>
void AATree<T>::display(treeNode<T>* aTreeNode) const
{
cout << "Key is " << aTreeNode->key << "\n";
cout << "Value is " << aTreeNode->value << "\n";
}

// ================================================

// ================================================

// ================================================

#else
// POSIX function

#endif

#endif

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#include "TreeNode.h"
#include "AATree.h"

using namespace std;

================================================
int main()
{
AATree<int> aTree;

aTree.Insert(10, 10);
aTree.Insert(1, 1);
aTree.Insert(2, 2);
aTree.Insert(4, 4);
aTree.Insert(3, 3);
aTree.Insert(6, 6);

aTree.PostOrder();

// asd.skew(a);

return 0;
}

Any hint how to balance the tree as it suppose to be ?

• 11-21-2008, 09:11 AM
Hack
Is it giving you errors or it is just "out of balance"?
• 11-24-2008, 11:43 PM
Peter_APIIT
It's logic error and out of balance.
• 11-27-2008, 05:29 AM
Peter_APIIT
I hope someone can help.
• 12-07-2008, 05:07 AM
Peter_APIIT
Yes, same level of left child and its parent is not allowed.

My problem is the tree is unbalance.

For instance, the insert sequence is 10, 1, 2, 4, 3, 6

Quote:

10 1
/ -> \
1 10

1 1
\ \
10 -> 2
/ \
2 10

When split was performed, 2 was not become the root and 1 is directly point to 10 and 2 is also point to 10.

How to make them like this

2
/ \
1 10