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         
};

---

AvlNodeis a type. You are using it as if it was a pointer. I assume you want to insert a new value?

Quote:

---

Originally Posted by Daved

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?

So how does the AVLTree class you are implementing expect the user to insert a value?

Quote:

---

Originally Posted by Daved

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?

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.

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?

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.