471,895 Members | 2,286 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,895 software developers and data experts.

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 3548
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 YellowAndGreen | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.