Insertion into a Random BST

This is a discussion on Insertion into a Random BST within the C++ Programming forums, part of the General Programming Boards category; Hello everyone, I'm writing a random BST, and, other than the first node, I am always inserting at the root. ...

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    80

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

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,676
    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

  3. #3
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,676
    Have you solved the problem yet? What was it?

    gg

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Another brain block... Random Numbers
    By DanFraser in forum C# Programming
    Replies: 2
    Last Post: 01-23-2005, 04:51 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Simple BST root insertion help
    By Extrovert in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 11-19-2003, 09:30 AM
  5. Best way to generate a random double?
    By The V. in forum C Programming
    Replies: 3
    Last Post: 10-16-2001, 04:11 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21