pointer problem in implementing Tree in C

Question

I am implementing an avl tree for my assignment.

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

struct TreeNode {
  char *item;
  struct TreeNode *left;
  struct TreeNode *right;
  signed char balance;
};

typedef struct TreeNode Node;

void _print_avl (Node *, int , const char *);

Node * get_new_node (char *);
int avl_insert(Node *, char *);
void print_avl (Node *);
void avl_swr(Node*);

int main (int argc, char *argv[])
{
  Node *root = get_new_node("thura");
  avl_insert(root, "thur2");
  print_avl(root);

  avl_insert(root, "thur1");

  return 0;
}

int avl_insert(Node *root, char *item)
{
  assert(root);

  if( strcmp(item, root->item) < 0) {

        if(!root->left) {
          root->left = get_new_node(item);
          if(--(root->balance)) return 1;
          return 0;
        } else  {
          if(avl_insert(root->left, item)) {
                if( root->balance-- < 0) {
                  avl_swr(root); //Rotate the node right.
                  print_avl(root); //Here, the tree is corrupted.
                  return 0;
                }
                return 1;
          }
        }
  } else {
        if(!root->right) {
          root->right = get_new_node(item);
          if(++(root->balance)) return 1;
          return 0;
        }
        else {
          if(avl_insert(root->right, item)) {
                root->balance++;
                return 1;
          }
        }
  }
  return 0;
}

void avl_swr(Node* root)
{
  Node *node = root;
  root = node->left;

  node->left = NULL;
  node->balance = 0;

  root->right = node;
  root->balance++;

  print_avl(root); // It is working fine here.
}

Node * get_new_node (char *item) {
  Node * node = (Node *)malloc(sizeof(Node));
  node->item  = item;
  node->left  = NULL;
  node->right = NULL;
  node->balance = 0;
  return node;
}

void print_avl (Node *node)
{
  _print_avl(node, 0, "\t\t");
}

void _print_avl (Node *node, int depth, const char *delim)
{
  if(!node)
        return;
  int i = 0;
  while(i++ < depth) printf("%s", delim);
  printf("--> %s:%d\n", node->item, node->balance);

  depth++;

  if(node->left)
        _print_avl (node->left, depth, delim);

  if(node->right)
        _print_avl (node->right, depth, delim);
}

The problem is when I rotate the tree, using avl_swr (), it is successfully rotated according to the print_avl (), but when the function returns to the caller, the tree is corrupted. Any ideas?

Answer 1

The problem with avl_swr() is related to the function signature: void avl_swr(Node* root) and the assignment: root = node->left;

The root pointer is not being updated when the function returns (only a local copy within the function is being updated). The signature should be: void avl_swr(Node** root) in order to have the desired result.

Answer 2

The copy of the pointer is updated. You need to pass in a pointer to a pointer in your rotate function.

Answer 3

That's because the root variable in avl_insert does not change in avl_swr. When you pass it to avl_swr, a copy of the pointer is made. You change this pointer.

Change the calls to root = avl_swr(...) and have avl_swr return the root.

Answer 4

not 100% sure, but I do see one problem. In avl_swr() you change root to left subtree. So when you print out in avl_swr() you'll have root = "thur2". But when you return to avl_insert(), root there is unchanged, still pointing to "thura", which now has no children. So when you print that root it shows no children. Perhaps that's what you mean by corrupted? The solution is obviously to change the "root" in avl_insert(). You can do this by having avl_swr return the new root value, or by changing the parameter from "Node* root" to "Node** root" so that change in avl_swr is "passed back" to avl_insert