AA Tree Implementation Variation and Concepts


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 8 of 8

Thread: AA Tree Implementation Variation and Concepts

  1. #1
    Join Date
    May 2007
    Posts
    843

    Thumbs up 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 04:33 AM.

  2. #2
    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. #3
    Join Date
    Apr 2007
    Location
    Sterling Heights, Michigan
    Posts
    8,666
    Is it giving you errors or it is just "out of balance"?
    I don't answer coding questions via PM or Email. Please post a thread in the appropriate forum section.
    Please use [Code]your code goes in here[/Code] tags when posting code.
    Before posting your question, did you look here?
    Got a question on Linux? Visit our Linux sister site.
    Modifications Required For VB6 Apps To Work On Vista

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

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

  6. #6
    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. #7
    Join Date
    Dec 2007
    Posts
    401
    AA tree algorithms for skew, split, insert and delete:
    http://en.wikipedia.org/wiki/AA_tree

  8. #8
    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
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center