Re: AVL tree insertion - programming exercise

From	BGB <cr88192@gmail.com>
Newsgroups	comp.lang.c
Subject	Re: AVL tree insertion - programming exercise
Date	2026-10-07 20:10 -0500
Organization	A noiseless patient Spider
Message-ID	<11a6qi4$3cv2b$1@dont-email.me> (permalink)
References	<86ece2kppv.fsf@linuxsc.com> <11a5h8m$2t8e8$1@dont-email.me> <865wzdl3xz.fsf@linuxsc.com>

Show all headers | View raw

On 10/7/2026 2:13 PM, Tim Rentsch wrote:
> fir <profesor.fir@gmail.com> 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 <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.
>>
>> 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):

typedef struct AVL_Node_s AVL_Node;

struct AVL_Node_s {
   AVLNode *ln;
   AVLNode *rn;
   int key;
   char depth;
};

AVL_Node *AVL_AllocNode()
{
   AVL_Node *tmp;
   tmp=malloc(sizeof(AVL_Node));
   memset(tmp, 0, sizeof(AVL_Node));
   return(tmp);
}

int AVL_GetDepth(AVL_Node *n)
   { return(n?n->depth:(-1)); }

int AVL_RecalcDepth(AVL_Node *n)
{
   int dl, dr, d;
   if(!n)return(-1);
   dl=AVL_GetDepth(n->nl);
   dr=AVL_GetDepth(n->nr);
   d=max(dl, dr)+1;
   n->depth=d;
   return(d);
}

void AVL_AddKeyR(AVL_Node **rnr, int key)
{
   AVL_Node *n, *ln, *rn;
   int dl, dr;

   n=*rnr;
   if(!n)
   {
     n=AVL_AllocNode();
     n->key=key;
     *rnr=n;
     return;
   }
   if(n->key==key)
     return;
   if(key<n->key)
     AVL_AddKeyR(&n->ln, key);
   else
     AVL_AddKeyR(&n->rn, key);

   ln=n->ln;
   rn=n->rn;
   dl=AVL_GetDepth(ln);
   dr=AVL_GetDepth(rn);
   if(dl>(dr+1))
   {
     /* rotate tree */
     n->ln=ln->rn;
     ln->rn=n;
     AVL_RecalcDepth(n);
     AVL_RecalcDepth(ln);
     *rnr=ln;
     return;
   }
   if(dr>(dl+1))
   {
     /* rotate tree */
     n->rn=rn->ln;
     rn->ln=n;
     AVL_RecalcDepth(n);
     AVL_RecalcDepth(rn);
     *rnr=rn;
     return;
   }
   AVL_RecalcDepth(n);
}

Thread

AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 23:08 -0700
  Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 15:25 +0200
    Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-07 12:13 -0700
      Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-07 21:28 +0200
        Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:31 -0700
          Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
            Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 11:12 +0200
      Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-07 20:10 -0500
        Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 05:56 -0700
          Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 15:09 -0500
            Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-08 22:56 +0200
              Re: AVL tree insertion - programming exercise BGB <cr88192@gmail.com> - 2026-10-08 17:29 -0500
                Re: AVL tree insertion - programming exercise fir <profesor.fir@gmail.com> - 2026-10-09 09:56 +0200
            Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 01:39 +0200
              Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-09 00:03 -0700
            Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-08 23:53 -0700
              Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 10:34 +0200
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 12:27 +0200
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 12:59 +0200
                Re: AVL tree insertion - programming exercise bart <bc@freeuk.com> - 2026-10-09 11:43 +0100
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 13:20 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 12:38 +0000
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-09 16:05 +0200
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-09 17:54 +0200
                Re: AVL tree insertion - programming exercise Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-10-10 10:38 +0800
                Re: AVL tree insertion - programming exercise ram@zedat.fu-berlin.de (Stefan Ram) - 2026-10-10 03:12 +0000
                Re: AVL tree insertion - programming exercise Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-10 04:44 +0000
                Re: AVL tree insertion - programming exercise "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-10 14:12 -0700
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 19:48 +0000
                Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-09 23:18 +0000
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 15:27 +0200
                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-09 17:47 +0300
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 16:48 +0000
                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 19:08 +0300
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 18:29 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:44 +0000
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-10 23:22 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:43 +0000
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 20:35 +0200
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 19:36 +0000
                Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:08 +0200
                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:21 +0300
                Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 20:55 +0000
                Re: AVL tree insertion - programming exercise scott@slp53.sl.home (Scott Lurndal) - 2026-10-10 20:22 +0000
                Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:32 +0300
  Re: AVL tree insertion - programming exercise Bonita Montero <Bonita.Montero@gmail.com> - 2026-10-10 19:40 +0200
  Re: AVL tree insertion - programming exercise Andrey Tarasevich <noone@noone.net> - 2026-10-10 12:39 -0700
    Re: AVL tree insertion - programming exercise Michael S <already5chosen@yahoo.com> - 2026-10-10 23:00 +0300
    Re: AVL tree insertion - programming exercise Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-10 22:28 +0200
    Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-10 19:02 -0700

csiph-web