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: Re: AVL tree insertion - programming exercise
Date: Tue, 13 Oct 2026 03:52:15 -0700
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <86bj8xj2jk.fsf@linuxsc.com>
References: <86ece2kppv.fsf@linuxsc.com> <11akqm4$c6h9$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Tue, 13 Oct 2026 10:52:16 +0000 (UTC)
Injection-Info: dont-email.me; logging-data="463729"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18lCNHfc20ZTU43wdTH2lJk/NzVRrf2lU0="; posting-host="065d2eee2cd7241f5f1e4f229d8fc207"
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:XFygAo+4OP/3DjMvLWLc8mBEvB8= sha1:boZkqwpv2Qzgykgt2gSPWbzii+M= sha256:DvmSe6K2vFKsFg7jPUWNMbtNDoYiWNr6UgqAl9De4PA= sha1:NFYxDDaNHxGEbUKyFYtY8+frUfQ= sha256:FnbUmdpMH1lCBOa9v610pRYgfjfkp3k2ow+/PPUzkp0=
Xref: csiph.com comp.lang.c:403092

"chine.bleu" <chine.bleu@yahoo.com> writes:

> Tim Rentsch wrote:
>
>> 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
>
> Memory is cheap.  Do not encode tags into low bits of an address unless
> you really know what your doing.  As a precaution check the return
> address of malloc
>
>     p = malloc(m);
>     if ((uintptr_t)p)&1!=0) abort();

Yes, in general the interface described will fall down on some
systems.  But it's just an exercise.  Feel free to use code along
the lines of the following (disclaimer: not tested) to confirm
the suitability of the pointer values being used:

    Node *
    new_node( int key ){
        Node *r = malloc( sizeof *r );
        assert(  (uintptr_t)r %2 ==0  );
        *r = (Node){ .key = key };
        return  r;
    }