Inheritance and AVL/BST Trees

Question

Is there any way to use the same insert function for both Bst and Avl tree? The problem is that Bst and Avl have different Node types, but I don't want to make the Bst Node a general case(with height and Node* parent inside, which makes no sense because there is no need of parent and height inside a Bst).

class Bst
{
public:
    struct Node
    {
        int value;
        Node* left;
        Node* right;
    };

    Node* insert(Node* node) {/* do stuff using Bst::Node */}

    // ...
};

class Avl : public Bst
{
public:
    struct Node : public Bst::Node
    {
        int height;
        Node* parent;
    };

    // now I want that Bst::insert use this Node
    // instead of the old one


    Node* insert(Node* node)
    {
        Node* inserted_node = Bst::insert(node);
        /* rotations stuff */
        return inserted_node;
    }
};

Roughly what I'm trying to do is make Bst::Node "virtual".

So, how can I solve the problem of implenting the Avl Tree without rewriting the entire insert function just because Node changed?

Answer 1

Actually I'm also working on this stuff and I think you're very clear to describe what you want.

At the first, it's may be little confuse about the given interface, insert() should not return the pointer of the Node, doesn't it. We may use the findNode() function, which return the pointer of the Node and exactly do this work only.

Back to the main question, may be you can use the template to set your Node type for every function in the BST. But the BST is not just a abstract interface, which also implement the BST operation, so it's not CRTP..

The pseudo code for now may be the following : // pre-define :

//parent ptr also alleviate the implementation of BST.

template<typename T>
class BST{
    ... omit..
    protected:
        template<typename node_type>
        class BST_Node{  
            public:
                T val;
                BST_Node *left, *right, *parent;  
                BST_Node():left{nullptr}, 
                           right{nullptr},
                           parent{nullptr}, val{}{};
        // empty {} default to value initialization.
        }
 ... omit ...
}


template<typename T>
class AVL_Node : public BST_Node{
    public:
        short height;
        AVL_Node(T val):BST_Node(val), height(0){};
}

template<typename T>
void insert(T val){
    AVL_Node<T> Node(val);
    BST<T>::insert_node<AVL_Node>(Node);
    AVL_Node<T>* ptr = BST<T>::find_node<AVL_Node>(val);
    ptr->height = BST<T>::get_height(ptr); 

    state = chk_balance(ptr);
    switch(state){
        case 0:  // tree very balance..
            break;
        case 1:
            LL_rotate(ptr);
            break;
        case 2:
            RR_rotate(ptr);
            break;
        ... omit
     }
}

@ help this post solve your question..

Answer 2

Maybe you want CRTP (in which case you haven't given enough info about your needs for even a rough example, but a simpler less powerful template approach may make more sense to you. Have a base class (under each of your tree types) that has no data members, and just defines static template functions for the common code. Since the functions are static, you need to pass in the relevant data (for insert that should be &root) but that should not be much trouble. (Rough and untested):

struct tree_base
{
   template <class Node>
   static Node* insert( Node** where, Node* what)
   {
      Node* here;
      while ( (here = *where) != 0 )
      {
         if ( *what < *here ) where = &(here->left);
         else if ( *here < *what ) where = &(here->right);
         else
         {
      Trying to insert something already there, what should be done
         }
      }
      *where = what;
      return what;  // Is that the desired return?
   }
};

Then each of your real tree classes would inherit from tree_base and would call tree_base::insert(&root, new_node) to do the common parts of insert

A CRTP version of that would allow root to be a member of the base class even though it points to the Node type of the derived class. Given root as a member of the base class, the insert function doesn't need to be static and doesn't need to take &root as input. And since a CRTP base class is already correctly templated to have access to the Node type, the base class insert method wouldn't need to be a template. All that would be a lot more things to learn (by looking at some real examples of CRTP) and probably overkill for the code sharing you want.