CODEWITHSUNDEEP
c++tree
user3136756
user3136756

Reputation: 11

Working with templates and error in C++

I am trying to implement a red black tree with the use of templates. For example, when inserting an item to the tree, the key and the item should both be generic types. Till now, I implemented a header file which consists of a struct and functions to be implemented. However, I don't know if I'm using templates the right way. Also, when I tried to implement the 'Insert' function, the IDE gives the error: prototype for ‘void RedBlackTree::InsertKey(Item*&, Key*&)’ does not match any in class ‘RedBlackTree’ RedBlackTree.h

This is my header file:

#ifndef REDBLACKTREE_H_
#define REDBLACKTREE_H_

template <class Item, class Key>
class RedBlackTree
{
    typedef enum
    {
        BLACK,
        RED
    }ColourNode;

    typedef struct RBT
    {
        struct RBT *left;
        struct RBT *right;
        struct RBT *parent;
        struct RBT *root;
        ColourNode colour;
        Item item;
        Key key;
    }RBTNode;

    public:
        ~RedBlackTree(); // destructor
        RedBlackTree(Item, Key); // default constructor

        void InsertKey(Item, Key);
        int InsertFixUp(Item, Key);
        int RemoveKey(Item, Key);
        int FindKey(Item, Key);

    private:
        RedBlackTree<Item, Key> *rootPointer;
        RedBlackTree<Item, Key> *NILL_LEAF;

};

template <class Item, class Key>
void RedBlackTree<Item, Key>::InsertKey(Item *&T, Key *&z)
{
    //node* nil=tree->nil;
    //node* root=tree->root;
    RBTNode *y;
    RBTNode *x;
    y=T->nil;
    x=T->root;

    while(x != T->nil)
    {
        y=x;
        if((z->key)<(x->key))
            x=x->left;
        else
            x=x->right;
    }

    y=z->parent;

    if(y == T->nil)
        z=T->root;
    else
    if((z->key)<(y->key))
        z=y->left;
    else
        z=y->right;
        z->left=T->nil;
        z->right=T->nil;
        z->colour=RED;
        InsertFixUp(T,z);
}
#endif /* REDBLACKTREE_H_ */

Thanks in advance.

Upvotes: 0

Views: 75

Answers (2)

Sceptical Jule
Sceptical Jule

Reputation: 917

You have to move the implementation of the function (the template) to the class definition.

template <class Item, class Key>
class RedBlackTree
{
//...
public:
    ~RedBlackTree(); // destructor
    RedBlackTree(Item, Key); // default constructor

    void InsertKey(Item *&T, Key *&z)
    {
        //...
    }

    //...
};

Upvotes: 0

Joseph Mansfield
Joseph Mansfield

Reputation: 110658

The problem is that the types of the arguments to InsertKey don't match the declaration. In the declaration the arguments are Item and Key, and in the implementation they are Item*& and Key*& (references to pointers). These need to match.

void InsertKey(Item, Key);
               ^^^^  ^^^
void RedBlackTree<Item, Key>::InsertKey(Item *&T, Key *&z)
                                        ^^^^^^^   ^^^^^^

Upvotes: 1

Related Questions