Parse error?

[Albert]

Hi,

Why does GCC returns a parse error on line 42 where I make the root's
right child/link point to something new?

The following contains a modified insertion function for AA (Andersson)
trees. The only links that should be created are those when a value is
inserted and it is larger than any other value already in the tree.
Otherwise, what is passed replaces a value already in the tree. Note:
*no* values passed to this function will be equal.

Andersson trees are balanced binary search trees that are simpler to
implement than AVL trees. Split performs a right tree rotation, skew
performs a left tree rotation and bumps up the new "root" up a level. As
can be seen, newly added nodes start at level 1. Split and skew are
called in that order to remove left horizontal links and consecutive
links respectively and we move up through the "stack" (from recursion
) calling these functions to fix anything mixed up (in both insert() and
remove()).

I've removed the contents of main which initialises nil.

#include <stdlib.h>

struct node {
int value, level;
struct node *link[2];
};

struct node *nil;

struct node *skew(struct node *root)
{
if (root != nil) {
if (root->level == root->link[0]->level) {
struct node *save = root;
root = root->link[0];
save->link[0] = root->link[1];
root->link[1] = save;
}
root->link[1] = skew(root->link[1]);
}
return root;
}

struct node *split(struct node *root)
{
if (root->level == root->link[1]->link[1]->level && root != nil) {
struct node *save = root;
root = root->link[1];
save->link[1] = root->link[0];
root->link[0] = save;
++root->level;
root->link[1] = split(root->link[1]);
}
return root;
}

struct node *insert(struct node *root, int value)
{
if (root->link[value > root->value] != nil)
return root = split(skew(insert(root->link[value > root->value], value)));
else if (value > root->value) {
root->link[1] = (struct node *) malloc(struct node);
root->link[1]->value = value;
root->link[1]->level = 1;
root->link[1]->link[0] = root->link[1]->link[1] = nil;
return root = split(skew(root));
} else {
root->value = value;
return root;
}
}

int main()
{
return 0;
}

TIA,
Albert

 

[Beej Jorgensen]

root->link[1] = (struct node *) malloc(struct node);

malloc takes the number of bytes to allocate, not the type to allocate.
Try:

malloc(sizeof(struct node));

HTH,
-Beej

 

[Ben Pfaff]

root->link[1] = (struct node *) malloc(struct node);

You want malloc(sizeof(struct node)). I also recommend dropping
the cast.

I only looked at this line of your code.

 

[Albert]

root->link[1] = (struct node *) malloc(struct node);

malloc takes the number of bytes to allocate, not the type to allocate.
Try:

malloc(sizeof(struct node));

HTH,
-Beej

Thanks.