473,320 Members | 2,094 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

AVL implementation in C

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?
Nov 14 '05 #1
3 8662
"Lyn Powell" <me******************@earthlink.net> writes:

[...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.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Nov 14 '05 #2

"Ben Pfaff" <bl*@cs.stanford.edu> wrote
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.
Nov 14 '05 #3
Lyn Powell wrote:
"Ben Pfaff" <bl*@cs.stanford.edu> wrote
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.


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

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: jenniferyiu | last post by:
IMHO, simply NO. False actually, practically.
9
by: Anon Email | last post by:
Hi people, I'm learning about header files in C++. The following is code from Bartosz Milewski: // Code const int maxStack = 16; class IStack
29
by: Enrico `Trippo' Porreca | last post by:
Both K&R book and Steve Summit's tutorial define a getline() function correctly testing the return value of getchar() against EOF. I know that getchar() returns EOF or the character value cast to...
52
by: lovecreatesbeauty | last post by:
Why the C standard committee doesn't provide a standard implementation including the C compiler and library when the language standard document is published? C works on the abstract model of low...
20
by: Luc Kumps | last post by:
(Sorry about the previous post, it got transmitted before it was complete) We try to separate implementation and interface defintions, but we run into a problem. I hope the guru's can solve this,...
7
by: desktop | last post by:
I the C++ standard page 472 it says that an associative container can be constructed like X(i,j,c) where i and j are input iterators to elements. But in the implementation there is no constructor...
6
by: Ralph | last post by:
Hi, I was reading effictive C++ and some other books again and they all tell you about hiding implementation details (proxy/pimpl/inheritance) but they never really explain when to use it. I...
0
by: anto.anish | last post by:
Hi , Since, i did not want to write instantiations in Source file of all template methods for various different datatypes that my client might use, i choose to write implementation of template...
1
by: anto.anish | last post by:
Hi , Since, i did not want to write explicit instantiations in Source file of all template methods for various different datatypes that my client might use, i choose to write implementation of...
173
by: Ron Ford | last post by:
I'm looking for a freeware c99 compiler for windows. I had intended to use MS's Visual C++ Express and use its C capability. In the past with my MS products, I've simply needed to make .c the...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.