I am having trouble getting past the initialization of the red black tree. Whenever I compile I get the following error.
redBlackTree.h:81:28: error: invalid conversion from ‘long int’ to ‘nodeColor’ [-fpermissive]
nodeType<myType> *x = new nodeType<myType>;
^
redBlackTree.h:10:8: error: invalid conversion from ‘long int’ to ‘nodeColor’ [-fpermissive]
struct nodeType
^
redBlackTree.h:81:28: note: synthesized method ‘nodeType<int>::nodeType()’ first required here
nodeType<myType> *x = new nodeType<myType>;
I am also having trouble searching the tree to make sure a value is not already inside the tree. The current method I can think of it this but I am still getting duplicate results inside of my tree.
if(nd != NULL)
{
if(nd->keyValue == x)
return true;
return ((search(x, nd->right)) || (search(x, nd->left)));
}
return false;
It is under the insertion function. Could it be how I am declaring my variables? We are supposed to follow a certain template and it says to make x a new nodeType but am not able to. Deleting it causes the program to have a seg fault.
#ifndef REDBLACKTREE_H
#define REDBLACKTREE_H
#include <iostream>
#include <sstream>
using namespace std;
enum nodeColor { RED, BLACK };
template<class myType>
struct nodeType
{
myType keyValue = keyValue;
nodeColor color = NULL;
nodeType *left = NULL;
nodeType *right = NULL;
nodeType *parent = NULL;
};
template <class myType>
class redBlackTree
{
public:
redBlackTree(){};
~redBlackTree();
void destroyTree();
unsigned int countNodes() const;
unsigned int height() const;
void printTree() const;
void insert(myType);
bool search(myType);
private:
nodeType<myType> *root = NULL;
bool search(myType, nodeType<myType> *);
void destroyTree(nodeType<myType> *);
unsigned int countNodes(nodeType<myType> *) const;
unsigned int height(nodeType<myType> *) const;
void printTree(nodeType<myType> *) const;
void rightRotate(nodeType<myType> *);
void leftRotate(nodeType<myType> *);
};
//template <class myType>
//redBlackTree<myType>::redBlackTree():root(NULL)
//{
//};
template <class myType>
redBlackTree<myType>::~redBlackTree()
{
destroyTree();
}
template <class myType>
void redBlackTree<myType>::destroyTree()
{
destroyTree(root);
};
template <class myType>
unsigned int redBlackTree<myType>::countNodes() const
{
return countNodes(root);
};
template <class myType>
unsigned int redBlackTree<myType>::height() const
{
return height(root);
};
template <class myType>
void redBlackTree<myType>::printTree() const
{
printTree(root);
};
template <class myType>
void redBlackTree<myType>::insert(myType value)
{
if(search(value))
return;
nodeType<myType> *x = new nodeType<myType>;
x->right = NULL;
x->left = NULL;
x->parent = NULL;
x->keyValue = value;
x->color = RED;
if(root == NULL)
{
root = x;
x->color = BLACK;
return;
}
nodeType<myType> *curr = root;
if(curr->keyValue > x->keyValue)
{
curr->left = x;
x->parent = curr;
x->color = RED;
}
else
{
curr->right = x;
x->parent = curr;
x->color = RED;
}
while(x != root && x->parent->color == RED)
{
if(x->parent == x->parent->parent->left)
{
if(x->parent->parent->right != NULL && x->parent->parent->color == RED)
{
x->parent->color = BLACK;
x->parent->parent->right->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
}
else
{
if(x == x->parent->right)
{
x = x->parent;
leftRotate(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rightRotate(x->parent->parent);
}
}
else
{
if(x->parent->parent->left != NULL && x->parent->parent->color == RED)
{
x->parent->color = BLACK;
x->parent->parent->left->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
}
else
{
if(x == x->parent->right)
{
x = x->parent;
rightRotate(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
leftRotate(x->parent->parent);
}
}
if(x == root)
x->color = BLACK;
}
};
template <class myType>
bool redBlackTree<myType>::search(myType x)
{
search(x, root);
};
template <class myType>
bool redBlackTree<myType>::search(myType x, nodeType<myType> *nd)
{
if(nd == NULL)
return 0;
search(x, nd->left);
search(x, nd->right);
if(nd->keyValue == x)
return true;
else
return false;
};
template <class myType>
void redBlackTree<myType>::destroyTree(nodeType<myType> *node)
{
if(node==NULL)
return;
destroyTree(node->left);
destroyTree(node->right);
delete node;
};
template <class myType>
unsigned int redBlackTree<myType>::countNodes(nodeType<myType> *nd) const
{
if(nd==NULL)
return 0;
return (countNodes(nd->left) + countNodes(nd->right) + 1);
};
template <class myType>
unsigned int redBlackTree<myType>::height(nodeType<myType> *nd) const
{
int leftHeight = 0;
int rightHeight = 0;
if(nd==NULL)
return 1;
leftHeight = leftHeight + height(nd->left);
rightHeight = rightHeight + height(nd->right);
if(leftHeight == rightHeight)
return leftHeight;
else if(leftHeight > rightHeight)
return leftHeight;
else
return rightHeight;
};
template <class myType>
void redBlackTree<myType>::printTree(nodeType<myType> *nd) const
{
if(nd == NULL)
return;
printTree(nd->left);
cout << nd->keyValue;
printTree(nd->right);
cout << nd->keyValue;
};
template <class myType>
void redBlackTree<myType>::rightRotate(nodeType<myType> *y)
{
nodeType<myType> *x = y->left;
x->left = x->right;
if(x->right != NULL)
x->right->parent = y;
x->parent = y->parent;
if(x->parent == NULL)
root = x;
else if(y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
x->right = y;
y->parent = x;
};
template <class myType>
void redBlackTree<myType>::leftRotate(nodeType<myType> *x)
{
nodeType<myType> *y = y->right;
x->right = y->left;
if(x->right != NULL)
root = y;
else if(x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
x->left = x;
x->parent = y;
};
#endif
The problem is caused by the line:
nodeColor color = NULL;
NULL is not a valid value for color. Use a value that is valid, such as:
nodeColor color = RED;
Also, the line
myType keyValue = keyValue;
is going to be a problem. It initializes keyValue with the uninitialized value of keyValue.Make the RHS of that line something more appropriate, such as:
myType keyValue = {};
You are missing a return in the first search function.
template <class myType>
bool redBlackTree<myType>::search(myType x)
{
return search(x, root);
// ^^
}
You don't need ; at the end of member function definition. You have them in some of the function definitions. You should remove them.