fork download

typedef struct node *tree;
 
int height(tree t){           // height of a (sub) tree
   if (t == NULL) return 0;
   return t->height;               // relies on memoized height value
}
 
static int max(int a, int b) {       // utility function -- maximum
   if (a > b) return a;
   return b;
}
 
static void memoize(tree t){       // update fields after tree mutation
   if (t == NULL) return;
   t->height = 1 + max(height(t->left), height(t->right));
}
 
static tree newnode(int d){       // create a new treenode
   tree t = malloc(sizeof(struct node));
   t->data = d;
   t->left = NULL;
   t->right = NULL;
   memoize(t);
   return t;
}
 
static void setleft(tree t, tree p){  // set left link and memoize
   t->left = p;
   memoize(t);
}
 
static void setright(tree t, tree p){  // set right link and memoize
   t->right = p;
   memoize(t);
}
 
static tree raise_right(tree t) { // "left" rotation
   tree tmp = t->right;
   setright(t, tmp->left);
   setleft(tmp, t);
   return tmp;
}
 
static tree raise_left(tree t) { // "right" rotation
   tree tmp = t->left;
   setleft(t, tmp->right);
   setright(tmp, t);
   return tmp;
}
 
static tree rebalance(tree t){                        // rebalance after insert/del
   if (t == NULL) return t;
   if (height(t->left) > 1 + height(t->right)) {         // left too high
      if (height(t->left->right) > height(t->left->left)) {   
         setleft(t, raise_right(t->left));              // first of double rotation
      }
      return raise_left(t);                       // single/second rotation
   }
   if (height(t->right) > 1 + height(t->left)) {         // right too high
      if (height(t->right->left) > height(t->right->right)) {
         setright(t, raise_left(t->right));               // first of double rotation
      }
      return raise_right(t);                      // single/second rotation
   }
   return t;
}
 
tree insertavl(tree t, int d){                   // AVleft preserving insert
   if (t == NULL) return newnode(d);
   if (d < t->data) {
      setleft(t, insertavl(t->left, d));
   } else {
      setright(t, insertavl(t->right, d));
   }
   return rebalance(t);
}
 
static tree remove_rightmost(tree t, int *d){  // sets d to deleted key
   if (t->right == NULL) {
      *d = t->data;
      tree tmp = t->left;
      free(t);
      return tmp;
   }
   setright(t, remove_rightmost(t->right, d));
   return rebalance(t);
}
 
tree deleteavl(tree t, int d){         // delete node with key value d
   if (t == NULL) return t;
   if (d < t->data) {                  // recurse left
      setleft(t, deleteavl(t->left, d));
   } else if (d > t->data) {           // recurse right
      setright(t, deleteavl(t->right, d));
   } else if (t->right == NULL) {       // no right child; promote left
      tree tmp = t;
      t = t->left;
      free(tmp);
   } else if (t->left == NULL) {       // no left child; promote right
      tree tmp = t;
      t = t->right;
      free(tmp);
   } else {
      setleft(t, remove_rightmost(t->left, &t->data)); // replace root key
   }
   return rebalance(t);
}

prog.cpp: In function ‘int height(node*)’:
prog.cpp:4: error: ‘NULL’ was not declared in this scope
prog.cpp:5: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘void memoize(node*)’:
prog.cpp:14: error: ‘NULL’ was not declared in this scope
prog.cpp:15: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:15: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:15: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘node* newnode(int)’:
prog.cpp:19: error: invalid application of ‘sizeof’ to incomplete type ‘node’ 
prog.cpp:19: error: ‘malloc’ was not declared in this scope
prog.cpp:20: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:21: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:21: error: ‘NULL’ was not declared in this scope
prog.cpp:22: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘void setleft(node*, node*)’:
prog.cpp:28: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘void setright(node*, node*)’:
prog.cpp:33: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘node* raise_right(node*)’:
prog.cpp:38: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:39: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘node* raise_left(node*)’:
prog.cpp:45: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:46: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘node* rebalance(node*)’:
prog.cpp:52: error: ‘NULL’ was not declared in this scope
prog.cpp:53: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:53: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:54: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:54: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:55: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:59: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:59: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:60: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:60: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:61: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘node* insertavl(node*, int)’:
prog.cpp:69: error: ‘NULL’ was not declared in this scope
prog.cpp:70: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:71: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:73: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘node* remove_rightmost(node*, int*)’:
prog.cpp:79: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:79: error: ‘NULL’ was not declared in this scope
prog.cpp:80: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:81: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:82: error: ‘free’ was not declared in this scope
prog.cpp:85: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp: In function ‘node* deleteavl(node*, int)’:
prog.cpp:90: error: ‘NULL’ was not declared in this scope
prog.cpp:91: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:92: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:93: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:94: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:95: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:95: error: ‘NULL’ was not declared in this scope
prog.cpp:97: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:98: error: ‘free’ was not declared in this scope
prog.cpp:99: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:101: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:102: error: ‘free’ was not declared in this scope
prog.cpp:104: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’
prog.cpp:104: error: invalid use of incomplete type ‘struct node’
prog.cpp:1: error: forward declaration of ‘struct node’

Standard output is empty