When I try to create an opject of type rbtree it appears to complete the initialization successfully, however, when I try to insert a node using the public member insert, it return this while compiling:
error: no matching function for call to ‘rbtree<std::basic_string<char>>::insert(std::basic_string<char>&, node<std::basic_string<char> >*&)’
template <typename T>
struct node
{
T data;
bool red;
node<T> *link[2]; // [0] is left, [1] is right
};
template <typename T>
class rbtree
{
public:
rbtree() // Construct without arguments; nodes are inserted later
{
treeRoot=NULL;
};
void insert (T data) // Insert a new node and balance the tree
{
if(treeRoot!=NULL)
{
insert(data, treeRoot); // Call a recursive insert to find the right place
}
else
{
treeRoot=new node<T>;
treeRoot->data=data;
treeRoot->link[0]=NULL;
treeRoot->link[1]=NULL;
}
};
node<T> *search (T data) // Search the tree for a node
{
};
void print (); // Print inorder traversal of tree to stdout
private:
node<T> *treeRoot; // Root node of tree
bool isRed (node<T> *root) // Helper function to determine if a node is red or not (assume null pointers are black)
{
return root != NULL && root->red == true;
};
void insert (T data, node<T> root)
{
if(data< root->data)
{
if(root->link[0]!=NULL)
insert(data, root->link[0]);
else
{
root->link[0]=new node<T>;
root->link[0]->data=data;
root->link[0]->link[0]=NULL; //Sets the left child of the child node to null
root->link[0]->link[1]=NULL; //Sets the right child of the child node to null
}
}
elseif(data>=root->data)
{
if(root->link[1]!=NULL)
insert(data, root->link[1]);
else
{
root->link[1]=new node<T>;
root->link[1]->data=data;
root->link[1]->link[0]=NULL; //Sets the left child of the child node to null
root->link[1]->link[1]=NULL; //Sets the right child of the child node to null
}
}
};
node<T> *singleRotate (node<T> *root, bool dir); // Rotate once. False is left, true is right.
};
Any ideas? It seems like it should be compiling okay, and I don't see how it could be an ambiguous case.
Your private overload for insert() takes the node by value and T by value, while the error message says you are passing T by reference and a pointer to a node by reference, and this is the overload that it complains it cannot find.
First of all, your insert() function should take T and node<T> by reference to increase performance and avoid copy construction, which may be problematic on more complex data types (classes).
Second: Your treeRoot variable is of type "pointer to a node<T>", but your insert takes a node<T>. If you want to preserve treeRoot's data type (I would), then you need to change your insert() overload to take a pointer of node<T>, or call the overload in line 23 as insert(data, *treeRoot);. If you change your overload to accept a pointer, then take the pointer by value; if you leave your overload as you have it now, then at least take the node by reference.