Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #402780 > unrolled thread

AVL tree insertion - programming exercise

Back to article view | Back to comp.lang.c

Contents

  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

Page 3 of 3 — ← Prev page 1 2 [3]

#402898

On 2026-10-10 21:36, Dan Cross wrote:
> In article <11ae0h8$cjlv$3@dont-email.me>,
> Janis Papanagnou  <janis_papanagnou+ng@hotmail.com> wrote:
>> On 2026-10-10 18:08, Michael S wrote:
>>>> TAOCP
>>>
>>> It is still the best reference for *some* data structures and
>>> algorithms. Not necessarily something that is still practically
>>> important. In particular, I am thinking about external sortng.
>>
>> Have you anything specific in mind beyond merge-sort?
> 
> Radix sort?

I've only few dedicated books about "data structures and algorithms"
in my bookshelf, but one the the three has it as topic.

I suppose if any of the algorithms appearing in Knuth's book would
over the time not have been mentioned as well by other authors then
that algorithm might not have been worth to be mentioned? ;-)

Janis

> [...]

[toc] | [prev] | [next] | [standalone]

#402901

On Sat, 10 Oct 2026 19:36:53 -0000 (UTC)
cross@spitfire.i.gajendra.net (Dan Cross) wrote:

> In article <11ae0h8$cjlv$3@dont-email.me>,
> Janis Papanagnou  <janis_papanagnou+ng@hotmail.com> wrote:
> >On 2026-10-10 18:08, Michael S wrote:  
> >>> TAOCP  
> >> 
> >> It is still the best reference for *some* data structures and
> >> algorithms. Not necessarily something that is still practically
> >> important. In particular, I am thinking about external sortng.  
> >
> >Have you anything specific in mind beyond merge-sort?  
> 
> Radix sort?
> 

Is there a variant of radix sort usable for external sorting?
I don't recollect anything of this sort.

[toc] | [prev] | [next] | [standalone]

#402908

In article <20261010232112.000024ee@yahoo.com>,
Michael S  <already5chosen@yahoo.com> wrote:
>On Sat, 10 Oct 2026 19:36:53 -0000 (UTC)
>cross@spitfire.i.gajendra.net (Dan Cross) wrote:
>
>> In article <11ae0h8$cjlv$3@dont-email.me>,
>> Janis Papanagnou  <janis_papanagnou+ng@hotmail.com> wrote:
>> >On 2026-10-10 18:08, Michael S wrote:  
>> >>> TAOCP  
>> >> 
>> >> It is still the best reference for *some* data structures and
>> >> algorithms. Not necessarily something that is still practically
>> >> important. In particular, I am thinking about external sortng.  
>> >
>> >Have you anything specific in mind beyond merge-sort?  
>> 
>> Radix sort?
>
>Is there a variant of radix sort usable for external sorting?
>I don't recollect anything of this sort.

Section 5.4.7 is titled, "External Radix Sorting."

	- Dan C.

[toc] | [prev] | [next] | [standalone]

#402902

Michael S <already5chosen@yahoo.com> writes:
>On Fri, 9 Oct 2026 16:48:21 -0000 (UTC)
>cross@spitfire.i.gajendra.net (Dan Cross) wrote:
>
>> In article <20261009174739.00006700@yahoo.com>,
>> Michael S  <already5chosen@yahoo.com> wrote:
>> >On Fri, 9 Oct 2026 12:38:04 -0000 (UTC)
>> >cross@spitfire.i.gajendra.net (Dan Cross) wrote:  
>> >> Knuth is a wonderful object of study, but I do not recommend it.  

>
>> I do not
>> recommend it as an everyday reference for programmers, nor for
>> learning data structures and algorithms;
>
>It is still the best reference for *some* data structures and
>algorithms. Not necessarily something that is still practically
>important. In particular, I am thinking about external sortng.

Like 6-tape drive merge sorts?    Not a common use case in these
days...

[toc] | [prev] | [next] | [standalone]

#402904

On Sat, 10 Oct 2026 20:22:21 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

> Michael S <already5chosen@yahoo.com> writes:
> >On Fri, 9 Oct 2026 16:48:21 -0000 (UTC)
> >cross@spitfire.i.gajendra.net (Dan Cross) wrote:
> >  
> >> In article <20261009174739.00006700@yahoo.com>,
> >> Michael S  <already5chosen@yahoo.com> wrote:  
> >> >On Fri, 9 Oct 2026 12:38:04 -0000 (UTC)
> >> >cross@spitfire.i.gajendra.net (Dan Cross) wrote:    
> >> >> Knuth is a wonderful object of study, but I do not recommend
> >> >> it.    
> 
> >  
> >> I do not
> >> recommend it as an everyday reference for programmers, nor for
> >> learning data structures and algorithms;  
> >
> >It is still the best reference for *some* data structures and
> >algorithms. Not necessarily something that is still practically
> >important. In particular, I am thinking about external sortng.  
> 
> Like 6-tape drive merge sorts?    Not a common use case in these
> days...
> 

Sure. But algorithms are still fun.
I like chess problems, mostly of mate in 3 variaty. That sorting thing
is certainly no worse than some of them.
But I think that he discusses sorting on other forms of mass storage as
well. Not sure if any of specific algorithms would be applicable to
modern SSDs but the way he analyze them very likely still relevant.

[toc] | [prev] | [next] | [standalone]

#402884

AVL trees are cool. Nominally, a red-black tree is faster for insertions
and deletions—and in C++, `std::map` is almost always based on one—but
that is a theoretical advantage. In practice, because the search depth
of an AVL tree is up to half that of a red-black tree, you touch fewer
memory locations during a search, meaning less cache data needs to be
reloaded. The same applies to insertion and deletion operations.

[toc] | [prev] | [next] | [standalone]

#402894

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.

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?

-- 
Best regards,
Andrey

[toc] | [prev] | [next] | [standalone]

#402896

On Sat, 10 Oct 2026 12:39:09 -0700
Andrey Tarasevich <noone@noone.net> wrote:

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

I also did it relatively recently (2 or 3 years ago) and also in
specialized context (median filtering) so not sure how applicable my
solution would be here.
BTW, at the end AVL tree didn't ended up as my data structure of choice
for this particular application, but it did ended up as a solid
contender with the same BigO characteristics as a winner.

[toc] | [prev] | [next] | [standalone]

#402903

On 2026-10-10 21:39, Andrey Tarasevich wrote:
> [ AVL-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).

We don't need a parent-reference to delete an actual referenced node,
do we?

In my Algol 68 implementation I'm using a "REF REF NODE" type (let's
call that a pointer reference for better understanding) that makes it
possible to operate on a higher indirection level. (In C++ that might
be implemented with &*, and in "C" emulated with **, I'd suppose, and
in Pascal I had done that with a 'var' parameter on a pointer type;
I don't recall to have implemented that in "C" myself but I don't see
that it wouldn't be feasible.)

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

I recall I've done such a hack in the 1980's on an Atari where memory
was scarce to implement a 'tries' data structure.

Janis

[toc] | [prev] | [next] | [standalone]

#402935

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).

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.lang.c

csiph-web