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: Sat, 10 Oct 2026 19:02:29 -0700 Organization: A noiseless patient Spider Lines: 185 Message-ID: <86bj91j8p6.fsf@linuxsc.com> References: <86ece2kppv.fsf@linuxsc.com> <11ae48u$21bo6$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Sun, 11 Oct 2026 02:02:34 +0000 (UTC) Injection-Info: dont-email.me; logging-data="2383215"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+KPBkkbwrsi8cq/TNq5Ss7BcXd2LNlnOk="; posting-host="1098c1f1b6b0f5d684612506fbd55361" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:XyDTzgIQjJW7hqxx8YC2xcdLD58= sha1:9xKUYrLG8zFbkX0NQbscoSCOPYI= sha256:slCGyHq9WLCFJuPAlFQ3bT9YbvUERqEuKEyBwX053xg= sha1:6dFZEp2HFUjh47swzRN2hBbQ3gY= sha256:Wv3/3W/fwXZGPm/KDoM6j0pW7w+a0zdfnJwPsiJGtec= Xref: csiph.com comp.lang.c:402935 Andrey Tarasevich writes: > On Tue 10/6/2026 11:08 PM, Tim Rentsch wrote: > >> I offer this small programming exercise for anyone who is >> interested. > > I did exactly that a couple of months ago, except that my case the AVL > tree was intended to serve as a carrying sub-structure for an > augmented interval tree. I did not make any effort to decouple the > implementations, meaning that my AVL implementation is intermixed with > the interval tree implementation. > > Also, I had to support not only operations that start from the root of > the tree (like your `add_key`), but also operations that start from a > specific arbitrary node (e.q. a `delete_node(Node *)` operation). So, > in my case I opted to also keep and maintain the parent link in each > node. Extra memory expenditure is not that drastic, especially > considering the fact that my nodes are already heavier - carrying > geometric data for the interval tree. Right. Clearly your requirements were more extensive than those of my simple programming exercise. > Meanwhile, you seem to be striving to squeeze out all "unnecessary" > memory usage (re: embedding the balance value into the unused pointer > bits). Is this a hard requirement in your exercise? It might be useful to give some history as background for my comments, and for the exercise. More than a few years ago I was interested in using trees, of some as-yet-to-be-determined variety, as the basis for a (generic) set data type. One of the kinds of trees I looked into was AVL trees. Because I had a copy of Sorting and Searching handy, I pulled it off the shelf and read about AVL trees. To help my exploration, I took the Knuth description of AVL-tree insertion and transliterated it into C. Here is the result, more or less a direct expression of the AVL-insertion algorithm given in Sorting and Searching: #include #include typedef struct tree_node_s *Tree; typedef signed int Key; typedef signed int Balance; struct tree_node_s { Tree left, right; Key key; Balance b; }; void avl_insert( Tree head, Key k ){ Tree t, s, p, q, r; Balance a; A1: t = head, s = p = head->right; /* fall through */ A2: if( k < p->key ) goto A3; if( k > p->key ) goto A4; return; A3: q = p->left; if( !q ){ p->left = q = malloc( sizeof *q ); goto A5; } if( q->b != 0 ) t = p, s = q; p = q; goto A2; A4: q = p->right; if( !q ){ p->right = q = malloc( sizeof *q ); goto A5; } if( q->b != 0 ) t = p, s = q; p = q; goto A2; A5: q->left = q->right = 0, q->key = k, q->b = 0; /* fall through */ A6: if( k < s->key ) r = p = s->left; else r = p = s->right; while( p != q ){ if( k < p->key ) p->b = -1, p = p->left; else p->b = +1, p = p->right; } /* fall through */ A7: if( k < s->key ) a = -1; else a = +1; if( s->b == 0 ){ s->b = a; return; } if( s->b == -a ){ s->b = 0; return; } if( s->b == a ){ if( r->b == a ) goto A8; if( r->b == -a ) goto A9; assert( 0 ); } assert( 0 ); A8: p = r; if( a == 1 ) s->right = r->left, r->left = s; else s->left = r->right, r->right = s; s->b = r->b = 0; goto A10; A9: if( a == 1 ){ p = r->right; r->right = p->left, p->left = r; s->left = p->right, p->right = s; } else { p = r->left; r->left = p->right, p->right = r; s->right = p->left, p->left = s; } if( p->b == a ) s->b = -a, r->b = 0; if( p->b == 0 ) s->b = 0, r->b = 0; if( p->b == -a ) s->b = 0, r->b = -a; p->b = 0; /* fall through */ A10: if( s == t->right ) t->right = p; else t->left = p; } The code compiles but I can't say more than that. To the best of my recollection it was never actually run. Because I found the above "explanation" so unhelpful in trying to understand how AVL trees work, I wrote my own AVL-insertion code in C, using an interface similar to the one shown in my posting stating the exercise. (The earlier interface was slightly more elaborate because it allowed for "threading" of the binary tree, but I took that aspect out of the exercise problem.) In my revised version, it made sense to put the extra state "inside" the pointers, in order to distinguish a "true" link from a "thread" link in the tree traversal algorithms. In posting the exercise I took out the second extra bit (the bit saying this link is a thread link) but otherwise left it alone. In some ways I think having the "taller" bit be part of the links simplifies the algorithm slightly but I didn't really think about that when posting the exercise. There is an advantage (to me) to keep that interface, since I already have a test rig to drive it. There wasn't any sort of consideration about the nature of the exercise, just a pragmatic thought that if there were any testing to be done it would be easier to use the same interface. I posted the exercise because I thought some people might enjoy writing some C code, and because I was (and am) curious about how other people would implement AVL insertion in C. AVL trees are rather tricky to implement, and I wonder what other people would do to deal with that barrier. And since you have some experience (and also a good level of expertise) I hope you will take the time to write and post an answer. Incidentally, in my tree investigation of many years ago, the winner (judged by an unspecified metric) ended up being 2-3-4 trees. But that is a topic for another day (and most likely another newsgroup, since it wasn't written in C).