AVL implementation in C

[Lyn Powell]

I've translated the algorithm from The Art of Computer Programming
volume 3 for AVL balanced tree insertion into C. While I understand the
concept behind the algorithm, the actual implementation has me stumped
because I just can't get it to work. I posted in comp.programming and was
pointed toward this group if I couldn't figure out my problem. Well, I
tried, and I can't, so here I am. The following code, when using the input
data 5, 4, 3, 2, 1, simply doesn't balance. I have no problem inserting the
data, but the tree is still degenerate.

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

struct node {
struct node *left, *right;
int balance, data;
};

struct tree {
struct node *header;
};

int insert(struct tree *HEAD, struct node *n, int K)
{
struct node *T, *S, *P, *Q, *R;
int a;

if (HEAD->header == NULL) {
HEAD->header = malloc(sizeof *HEAD->header);
HEAD->header->right = n;
HEAD->header->left = NULL;
return 1;
}
T = HEAD->header;
S = P = HEAD->header->right;
while (1) {
if (K < P->data) {
Q = P->left;
if (Q == NULL) {
P->left = Q = n;
break;
}
T = P;
S = Q;
P = Q;
}
else if (K > P->data) {
Q = P->right;
if (Q == NULL) {
P->right = Q = n;
break;
}
T = P;
S = Q;
P = Q;
}
else
return 0;
}
if (K < S->data)
a = -1;
else
a = +1;
R = P = (a == -1) ? S->left : S->right;
while (P != Q) {
if (K < P->data) {
P->balance = -1;
P = P->left;
}
else {
P->balance = +1;
P = P->right;
}
}
if (S->balance == 0)
S->balance = a;
else if (S->balance == -a)
S->balance = 0;
else if (S->balance == a) {
if (R->balance == a) {
P = R;
if (a == -1) {
S->left = R->right;
R->right = S;
}
else {
S->right = R->left;
R->left = S;
}
S->balance = R->balance = 0;
}
else if (R->balance == -a) {
if (a == -1) {
P = R->right;
R->right = P->left;
P->left = R;
S->left = P->right;
P->right = S;
}
else {
P = R->left;
R->left = P->right;
P->right = R;
S->right = P->left;
P->left = S;
}
if (P->balance == a) {
S->balance = -a;
R->balance = 0;
}
else if (P->balance == 0) {
S->balance = 0;
R->balance = 0;
}
else if (P->balance == -a) {
S->balance = 0;
R->balance = a;
}
P->balance = 0;
}
if (S == T->right)
T->right = P;
else
T->left = P;
}

return 1;
}

void print_tree_structure(struct node *node, int level)
{
int i;

if (node == NULL) {
for (i = 0; i < level; i++)
printf ("\t");
printf ("*\n");
}
else {
print_tree_structure(node->right, level+1);
for (i = 0; i < level; i++)
printf("\t");
printf("%d\n",node->data);
print_tree_structure(node->left, level+1);
}
}

int main(void)
{
struct tree tree = {0};

/* Temporary test scaffolding */
while (1) {
struct node *node = malloc(sizeof *node);
node->data = getchar()-'0';
getchar();
if (node->data == EOF)
break;
node->balance = 0;
node->left = node->right = NULL;
insert(&tree, node, node->data);
print_tree_structure(tree.header->right, 0);
}

return 0;
}

My best guess based on debugging efforts is that the balance of S is always
equal to 0, so the case where rotating is done never comes up. This is the
part the confuses me the most because I've duplicated the algorithm that
Knuth gives to the point where I don't see any differences in the logic. I
know when I can't solve a problem without help, so could somebody give me a
hint as to the problem, or a direction where I should start looking again?

 

[Ben Pfaff]

[...implementing Knuth Algorithm 6.2.3A...]

T = HEAD->header;
S = P = HEAD->header->right;
while (1) {
if (K < P->data) {
Q = P->left;
if (Q == NULL) {
P->left = Q = n;
break;
}

This is step A3, but you omitted the conditional "Otherwise if B(Q) !=
0" on the assignments to T and S.

T = P;
S = Q;
P = Q;
}
else if (K > P->data) {
Q = P->right;
if (Q == NULL) {
P->right = Q = n;
break;
}

Ditto for A4.

T = P;
S = Q;
P = Q;
}
else
return 0;
}
if (K < S->data)
a = -1;
else
a = +1;
R = P = (a == -1) ? S->left : S->right;

The code is easier to read and to write if you give your nodes a
single "link" member that is an array of two elements, and then
use 0 and 1 in place of -1 and +1, !a in place of -a, etc.

The rest looks okay to me at first read.

 

[Lyn Powell]

This is step A3, but you omitted the conditional "Otherwise if B(Q) !=
0" on the assignments to T and S.

Ditto for A4.

That was the problem. For some reason I was reading it, if Q == NULL do so
and so, otherwise if Q is != NULL, do the other stuff. Thanks, now that it
works I can try to fully understand it.

 

[CBFalconer]

That was the problem. For some reason I was reading it, if Q ==
NULL do so and so, otherwise if Q is != NULL, do the other stuff.
Thanks, now that it works I can try to fully understand it.

More important, you have now learned how to properly present
enquiries in the newsgroups. Welcome.