L
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?
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?