Hello everyone,
I'm writing a random BST, and, other than the first node, I am always inserting at the root. I don't know why this is....any ideas?
Code:
header File:
class RandBST
{
private:
class node
{
public:
Files file;
node* left;
node* right;
node(Files f)
{ file = f; left = NULL; right = NULL; }
};
node* root;
int size;
Files* findPrivate(node*, const char*);
void rightRotate(node*&);
void leftRotate(node*&);
void insertPrivate(node*&, const char*, int);
void insertPrivateRoot(node*&, const char*, int);
void printPrivate(node*);
public:
RandBST()
{ root = NULL; size = 0; }
Files* find(const char* wordToFind)
{ return findPrivate(root, wordToFind); }
void insert(const char* wordToFind, int fileNum)
{ insertPrivate(root, wordToFind, fileNum); }
void print()
{ printPrivate(root); }
};
/*-------------------------------------------------*/
void RandBST::rightRotate(node*& ptr)
{
node* leftPtr = ptr->left;
ptr->left = leftPtr->right;
leftPtr->right = ptr;
ptr = leftPtr;
}
void RandBST::leftRotate(node*& ptr)
{
node* rightPtr = ptr->right;
ptr->right = rightPtr->left;
rightPtr->left = ptr;
ptr = rightPtr;
}
void RandBST::insertPrivate(node*& ptr, const char* wordToFind, int fileNum)
{
cout << ptr << endl;
if (ptr == NULL)
{
cout << "Adding: " << wordToFind << " to a NULL node" << endl;
Files* file = new Files;
file->setWord(wordToFind);
file->addFile(fileNum);
ptr = new node (*file);
cout << ptr << endl;
return;
}
if (rand() < RAND_MAX / (size + 1))
{
insertPrivateRoot(ptr, wordToFind, fileNum);
return;
}
if (strcmp(wordToFind, ptr->file.getWord()) < 0)
insertPrivate(ptr->left, wordToFind, fileNum);
else if (strcmp(wordToFind, ptr->file.getWord()) > 0)
insertPrivate(ptr->right, wordToFind, fileNum);
size++;
cout << "Size= " << size << endl;
}
void RandBST:: insertPrivateRoot(node*& ptr, const char* wordToFind, int fileNum)
{
if (ptr == NULL)
{
cout << "Inserting: " << wordToFind << " at the root" << endl;
Files* file = new Files;
file->setWord(wordToFind);
file->addFile(fileNum);
ptr = new node (*file);
return;
}
if (strcmp(wordToFind, ptr->file.getWord()) < 0)
{
insertPrivateRoot(ptr->left, wordToFind, fileNum);
rightRotate(ptr);
}
else if (strcmp(wordToFind, ptr->file.getWord()) > 0)
{
insertPrivateRoot(ptr->right, wordToFind, fileNum);
leftRotate(ptr);
}
}