Implementation of a data structure (Binary search tree) in c++

user_17317895 0
Viewed 201

I want to ask what's the best way to implement Binary search tree data structure in c++ given the following:

I already implemented BinaryNode class in c++, which have the following fields:

//|-------------------- Protected fields --------------------|
protected:
    U value;
    T key;
    BinaryNode* left;
    BinaryNode* right;
    BinaryNode* parent;

and supports the following methods:

BinaryNode(const T _key, const U& _value);
virtual void insert(const T element,const U& value);
virtual int height();        //Returns the height of the subtree where the activating node is the root 
virtual int nodeSize();      //Counting the nodes in the subtree where the activating node is the root
virtual int depth(const T& _key) //Returns the depth of the node with the argument key
virtual void printInOrder();
virtual void printPreOrder();
virtual void printPostOrder();
void printNode(int space); //Prints the subtree where the activating node is the root in a "graphical" way.
~BinaryNode();

And I implemented the BinaryTree class, which have only one field:

protected:
    BinaryNode<T,U>* root;

And supports all of the methods that the BinaryNode supports, with the simple implementation of just calling the right methode of the root. For example the implementation of height() would be

int height() const {
    return root->height();
}

Now, I want to implement BinarySearchNode and BinarySearchTree classes, but since every method of the BinaryTree except for insertwould be the same for BinarySearchTree and BinaryTree, are relevant for the BinarySearchNode class, I would like to use this existing code. So I thought about inheritence, and since BinarySearchNode should have all of the methods of BinaryNode (and some more methods), I thought that correct design would be to implement BinarySearchNode as a derived class of BinaryNode, and BinarySearchTree as a derived class of BinaryTree.

But, during the implementation of the additional methods of BinarySearchNode I noticed that I have to downcast a lot. For example, here is the implementation of insert method:

virtual void insert(const T key, const U& data){
    if(key < this->key){
        if(!(this->left)){
          this->left = new BinarySearchNode(key, data);
          ((BinarySearchNode*) this->left)->parent = this;
        }
        else
            this->left->insert(key,data);
    }
    if(this->key < key){
        if(!(this->right)){
            this->right = new BinarySearchNode(key,data);
            ((BinarySearchNode*)this->right)->parent = this;
        }
        else
            this->right->insert(key,data);
    }
    if(this->key == key)
        throw "Error: Key already exists in the tree.";

Note that since I used inheritence, the pointer fields of the BinarySearchNode are of type BinaryNode, and so this->right is a BinaryNode and I cannot access its protected field parent unless I downcast it to a BinarySearchNode.

So I guess this design is not very smart.

How would you implement BinarySearchNode and BinarySearchTree instead? Thanks in advance.

And I implemented the BinaryTree class, which have only one field:

protected:
    BinaryNode<T,U>* root;

And supports all of the methods that the BinaryNode supports, with the simple implementation of just calling the right methode of the root. For example the implementation of height() would be

int height() const {
    return root->height();
}

Now, I want to implement BinarySearchNode and BinarySearchTree classes, but since every method of the BinaryTree except for insertwould be the same for BinarySearchTree and BinaryTree, are relevant for the BinarySearchNode class, I would like to use this existing code. So I thought about inheritence, and since BinarySearchNode should have all of the methods of BinaryNode (and some more methods), I thought that correct design would be to implement BinarySearchNode as a derived class of BinaryNode, and BinarySearchTree as a derived class of BinaryTree.

But, during the implementation of the additional methods of BinarySearchNode I noticed that I have to downcast a lot. For example, here is the implementation of insert method:

virtual void insert(const T key, const U& data){
    if(key < this->key){
        if(!(this->left)){
          this->left = new BinarySearchNode(key, data);
          ((BinarySearchNode*) this->left)->parent = this;
        }
        else
            this->left->insert(key,data);
    }
    if(this->key < key){
        if(!(this->right)){
            this->right = new BinarySearchNode(key,data);
            ((BinarySearchNode*)this->right)->parent = this;
        }
        else
            this->right->insert(key,data);
    }
    if(this->key == key)
        throw "Error: Key already exists in the tree.";

Note that since I used inheritence, the pointer fields of the BinarySearchNode are of type BinaryNode, and so this->right is a BinaryNode and I cannot access its protected field parent unless I downcast it to a BinarySearchNode.

So I guess this design is not very smart.

How would you implement BinarySearchNode and BinarySearchTree instead? Thanks in advance.

c++
1 Answers

Normal public inheritance of nodes is not a good idea. I strongly advise against using it.

An AVLNode has no job of being inside the regular BinaryTree. However, if you use inheritance, then Liskov Substitution Principle dictates that you should be able to use an AVLNode everywhere a BinaryNode may be used. This is not what you want.

You can use a variation of inheritance known as the Curiously Recurring Template Pattern. Example code (not tested):

   template <class DerivedNode>
   class Node
   {
      private:
        DerivedNode* left;
        DerivedNode* right;
      // .. whatever
   };

   template <class DerivedNode>
   class ParentedNode : public Node<DerivedNode>
   {
      private:
        DerivedNode* parent;
      // ... whatever
   };

   class SearchNode : public ParentedNode<SearchNode>
   {
      // ...
   };

   class AVLNode : public ParentedNode<AVLNode>
   {
      // ...
   };

   AVLSearchNode a;

You can then templatize the tree itself:

   template <class Node> 
   class Tree 
   { 
      // ... 
   };

   class SearchTree : public Tree<SearchNode> 
   {
      // ...
   };

   class AVLTree : public Tree<AVLNode> 
   {
      // ...
   };

Things that others have said about placement of methods in the node class vs in the tree class still apply.

user_7758060
Related