By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
462,356 Members | 546 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 462,356 IT Pros & Developers. It's quick & easy.

Help with Parent Pointer in Recursive AVL Tree

P: 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
Share this Question
Share on Google+
1 Reply

weaknessforcats
Expert Mod 5K+
P: 9,197
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.