DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: AA Tree Implementation Variation and Concepts

#### Hybrid View

1. Registered User
Join Date
May 2007
Posts
843

## 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.

Thanks for your help.
Last edited by Peter_APIIT; 11-01-2008 at 03:33 AM.

2. Registered User
Join Date
May 2007
Posts
843
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:

#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 ?

Thanks for your help.

3. Is it giving you errors or it is just "out of balance"?

4. Registered User
Join Date
May 2007
Posts
843
It's logic error and out of balance.

5. Registered User
Join Date
May 2007
Posts
843
I hope someone can help.

6. Registered User
Join Date
May 2007
Posts
843
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

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

Thanks for your help.

7. Registered User
Join Date
Dec 2007
Posts
401
AA tree algorithms for skew, split, insert and delete:
http://en.wikipedia.org/wiki/AA_tree

8. Registered User
Join Date
May 2007
Posts
843
I know the skew and split algorithm but there are some errors there which i cannot solved it.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise
 Questions? Contact us. C++ Web Development Wireless Latest Tips Open Source