Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Odoacer

Weird binary tree problem

This topic is 5371 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m making a random story generator using Markov chains. I''m using a binary tree to store all the word pairs. It works fine for the most part, but a few words are listed as out of order sometimes in random places, usually a few letter-groups up or down (ie, a word beginning with H will be somewhere in the G group and so forth). This only seems to happen once or twice for every couple hundred of words but it''s enough to mess up my searching. Here''s the code I use to build my tree:
//story: Our main document tree.

//oldWord: The world to be compared, will be inserted as ''word1'' in the new WordNode element.

//newWord: The word we''ve just recieved from text input, its only use now is to fill in ''word2''

//         When the new node is created, newWord will go on to become the oldWord for the next 

//         node. (This akes place in a different function though.)


WordNode &buildTree(WordNode &story, const apstring &oldWord, const apstring &newWord){
    if(oldWord == story.word1){ //two words match, add it to the ''down'' branch of the tree

        if(story.down == NULL)
            story.down = new WordNode(oldWord, newWord);
        else
            buildTree(*story.down, oldWord, newWord); 
    }else if(oldWord > story.word1){ //word is larger, add it to the right branch

        if(story.right == NULL)
            story.right = new WordNode(oldWord, newWord);
        else
            buildTree(*story.right, oldWord, newWord);
    }else{
        if(story.left == NULL) { //otherwise, add to the left branch

            story.left = new WordNode(oldWord, newWord);
        } else {
            buildTree(*story.left, oldWord, newWord); }
   } 
   return story;
}

Share this post


Link to post
Share on other sites
Advertisement
I don''t see anything immediately horrible with your function, but the whole code isn''t visible. It could be an issue with the WordNode constructor. Is apstring a custom class? If so, are you sure the comparison operators work properly?

Share this post


Link to post
Share on other sites
yes, apstring is a (kinda)custom string class. I got it last year as part of my AP computer science course. I''ve looked through the code, its comparison operators just call the C strcmp() function which should work fine.

Here''s my WordNode struct:


//sorry its kinda messy

struct WordNode{
apstring word1, word2;
WordNode *left, *right, *down;
WordNode(apstring W1, apstring W2, WordNode *L = NULL, WordNode *R = NULL, WordNode *D = NULL)
:word1(W1), word2(W2), left(L), right(R), down(D){}
WordNode():word1(""), word2(""), left(NULL), right(NULL), down(NULL){}
};


The code I use to get my file is only a few lines long but its pretty standard (i think), I can post that too if it''s needed.

Share this post


Link to post
Share on other sites
I found the problem, I was comparing the wrong pair of words in my search function. Man, I feel so dumb because I checked that a million times.

Thanks for the help anyway dude.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!