Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #402839
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: AVL tree insertion - programming exercise |
| Date | 2026-10-08 23:53 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <86jynrjrf3.fsf@linuxsc.com> (permalink) |
| References | (1 earlier) <11a5h8m$2t8e8$1@dont-email.me> <865wzdl3xz.fsf@linuxsc.com> <11a6qi4$3cv2b$1@dont-email.me> <86wlrsjqq9.fsf@linuxsc.com> <11a8ta9$6463$1@dont-email.me> |
BGB <cr88192@gmail.com> writes:
> 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 should add, nothing negative intended. Some of the best
developers I have met were dyslexic.
>> 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.
>
> [...]
My intention was that people keep the interface I gave, including
the definition of the Node struct.
>> 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. [...]
I encourage you to read the description in Knuth TAOCP.
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 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