desperately need help with avl tree

**bluebear1608** · 10-07-2009

i am required to create an avl tree that will store the lyrics of songs read in from a file.
i am then required to implement a function that will let the user enter a word query. the function is to search the avl tree and display the songs that the word is in, and the position(word number it is in the song)
for some reason, some of the words are missing. i tried entering the first word in the song, but it doesnt exist in the tree.

my insert function is as follow

Code:

AvlTree Insert( ElementType X, AvlTree T )
{
  int i;
  struct Song *song, *prev;
  if( T == NULL )
  {
    /* Create and return a one-node tree */
    T = malloc( sizeof( struct AvlNode ) );
    if( T == NULL )
    {
      printf("Error allocating space");
      exit(EXIT_FAILURE);
    }
    else
    {
      T->Element = X;
      T->Height = 0;
      T->Left = T->Right = NULL;
    }
  }
  else
  {
    if( strcmp(X->string,T->Element->string)<0 )
    {
      T->Left = Insert( X, T->Left );
      if( Height( T->Left ) - Height( T->Right ) == 2 )
      {
        if( strcmp(X->string, T->Left->Element->string)<0 )
          T = SingleRotateWithLeft( T );
        else
          T = DoubleRotateWithLeft( T );
      }
    }
    else
    {
      if( strcmp(X->string,T->Element->string)>0 )
      {
        T->Right = Insert( X, T->Right );
        if( Height( T->Right ) - Height( T->Left ) == 2 )
        {
          if( strcmp(X->string, T->Right->Element->string)>0 )
            T = SingleRotateWithRight( T );
          else
            T = DoubleRotateWithRight( T );
        }
      }
      /*else if word is already in list*/
      if(strcmp(X->string,T->Element->string)==0)
      {
        song = T->Element->firstSong;
        while(song!=NULL && song->Number!=X->firstSong->Number)
        {
          prev=song;
          song=song->nextSong;
        }
        if(song == NULL)
        {
          prev->nextSong = X->firstSong;
        }
        else if(song->Number == X->firstSong->Number)
        {
          for(i=1;i<100;i++)
          {
            if(song->Position[i]==-1)
            {
              song->Position[i]=X->firstSong->Position[0];
              break;
            }
          }
        }
      }
    }
  }
  T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
   return T;
}

when i call the funtion, is just have
Avltree T;
while(blah blah)
T = insert(word,T);

**quzah** · 10-07-2009

If T is not a pointer to a pointer, you cannot actually make it point to anything new. That is to say:

Code:

foo *p;
...
bar( p ); /* p will not retain its new memory if we did something like... */
...
void bar( foo *p )
{
    p = malloc( sizeof *p ); /* won't actually do anything useful once this function returns... */
}

To make a variable retain a value change through a function call, you need a pointer to that type. Thus:

Code:

foo *p;
...
bar( &p );
...
void bar( foo **p )
{
    *p = malloc( sizeof **p );
}

That's my at-a-glance guess as to what your problem is.

Quzah.

Thread: desperately need help with avl tree

Thread Tools

Search Thread

Display

desperately need help with avl tree

Similar Threads

Binary Tree Search

Interpreter.c

Binary Search Trees Part III

Request for comments

BST/Red and Black Tree