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 23:53:36 -0700 Organization: A noiseless patient Spider Lines: 119 Message-ID: <86jynrjrf3.fsf@linuxsc.com> 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> <11a8ta9$6463$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Fri, 09 Oct 2026 06:53:37 +0000 (UTC) Injection-Info: dont-email.me; logging-data="576466"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19FIVEp9irwJF5Ef4SnGlftYg2SlNE9tRg="; posting-host="5a0c7299f9ebed440838fd418bbcee35" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:sSIyRz2b1rYTpYbGdzc9c3NLtyI= sha1:sBTxj481JDbLfbnUgeXza+LrOhE= sha256:Fz6K0mWm/+faVCwXgVRGOnF2j6+RhZeHgAGeTdsJXzU= sha1:wZy8rHsLIwLD2NrL2G7XIr4jTrc= sha256:uX6RUtG0vgxlWMKxSpDYeFejaowHT4jbjFUXv/a4a08= Xref: csiph.com comp.lang.c:402839 BGB writes: > On 10/8/2026 7:56 AM, Tim Rentsch wrote: > >> 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. > > 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.