Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #402935
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: AVL tree insertion - programming exercise |
| Date | 2026-10-10 19:02 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <86bj91j8p6.fsf@linuxsc.com> (permalink) |
| References | <86ece2kppv.fsf@linuxsc.com> <11ae48u$21bo6$1@dont-email.me> |
Andrey Tarasevich <noone@noone.net> writes:
> On Tue 10/6/2026 11:08 PM, Tim Rentsch wrote:
>
>> I offer this small programming exercise for anyone who is
>> interested.
>
> I did exactly that a couple of months ago, except that my case the AVL
> tree was intended to serve as a carrying sub-structure for an
> augmented interval tree. I did not make any effort to decouple the
> implementations, meaning that my AVL implementation is intermixed with
> the interval tree implementation.
>
> Also, I had to support not only operations that start from the root of
> the tree (like your `add_key`), but also operations that start from a
> specific arbitrary node (e.q. a `delete_node(Node *)` operation). So,
> in my case I opted to also keep and maintain the parent link in each
> node. Extra memory expenditure is not that drastic, especially
> considering the fact that my nodes are already heavier - carrying
> geometric data for the interval tree.
Right. Clearly your requirements were more extensive than those of
my simple programming exercise.
> Meanwhile, you seem to be striving to squeeze out all "unnecessary"
> memory usage (re: embedding the balance value into the unused pointer
> bits). Is this a hard requirement in your exercise?
It might be useful to give some history as background for my
comments, and for the exercise.
More than a few years ago I was interested in using trees, of some
as-yet-to-be-determined variety, as the basis for a (generic) set
data type. One of the kinds of trees I looked into was AVL trees.
Because I had a copy of Sorting and Searching handy, I pulled it off
the shelf and read about AVL trees. To help my exploration, I took
the Knuth description of AVL-tree insertion and transliterated it
into C. Here is the result, more or less a direct expression of the
AVL-insertion algorithm given in Sorting and Searching:
#include <assert.h>
#include <stdlib.h>
typedef struct tree_node_s *Tree;
typedef signed int Key;
typedef signed int Balance;
struct tree_node_s {
Tree left, right;
Key key;
Balance b;
};
void
avl_insert( Tree head, Key k ){
Tree t, s, p, q, r;
Balance a;
A1:
t = head, s = p = head->right;
/* fall through */
A2:
if( k < p->key ) goto A3;
if( k > p->key ) goto A4;
return;
A3:
q = p->left;
if( !q ){
p->left = q = malloc( sizeof *q );
goto A5;
}
if( q->b != 0 ) t = p, s = q;
p = q;
goto A2;
A4:
q = p->right;
if( !q ){
p->right = q = malloc( sizeof *q );
goto A5;
}
if( q->b != 0 ) t = p, s = q;
p = q;
goto A2;
A5:
q->left = q->right = 0, q->key = k, q->b = 0;
/* fall through */
A6:
if( k < s->key ) r = p = s->left;
else r = p = s->right;
while( p != q ){
if( k < p->key ) p->b = -1, p = p->left;
else p->b = +1, p = p->right;
}
/* fall through */
A7:
if( k < s->key ) a = -1;
else a = +1;
if( s->b == 0 ){
s->b = a;
return;
}
if( s->b == -a ){
s->b = 0;
return;
}
if( s->b == a ){
if( r->b == a ) goto A8;
if( r->b == -a ) goto A9;
assert( 0 );
}
assert( 0 );
A8:
p = r;
if( a == 1 ) s->right = r->left, r->left = s;
else s->left = r->right, r->right = s;
s->b = r->b = 0;
goto A10;
A9:
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->b == a ) s->b = -a, r->b = 0;
if( p->b == 0 ) s->b = 0, r->b = 0;
if( p->b == -a ) s->b = 0, r->b = -a;
p->b = 0;
/* fall through */
A10:
if( s == t->right ) t->right = p;
else t->left = p;
}
The code compiles but I can't say more than that. To the best of my
recollection it was never actually run.
Because I found the above "explanation" so unhelpful in trying to
understand how AVL trees work, I wrote my own AVL-insertion code in
C, using an interface similar to the one shown in my posting stating
the exercise. (The earlier interface was slightly more elaborate
because it allowed for "threading" of the binary tree, but I took
that aspect out of the exercise problem.)
In my revised version, it made sense to put the extra state "inside"
the pointers, in order to distinguish a "true" link from a "thread"
link in the tree traversal algorithms. In posting the exercise I
took out the second extra bit (the bit saying this link is a thread
link) but otherwise left it alone. In some ways I think having the
"taller" bit be part of the links simplifies the algorithm slightly
but I didn't really think about that when posting the exercise.
There is an advantage (to me) to keep that interface, since I
already have a test rig to drive it. There wasn't any sort of
consideration about the nature of the exercise, just a pragmatic
thought that if there were any testing to be done it would be
easier to use the same interface.
I posted the exercise because I thought some people might enjoy
writing some C code, and because I was (and am) curious about how
other people would implement AVL insertion in C. AVL trees are
rather tricky to implement, and I wonder what other people would do
to deal with that barrier. And since you have some experience (and
also a good level of expertise) I hope you will take the time to
write and post an answer.
Incidentally, in my tree investigation of many years ago, the winner
(judged by an unspecified metric) ended up being 2-3-4 trees. But
that is a topic for another day (and most likely another newsgroup,
since it wasn't written in C).
Back to comp.lang.c | Previous | Next — Previous in thread | Find similar | Unroll thread
AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 23:08 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 15:25 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-07 12:13 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 21:28 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:31 -0700
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-07 20:10 -0500
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:56 -0700
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 15:09 -0500
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-08 22:56 +0200
Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 17:29 -0500
Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 09:56 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 01:39 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-09 00:03 -0700
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 23:53 -0700
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 10:34 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 12:27 +0200
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 12:59 +0200
Re: AVL tree insertion - programming exercise bart <bc@freeuk.com> - 2026-10-09 11:43 +0100
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 13:20 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 12:38 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 16:05 +0200
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 17:54 +0200
Re: AVL tree insertion - programming exercise Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-10-10 10:38 +0800
Re: AVL tree insertion - programming exercise ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-10 03:12 +0000
Re: AVL tree insertion - programming exercise Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-10 04:44 +0000
Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-10 14:12 -0700
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 19:48 +0000
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-09 23:18 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 15:27 +0200
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-09 17:47 +0300
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 16:48 +0000
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 19:08 +0300
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 18:29 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:44 +0000
Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 23:22 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:43 +0000
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 20:35 +0200
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 19:36 +0000
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:08 +0200
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:21 +0300
Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 20:55 +0000
Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-10 20:22 +0000
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:32 +0300
Re: AVL tree insertion - programming exercise Bonita Montero <Bonita.Montero@gmail.com> - 2026-10-10 19:40 +0200
Re: AVL tree insertion - programming exercise Andrey Tarasevich <noone@noone.net> - 2026-10-10 12:39 -0700
Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:00 +0300
Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:28 +0200
Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-10 19:02 -0700
csiph-web