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

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?

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 messystruct 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.

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.