Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: AVL tree insertion - programming exercise
Date: Tue, 06 Oct 2026 23:08:12 -0700
Organization: A noiseless patient Spider
Lines: 55
Message-ID: <86ece2kppv.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Wed, 07 Oct 2026 06:08:14 +0000 (UTC)
Injection-Info: dont-email.me; logging-data="2740258"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1//lLn+ijGyPalHiKZwtiVJ0NrSgv7Afus="; posting-host="f116a0ff36505fb6c1fca8f439768e04"
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:k+TFpKI7DgusFFGq9r7Io9nLxNI= sha1:RWUauh4nFbelxEQqCvyz2MiGcUI= sha256:0ruUPFCrFPSgluzNXs6iojQb6PIKlirs2RmZ2yVn3MU= sha1:jkFr+5Tgh+ro2WbPnA3UO/eS8/I= sha256:C6LMPayNuMsMiNCeHU82QiCcoO/rZ+MeTfT20xY93JA=
Xref: csiph.com comp.lang.c:402780

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.