Thread: Insertion into a Random BST

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);
    }
}

The only thing that looks suspicious to me is:
- size isn't incremented at the end of an insertPrivateRoot() recursion
- your rotation methods are labeled backwards (as I learned it anyways) - in other words, the code in rightRotate() is doing a "left rotation"

gg

Have you solved the problem yet? What was it?

gg