Re: AVL tree insertion - programming exercise

From	BGB <cr88192@gmail.com>
Newsgroups	comp.lang.c
Subject	Re: AVL tree insertion - programming exercise
Date	2026-10-08 15:09 -0500
Organization	A noiseless patient Spider
Message-ID	<11a8ta9$6463$1@dont-email.me> (permalink)
References	<86ece2kppv.fsf@linuxsc.com> <11a5h8m$2t8e8$1@dont-email.me> <865wzdl3xz.fsf@linuxsc.com> <11a6qi4$3cv2b$1@dont-email.me> <86wlrsjqq9.fsf@linuxsc.com>

Show all headers | View raw

On 10/8/2026 7:56 AM, Tim Rentsch wrote:
> BGB <cr88192@gmail.com> writes:
> 
>> On 10/7/2026 2:13 PM, Tim Rentsch wrote:
>>
>>> fir <profesor.fir@gmail.com> writes:
>>>
>>>> Tim Rentsch pisze:
>>>>
>>>>> I offer this small programming exercise for anyone who is
>>>>> interested.
>>>>>
>>>>> Write a function to insert a value into an AVL tree.  Here
>>>>> is an outline of the basic data structure involved:
>>>>>
>>>>>        #include <stdint.h>
>>>>>
>>>>>        typedef uintptr_t Link;
>>>>>        typedef signed int Key;
>>>>>
>>>>>        typedef struct {
>>>>>            Link sons[2];
>>>>>            Key  key;
>>>>>        } Node;
>>>>>
>>>>>        static Node *
>>>>>        as_tree( Link link ){
>>>>>            return  (Node*)(link & ~(0?link:1));
>>>>>        }
>>>>>
>>>>>        static _Bool
>>>>>        is_tall( Link link ){
>>>>>            return  link & 1;
>>>>>        }
>>>>>
>>>>> A Node is an element in the tree, with two child pointers, the
>>>>> sons[2] array.  These links are basically pointers, but held
>>>>> as uintptr_t so they can take one of the bits to mean "tall",
>>>>> which means taller than the other subtree of the node.  The
>>>>> tree structure should maintain an invariant that at most one
>>>>> of the two sons of each node is "tall", and if set then the
>>>>> height of that subtree is one larger than the height of the
>>>>> other subtree.  Of course if both subtrees are the same height
>>>>> then neither should be labeled as tall.
>>>>>
>>>>> What we're looking for is a function to add a key to an existing
>>>>> tree (possibly empty), which is held as a Node *.  Example:
>>>>>
>>>>>        Node *root = 0;
>>>>>
>>>>>        add_key( &root, 1 );
>>>>>        add_key( &root, 2 );
>>>>>        add_key( &root, 3 );
>>>>>        add_key( &root, 4 );
>>>>>        add_key( &root, 5 );
>>>>>
>>>>> should leave root as a reference to a tree with five values.
>>>>>
>>>>> Thus the exercise is to define the function
>>>>>
>>>>>        void add_key( Node **, Key );
>>>>>
>>>>> to add values to the AVL tree held in what the first argument
>>>>> points to.
>>>>
>>>> im not interested in this personally but you may take my ai answer
>>>> if you want [...]
>>>
>>> My interest here is to see how people would write the code.  I
>>> know how to program an AVL tree and don't have any particular
>>> interest in looking at AI-generated code.  But thank you for the
>>> effort.
>>
>> I guess I will weigh in, in something closer to my style, while mostly
>> following the original pattern (untested):
>>
>> [.. code follows ..]
> 
> A few comments.
> 
> The posted code has a few typos.  They were easy to fix.
> 
> Related to that, if you have some dyslexia, you might want to use
> longer names for variables and members.
> 

I don't really think I have dyslexia that I am aware of.

I do have ASD though (what was once called Asperger's, now apparently 
classified as "level 2 autism"; where "level 1" is mostly the ones that 
actually have life-skills and can mostly pass for "normal", *1).

I also do have an issue of "small fonts at 100% zoom on a 4K monitor" 
means at times I fail to see or notice typos as easily (but then 200% UI 
scaling defeats the point of having a 4K monitor, and 125% or 150% 
causes many programs to look like blurry crap).

So, turning it all into a little bit of a dilemma sometimes.

Some other various sensory issues, but none that relate to typos.

This area is sort of an odd grab bag.

My personal list of oddities that I have noticed is probably not 
something I will go into at the moment (and can turn into some whole 
"nature of the experience as my existence as myself" kind of thing).

*1:

Well, and also some form of affective alexithymia, but this doesn't 
really effect coding skills. Not great for social stuff though, and I 
have gotten a non-zero number of "Mr. Spock" jokes and similar over the 
years; as apparently my way of speaking and self-presentation do come 
off kinda like the Vulcans from Star Trek, but with a combination of 
both ASD associated vocal inflection patterns but also a tendency to 
speak in monotone, which isn't always beneficial for social 
interactions; and seems to frequently lead to avoidance.

Well, it seems to vary (sometimes "Mr. Spock", sometimes "Sheldon").

There are some worse labels people could try to apply, but at least from 
my own looking into them, they would seem not to apply. Some ironically 
in the category of: If one feels worried that they could apply, they 
don't apply (because in the minds of the people with these defects, they 
would not perceive them as being defects). None the less one can still 
worry at times about how they are perceived by others. But, at the same 
times, sometimes caution, hostility, or avoidance are the most rational 
options from the others' perspective, so they can't be held at fault as 
such (and trying to convince them otherwise would be what would be 
expected of those for whom such labels would apply; as such leaving the 
only valid option as accepting their hostility or avoidance as an 
inevitability).

...

> What you are calling "depth" in your code is customarily called
> "height".  The height of a (sub-)tree is the length of the longest
> path from the root of the sub-tree to a leaf.  For a node in a tree,
> the depth of the node is the length of the path from the root of the
> tree to that node.  So height measures "down" whereas depth measures
> "up".
> 
> I have run some test cases and the code looks like it produces trees
> that are well-structured.  I didn't do any tests to check for
> whether the trees produced are balanced.
> 

OK.

As can be noted, I typed it out directly in the post, no testing 
involved here.

Didn't notice some of the typos until after I posted it.

> Unfortunately what the code is doing is not an AVL tree.  AVL trees
> have the property that they store only two extra bits per node, not
> a full height.  Furthermore after an insertion the bits don't need
> to be recalculated by walking the tree - new values are determined
> based on local information rather than a tree walk calculation.
> 

I usually stored the depth/height because it was cheaper than fully 
recalculating it using a tree walk, and it makes it cheaper to run the 
rebalance logic by caching it.

But, this is what I remembered an AVL tree as being, so this is what I 
went with here.

I had understood it as being more about them being a balanced binary 
tree with the goal of maintaining a +/- 1 balance for the left and right 
sub-trees (as opposed to, say, an unbalanced binary tree).

The tag bit or "node coloring" approach was (I thought) a different type 
of tree (like a red/black tree).

> I learned about AVL trees from The Art of Computer Proggramming, by
> Knuth.  I'm sure there are other explanations available but I don't
> have any other pointers to give you.

I read about them at some point when I was younger, and used them 
occasionally.

Often their use-cases compete with B-Trees and hash-tables, which I more 
often use.

For better or worse I did use a similar tree structure for the 
directories in one of my filesystem designs:
   Allows faster lookup than linear search;
   Has lower constant overhead and scales better than hash chaining;
   Can give directory entries (mostly) in sorted order;
   Less overkill than B-Trees in this case (*1).

*1: Using B-Trees for directories doesn't really beat a binary tree 
until the directory is unreasonably large, and in this case the relative 
space overhead of the tree structure was modest if compared with the 
filename field and inode number.

Though, the FS in question only stored 48 bytes (UTF-8) per dirent 
directly, and would switch to multi-part dirents (like VFAT) for longer 
names. Personally I felt this less bad than either overly large 
fixed-size dirents, or the variable-length dirents approach that EXTn used.

Though, after implementing it, I was left to debate whether the 
complexity was worthwhile and whether I should have just gone with 
linear search instead, but alas...

For the directories though, did relax the balancing to +/- 2, as I noted 
that this would significantly reduce the number of node rotations during 
insertions or deletions with only a minor effect on overall balance.

In this case, the code for dealing with adding or removing directory 
entries became one of the more complicated parts of the filesystem.

Otherwise, it was a design sorta like a hybrid of EXT2 and NTFS, aiming 
more for simplicity (rather then the excessive complexity and 
over-engineering of NTFS).

...

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 scott@slp53.sl.home (Scott Lurndal) - 2026-10-11 15:24 +0000
  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