Thread: AVL Tree rotation help

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    4

    AVL Tree with strings? Memory overflow?

    I found a way to do what I wanted, and have the same problem, marvelous.

    The entire code is here: http://pastebin.com/wMfDtwfg for the int implementation
    or here: http://pastebin.ca/1964677 for the string implementation.

    My test is just a simple for loop that inserts a million int in ascending order. When I insert ten million the program breaks. One million int insertions uses up about a gig and a half of memory. But, I don't get any errors unless I do ten million inserts.

    What I will be doing is inserting strings from a text file. Specifically a dictionary, and words starting with S. It's a pretty big list. I'm getting weird heights like 4868, that I don't get when I simply insert an int. Could the problem lie here?

    Code:
         ifstream inFile;
        AVLTree dictionary;
        inFile.open("dictS.txt");
        string word;
        string definition;
        string dump;    
        while (!inFile.eof())
        {    
        
            inFile >> dump;
            if (dump.at(0) == '*')
            {    
                if (word != "")
                {
                    dictionary.insert(word, definition);
                    word = dump;
                    
                }    
                else
                {
                    word = dump;    
                }
                definition = "";
            }
            else
            {
                definition = definition + " " + dump;
            }
    
        }
        inFile.close();
    Any help would be appreciated.
    Last edited by nobusiness; 10-17-2010 at 01:45 AM.

  2. #2
    Registered User
    Join Date
    Oct 2010
    Posts
    4
    EDIT: Updating first post.
    Last edited by nobusiness; 10-17-2010 at 12:34 AM.

  3. #3
    Registered User
    Join Date
    Oct 2010
    Posts
    4
    I guess I've narrowed the problem down to this, the comparison of keys I use for insertion doesn't work for strings, at least not how I thought they would. And so I suppose I either need to write code to compare the strings how I want them compared (alphabetically) or revise how I handle multiple instances of the same key.
    Code:
    if (search ->key < parent->key)
    .....
    else if (search->key > parent->key)
    .....
    else // is the problem

  4. #4
    Registered User
    Join Date
    Oct 2010
    Posts
    4
    nope, wrong about that too.

    issue solved though.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. AVL tree rotation
    By Cpro in forum C++ Programming
    Replies: 8
    Last Post: 03-26-2008, 07:09 AM
  3. 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
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM