Clever Geek Handbook

Pointer problem with tree implementation in C

I am using 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 rotates successfully according to print_avl (), but when the function returns to the caller, the tree is corrupted. Any ideas?

+2


source to share


4 answers


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 updated when the function returns (only the local copy inside the function is updated). The signature must be: void avl_swr(Node** root)

to get the desired result.

+5


source


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



+1


source


This is 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 created. You are changing this pointer.

Change the calls to root = avl_swr(...)

and return the root directory to avl_swr.

+1


source


not 100% sure, but I see one problem. In avl_swr (), you change the root to the left subtree. So when you type in avl_swr (), you get root = "thur2". But when you go back to avl_insert (), root remains unchanged, still pointing to "thura", which now has no children. So when you type this root, it has no children. Perhaps this is what you mean by corrupt? Obviously the solution is to change the "root" in avl_insert (). You can do this if avl_swr returns a new root value, or by changing the "Node * root" parameter to "Node ** root" so that the change in avl_swr "went backwards" to avl_insert

0


source






More articles:


All Articles