469,300 Members | 2,057 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,300 developers. It's quick & easy.

Help with Parent Pointer in Recursive AVL Tree

9
This is C code. I am trying to fill each node's Parent field with its parent because I am drawing nodes to the screen. However, I have not been able to get this working. Reading the output from the code and tracing it, it seems that the code does not continue recursing down into the tree to insert. Can someone please point me to what is wrong and help me understand why it is wrong? Thank you.

Expand|Select|Wrap|Line Numbers
  1. struct AvlNode* Insert( gint X, struct AvlNode* T )
  2. {          
  3.    static struct AvlNode *Parent;
  4.    static struct AvlNode *Root;
  5.    static int level = 0;
  6.  
  7.    if(Parent && T != NULL)
  8.      printf("\n\nThe Root is %d and the Parent is %d", T->Element, Parent->Element);
  9.  
  10.      if(T!= NULL)
  11.      printf(" But T is %d \n", T->Element);
  12.  
  13.  
  14.    if( T == NULL )
  15.    {
  16.         /* Create and return a one-node tree */
  17.         T = g_malloc( sizeof( struct AvlNode ) );
  18.  
  19.         if( T == NULL )
  20.           printf( "Error: Out of space!" );
  21.  
  22.         else
  23.         {                     
  24.             T->Element = X; T->Height = 0;
  25.             T->Left = T->Right = NULL;
  26.  
  27.             //Special Case for Root Node
  28.             if(FIRST_TIME)
  29.             {             
  30.               T->rect_x = app.drawing_area->allocation.width/2 - 25;
  31.               T->rect_y = 0;      
  32.  
  33.               draw_node(T, app);
  34.  
  35.               Root = T;
  36.               FIRST_TIME = 0;
  37.             }
  38.  
  39.          }
  40.     }
  41.  
  42.     else
  43.        if( X < T->Element )
  44.        {
  45.            printf("\n%d is less than %d\n", X, T->Element);
  46.  
  47.            Parent = T;
  48.  
  49.            ++level; 
  50.  
  51.            T = Insert( X, T->Left );
  52.  
  53.            --level; //Finished Insert Call, decrement recursive level
  54.  
  55.            if(level == 0)
  56.            T->Parent = Parent;
  57.  
  58.           //Draw T's Left Node to Screen
  59.           LEFT_NODE = 1;
  60.           T->rect_x = T->Parent->rect_x;
  61.           T->rect_y = T->Parent->rect_y;
  62.  
  63.           draw_node(T, app);
  64.           LEFT_NODE = 0;
  65.  
  66.  
  67.             if( Height( T->Left ) - Height( T->Right ) == 2 )
  68.             {
  69.                 printf("Performing Left Rebalancing\n");
  70.  
  71.                 if( X < ( (T->Left)->Element ) )
  72.                     T = SingleRotateWithLeft( T );
  73.  
  74.                 else
  75.                   T = DoubleRotateWithLeft( T );
  76.             }
  77.         }
  78.  
  79.  
  80.         else
  81.           if( X > T->Element )
  82.           {
  83.             printf("\n%d is greater than %d\n", X, T->Element);
  84.  
  85.              Parent = T;
  86.              ++level;
  87.  
  88.              T = Insert( X, T->Right );
  89.  
  90.  
  91.              --level;
  92.  
  93.              if(level == 0)
  94.              T->Parent = Parent;
  95.  
  96.  
  97.              //Draw Right Node
  98.              RIGHT_NODE = 1;
  99.              T->rect_x = T->Parent->rect_x;
  100.              T->rect_y = T->Parent->rect_y;
  101.  
  102.  
  103.              //Draw T's Right Node to Screen
  104.              draw_node(T, app);
  105.              RIGHT_NODE = 0;
  106.  
  107.  
  108.              if( Height( T->Right ) - Height( T->Left ) == 2 )
  109.              {  
  110.  
  111.                   printf("Performing Right Rebalancing\n");
  112.                   if( X > ( (T->Right)->Element) ) 
  113.                         T = SingleRotateWithRight( T );
  114.  
  115.                   else
  116.                     T = DoubleRotateWithRight( T );
  117.              }    
  118.  
  119.  
  120.         }
  121.  
  122.  
  123.    /* Else X is in the tree already; we'll do nothing */
  124.    T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
  125.  
  126.  
  127.    return T;
  128. }
  129.  
Apr 6 '08 #1
1 3263
weaknessforcats
9,208 Expert Mod 8TB
Havwe you stepped through this with your debugger or are you relying on those printf() statements?

A debugger session should find your problem right away.
Apr 6 '08 #2

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

10 posts views Thread by Sims | last post: by
reply views Thread by ghiro | last post: by
9 posts views Thread by JP SIngh | last post: by
6 posts views Thread by Ying Yang | last post: by
16 posts views Thread by Suzanne Vogel | last post: by
2 posts views Thread by dannielum | last post: by
4 posts views Thread by Tarique Jawed | last post: by
8 posts views Thread by jason | last post: by
1 post views Thread by none | last post: by
reply views Thread by zhoujie | last post: by
reply views Thread by suresh191 | last post: by
1 post views Thread by Geralt96 | last post: by
reply views Thread by harlem98 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.