Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: AVL tree insertion - programming exercise Date: Thu, 08 Oct 2026 05:56:14 -0700 Organization: A noiseless patient Spider Lines: 104 Message-ID: <86wlrsjqq9.fsf@linuxsc.com> References: <86ece2kppv.fsf@linuxsc.com> <11a5h8m$2t8e8$1@dont-email.me> <865wzdl3xz.fsf@linuxsc.com> <11a6qi4$3cv2b$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Thu, 08 Oct 2026 12:56:18 +0000 (UTC) Injection-Info: dont-email.me; logging-data="4015457"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/FpTnEsxzYAB0f9zajhoQllAX19zj5UwQ="; posting-host="4cee8a76f88b3dc47378f6a457cfe5d4" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:33dY+C/W1+uGpsKhc9CFKqoNoW4= sha1:zOrKVha6h2cl2wilmTjkonFJFzo= sha256:bPqMOjjaqc+p6+FjPfYtV4PvKrB7D1mQSGaGb+5GpPk= sha1:yWin9kGnz5lOiTg6XzgTXdTI/X4= sha256:QzUoj+svyJBXRb1WVkM7qQb+s1U/Gu65R9902ls9mA4= Xref: csiph.com comp.lang.c:402829 BGB writes: > On 10/7/2026 2:13 PM, Tim Rentsch wrote: > >> fir 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 >>>> >>>> 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.