Thread: AVL Tree Implementation

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    34

    AVL Tree Implementation

    I am trying to implement an AVL tree and have come up with the following code.
    However, when I try the following, I get an error saying that AvlNode is undeclared.

    Code:
    int main()
    {
     AVL_Tree eavltree;
     AvlNode->element = 86;
    Can someone help me understand what I am doing wrong? Thanks.

    Code:
    class AVL_Tree
    {
     public:
            struct AvlNode
            {
              int element;
              AvlNode *left;
              AvlNode *right;
              int height;
              int frequency;
        
              AvlNode( const int & theElement, AvlNode *lt, AvlNode *rt, int h = 0 )
                              : element( theElement ), left( lt ), right( rt ), height( h ) { }
            };
      
          int insert(const int & x, AvlNode * & t ); 
          int remove(int item); 
          int find(int &item, int &freq); 
          void display(); 
          int height(AvlNode *t); 
          int intPathLength(); 
          int Size(); 
          int avgeNodesVisited();   
         
          void doubleWithLeftChild(AvlNode* &k3);
          void doubleWithRightChild(AvlNode* &k3);
          void rotateWithLeftChild(AvlNode* &k2);
          void rotateWithRightChild( AvlNode * & k2 );
     
     private:
          AvlNode *root; //pointer to root of tree
          int tree_height; //current height of tree
          int internal_path_length; //Current internal path length of tree
          int size; //Current number of nodes in tree
          int nodes_visited; //Current number of nodes visited by all finds so far
          int search_count; // Number of completed searches performed so far          
    };

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    AvlNodeis a type. You are using it as if it was a pointer. I assume you want to insert a new value?

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    34
    Quote Originally Posted by Daved View Post
    AvlNodeis a type. You are using it as if it was a pointer. I assume you want to insert a new value?
    Yes, that's right. And perhaps I am doing this wrong. Is it possible to declare the AvlNode struct as if it were another class and then allow the AVL_Tree class access to the AvlNode?
    Last edited by Bnchs400; 10-24-2007 at 05:17 PM.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    So how does the AVLTree class you are implementing expect the user to insert a value?

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    34
    Quote Originally Posted by Daved View Post
    So how does the AVLTree class you are implementing expect the user to insert a value?
    Yes, I see the problem now. Would this work if I just put the things in the struct in the public section of the AVL_Tree class and not use the struct so that I can create nodes from the class?

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I would imagine that the struct should be private and that the public interface shouldn't mention anything about nodes. To insert an element, just take an int and handle the node stuff internally.

  7. #7
    Registered User
    Join Date
    Mar 2006
    Posts
    34
    I have modified my code to declare the struct as a class instead.

    so now I have:

    Code:
    class AvlNode
    {
      int element;
      AvlNode *left;
      AvlNode *right;
      int height;
      int frequency;
       
      AvlNode( const int & theElement, AvlNode *lt, AvlNode *rt, int h = 0 )
                              : element( theElement ), left( lt ), right( rt ), height( h ) { }
           
      friend class AVL_Tree;
    };
    ...
    What is really confusing me is what this does. As I see it, the AvlNode class creates a node with those data members. Then, the AVL_Tree class would do things with that Node. Is this what is/should be happening?

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Whether AvlNode is a struct or class is pretty irrelevant. Making it a private struct (or class) inside AVL_Tree means that users won't have access to it, which I would imagine is what you want. If you want user's to have access to it, then say so.

    How the node works is an implementation detail of the tree class. Just expose publicly the methods to insert and retrieve the values.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Weight Balanced Tree - Implementation
    By paulovitorbal in forum C Programming
    Replies: 1
    Last Post: 10-31-2007, 02:28 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM