Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #402829
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: AVL tree insertion - programming exercise |
| Date | 2026-10-08 05:56 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <86wlrsjqq9.fsf@linuxsc.com> (permalink) |
| References | <86ece2kppv.fsf@linuxsc.com> <11a5h8m$2t8e8$1@dont-email.me> <865wzdl3xz.fsf@linuxsc.com> <11a6qi4$3cv2b$1@dont-email.me> |
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.
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.
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 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.
Back to comp.lang.c | Previous | Next — Previous in thread | Next 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