Groups > comp.lang.c > #402780 > unrolled thread

AVL tree insertion - programming exercise

Started by	Tim Rentsch <tr.17687@z991.linuxsc.com>
First post	2026-10-06 23:08 -0700
Last post	2026-10-10 19:02 -0700
Articles	20 on this page of 50 — 15 participants

Back to article view | Back to comp.lang.c

  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

Page 1 of 3 [1] 2 3 Next page →

#402780 — AVL tree insertion - programming exercise

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-10-06 23:08 -0700
Subject	AVL tree insertion - programming exercise
Message-ID	<86ece2kppv.fsf@linuxsc.com>

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.

[toc] | [next] | [standalone]

#402799

From	fir <profesor.fir@gmail.com>
Date	2026-10-07 15:25 +0200
Message-ID	<11a5h8m$2t8e8$1@dont-email.me>
In reply to	#402780

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

#include <stdint.h>
#include <stdlib.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 & ~(uintptr_t)1);
}

static int is_tall(Link link)
{
	return (int)(link & 1);
}

static Link make_link(Node *p,int tall)
{
	return (Link)p | (Link)tall;
}

/*
	balance:
	-1 = left subtree is taller
	 0 = equal
	+1 = right subtree is taller
*/
static int balance(Node *n)
{
	if(is_tall((*n).sons[0])) return -1;
	if(is_tall((*n).sons[1])) return 1;
	return 0;
}

static void set_balance(Node *n,int b)
{
	(*n).sons[0]&=~(Link)1;
	(*n).sons[1]&=~(Link)1;

	if(b<0)
		(*n).sons[0]|=1;
	else if(b>0)
		(*n).sons[1]|=1;
}

/* right rotation

	      x                 y
	     / \               / \
	    y   d     ->      a   x
	   / \                   / \
	  a   c                 c   d
*/
static Node *rotate_right(Node *x)
{
	Node *y=as_tree((*x).sons[0]);
	Node *c=as_tree((*y).sons[1]);

	(*x).sons[0]=make_link(c,0);
	(*y).sons[1]=make_link(x,0);

	set_balance(x,0);
	set_balance(y,0);

	return y;
}

/* left rotation

	    x                     y
	   / \                   / \
	  a   y       ->        x   d
	     / \               / \
	    c   d             a   c
*/
static Node *rotate_left(Node *x)
{
	Node *y=as_tree((*x).sons[1]);
	Node *c=as_tree((*y).sons[0]);

	(*x).sons[1]=make_link(c,0);
	(*y).sons[0]=make_link(x,0);

	set_balance(x,0);
	set_balance(y,0);

	return y;
}

/*
	Left-right rotation.

	      x                 z
	     / \               / \
	    y   d     ->      y   x
	   / \               / \ / \
	  a   z             a  b c  d
	     / \
	    b   c
*/
static Node *rotate_left_right(Node *x)
{
	Node *y=as_tree((*x).sons[0]);
	Node *z=as_tree((*y).sons[1]);
	Node *b=as_tree((*z).sons[0]);
	Node *c=as_tree((*z).sons[1]);

	int bz=balance(z);

	(*y).sons[1]=make_link(b,0);
	(*x).sons[0]=make_link(c,0);

	(*z).sons[0]=make_link(y,0);
	(*z).sons[1]=make_link(x,0);

	set_balance(y,bz==1 ? -1 : 0);
	set_balance(x,bz==-1 ? 1 : 0);
	set_balance(z,0);

	return z;
}

/*
	Right-left rotation.

	    x                     z
	   / \                   / \
	  a   y       ->        x   y
	     / \               / \ / \
	    z   d             a  b c  d
	   / \
	  b   c
*/
static Node *rotate_right_left(Node *x)
{
	Node *y=as_tree((*x).sons[1]);
	Node *z=as_tree((*y).sons[0]);
	Node *b=as_tree((*z).sons[0]);
	Node *c=as_tree((*z).sons[1]);

	int bz=balance(z);

	(*y).sons[0]=make_link(c,0);
	(*x).sons[1]=make_link(b,0);

	(*z).sons[0]=make_link(x,0);
	(*z).sons[1]=make_link(y,0);

	set_balance(x,bz==1 ? -1 : 0);
	set_balance(y,bz==-1 ? 1 : 0);
	set_balance(z,0);

	return z;
}

static Node *insert_node(Node *n,Key key,int *grew)
{
	if(!n)
	{
		n=(Node*)calloc(1,sizeof(Node));
		(*n).key=key;
		*grew=1;
		return n;
	}

	int d;

	if(key<(*n).key)
		d=0;
	else if(key>(*n).key)
		d=1;
	else
	{
		*grew=0;
		return n;
	}

	Node *child=as_tree((*n).sons[d]);

	child=insert_node(child,key,grew);

	if(!*grew)
		return n;

	(*n).sons[d]=make_link(child,is_tall((*n).sons[d]));

	int b=balance(n);

	if(d==0)
		b--;
	else
		b++;

	if(b==0)
	{
		set_balance(n,0);
		*grew=0;
		return n;
	}

	if(b==-1 || b==1)
	{
		set_balance(n,b);
		*grew=1;
		return n;
	}

	/* left heavy */
	if(b==-2)
	{
		Node *y=as_tree((*n).sons[0]);

		if(balance(y)<=0)
		{
			*grew=0;
			return rotate_right(n);
		}

		*grew=0;
		return rotate_left_right(n);
	}

	/* right heavy */
	if(b==2)
	{
		Node *y=as_tree((*n).sons[1]);

		if(balance(y)>=0)
		{
			*grew=0;
			return rotate_left(n);
		}

		*grew=0;
		return rotate_right_left(n);
	}

	return n;
}

void add_key(Node **root,Key key)
{
	int grew=0;

	*root=insert_node(*root,key,&grew);
}

ai also adds:

With:

Node *root=0;

add_key(&root,1);
add_key(&root,2);
add_key(&root,3);
add_key(&root,4);
add_key(&root,5);

you will get a properly balanced AVL tree.

One important thing: using bit 1 in Link assumes that malloc/calloc 
returns addresses aligned to at least 2 bytes, which is safe on normal 
platforms. as_tree() clears this bit before using the pointer.

[toc] | [prev] | [next] | [standalone]

#402805

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-10-07 12:13 -0700
Message-ID	<865wzdl3xz.fsf@linuxsc.com>
In reply to	#402799

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.

[toc] | [prev] | [next] | [standalone]

#402806

From	fir <profesor.fir@gmail.com>
Date	2026-10-07 21:28 +0200
Message-ID	<11a66hg$35t55$1@dont-email.me>
In reply to	#402805

Tim Rentsch pisze:
> 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.
> 

well i answered for two reasons...

1) this grooup is to small and there are not many people who want do 
some engaging task in small group of people  (this not stops me to 
posting, but just becouse if im focused on topic i often had something 
to say)

2) ai is tremendously good thig epecially in programing also in c 
programming and i find it good to encourage people to use it - as i 
suspect some could still not use it and not fully realize how its great

for stright answer i got no time..

[toc] | [prev] | [next] | [standalone]

#402828

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-10-08 05:31 -0700
Message-ID	<861pa0l6f6.fsf@linuxsc.com>
In reply to	#402806

fir <profesor.fir@gmail.com> writes:

> Tim Rentsch pisze:
[...]
>> 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.
>
> well i answered for two reasons...
>
> [...]

I appreciate you making an effort to contribute.  Unfortunately
any AI-generated code doesn't help with discussion I was hoping
to see.

[toc] | [prev] | [next] | [standalone]

#402844

From	fir <profesor.fir@gmail.com>
Date	2026-10-09 11:12 +0200
Message-ID	<11aab54$kreu$1@dont-email.me>
In reply to	#402828

Tim Rentsch pisze:
> fir <profesor.fir@gmail.com> writes:
> 
>> Tim Rentsch pisze:
> [...]
>>> 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.
>>
>> well i answered for two reasons...
>>
>> [...]
> 
> I appreciate you making an effort to contribute.  Unfortunately
> any AI-generated code doesn't help with discussion I was hoping
> to see.
> 

i was never using any of "trees" of such kind - so i cant answer, never 
yet seen any usage of it

[toc] | [prev] | [next] | [standalone]

#402845

From	fir <profesor.fir@gmail.com>
Date	2026-10-09 11:12 +0200
Message-ID	<11aab6k$kreu$2@dont-email.me>
In reply to	#402844

fir pisze:
> Tim Rentsch pisze:
>> fir <profesor.fir@gmail.com> writes:
>>
>>> Tim Rentsch pisze:
>> [...]
>>>> 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.
>>>
>>> well i answered for two reasons...
>>>
>>> [...]
>>
>> I appreciate you making an effort to contribute.  Unfortunately
>> any AI-generated code doesn't help with discussion I was hoping
>> to see.
>>
> 
> i was never using any of "trees" of such kind - so i cant answer, never 
> yet seen any usage of it
> 
its also not practical to me to learn something other than what im just 
doing or at least close

[toc] | [prev] | [next] | [standalone]

#402822

From	BGB <cr88192@gmail.com>
Date	2026-10-07 20:10 -0500
Message-ID	<11a6qi4$3cv2b$1@dont-email.me>
In reply to	#402805

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);
}

[toc] | [prev] | [next] | [standalone]

#402829

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-10-08 05:56 -0700
Message-ID	<86wlrsjqq9.fsf@linuxsc.com>
In reply to	#402822

BGB <cr88192@gmail.com> writes:

> 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):
>
> [.. 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.

What you are calling "depth" in your code is customarily called
"height".  The height of a (sub-)tree is the length of the longest
path from the root of the sub-tree to a leaf.  For a node in a tree,
the depth of the node is the length of the path from the root of the
tree to that node.  So height measures "down" whereas depth measures
"up".

I have run some test cases and the code looks like it produces trees
that are well-structured.  I didn't do any tests to check for
whether the trees produced are balanced.

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 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.

[toc] | [prev] | [next] | [standalone]

#402833

From	BGB <cr88192@gmail.com>
Date	2026-10-08 15:09 -0500
Message-ID	<11a8ta9$6463$1@dont-email.me>
In reply to	#402829

On 10/8/2026 7:56 AM, Tim Rentsch wrote:
> BGB <cr88192@gmail.com> writes:
> 
>> 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):
>>
>> [.. 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 do have ASD though (what was once called Asperger's, now apparently 
classified as "level 2 autism"; where "level 1" is mostly the ones that 
actually have life-skills and can mostly pass for "normal", *1).

I also do have an issue of "small fonts at 100% zoom on a 4K monitor" 
means at times I fail to see or notice typos as easily (but then 200% UI 
scaling defeats the point of having a 4K monitor, and 125% or 150% 
causes many programs to look like blurry crap).

So, turning it all into a little bit of a dilemma sometimes.

Some other various sensory issues, but none that relate to typos.

This area is sort of an odd grab bag.

My personal list of oddities that I have noticed is probably not 
something I will go into at the moment (and can turn into some whole 
"nature of the experience as my existence as myself" kind of thing).

*1:

Well, and also some form of affective alexithymia, but this doesn't 
really effect coding skills. Not great for social stuff though, and I 
have gotten a non-zero number of "Mr. Spock" jokes and similar over the 
years; as apparently my way of speaking and self-presentation do come 
off kinda like the Vulcans from Star Trek, but with a combination of 
both ASD associated vocal inflection patterns but also a tendency to 
speak in monotone, which isn't always beneficial for social 
interactions; and seems to frequently lead to avoidance.

Well, it seems to vary (sometimes "Mr. Spock", sometimes "Sheldon").

There are some worse labels people could try to apply, but at least from 
my own looking into them, they would seem not to apply. Some ironically 
in the category of: If one feels worried that they could apply, they 
don't apply (because in the minds of the people with these defects, they 
would not perceive them as being defects). None the less one can still 
worry at times about how they are perceived by others. But, at the same 
times, sometimes caution, hostility, or avoidance are the most rational 
options from the others' perspective, so they can't be held at fault as 
such (and trying to convince them otherwise would be what would be 
expected of those for whom such labels would apply; as such leaving the 
only valid option as accepting their hostility or avoidance as an 
inevitability).

...

> What you are calling "depth" in your code is customarily called
> "height".  The height of a (sub-)tree is the length of the longest
> path from the root of the sub-tree to a leaf.  For a node in a tree,
> the depth of the node is the length of the path from the root of the
> tree to that node.  So height measures "down" whereas depth measures
> "up".
> 
> I have run some test cases and the code looks like it produces trees
> that are well-structured.  I didn't do any tests to check for
> whether the trees produced are balanced.
> 

OK.

As can be noted, I typed it out directly in the post, no testing 
involved here.

Didn't notice some of the typos until after I posted it.

> 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.

I had understood it as being more about them being a balanced binary 
tree with the goal of maintaining a +/- 1 balance for the left and right 
sub-trees (as opposed to, say, an unbalanced binary tree).

The tag bit or "node coloring" approach was (I thought) a different type 
of tree (like a red/black tree).

> 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.

Often their use-cases compete with B-Trees and hash-tables, which I more 
often use.

For better or worse I did use a similar tree structure for the 
directories in one of my filesystem designs:
   Allows faster lookup than linear search;
   Has lower constant overhead and scales better than hash chaining;
   Can give directory entries (mostly) in sorted order;
   Less overkill than B-Trees in this case (*1).

*1: Using B-Trees for directories doesn't really beat a binary tree 
until the directory is unreasonably large, and in this case the relative 
space overhead of the tree structure was modest if compared with the 
filename field and inode number.

Though, the FS in question only stored 48 bytes (UTF-8) per dirent 
directly, and would switch to multi-part dirents (like VFAT) for longer 
names. Personally I felt this less bad than either overly large 
fixed-size dirents, or the variable-length dirents approach that EXTn used.

Though, after implementing it, I was left to debate whether the 
complexity was worthwhile and whether I should have just gone with 
linear search instead, but alas...

For the directories though, did relax the balancing to +/- 2, as I noted 
that this would significantly reduce the number of node rotations during 
insertions or deletions with only a minor effect on overall balance.

In this case, the code for dealing with adding or removing directory 
entries became one of the more complicated parts of the filesystem.

Otherwise, it was a design sorta like a hybrid of EXT2 and NTFS, aiming 
more for simplicity (rather then the excessive complexity and 
over-engineering of NTFS).

...

[toc] | [prev] | [next] | [standalone]

#402834

From	fir <profesor.fir@gmail.com>
Date	2026-10-08 22:56 +0200
Message-ID	<11a9025$75ql$1@dont-email.me>
In reply to	#402833

BGB pisze:
> 
> I also do have an issue of "small fonts at 100% zoom on a 4K monitor" 
> means at times I fail to see or notice typos as easily (but then 200% UI 
> scaling defeats the point of having a 4K monitor, and 125% or 150% 
> causes many programs to look like blurry crap)


its maybe kinda curious but if someone starts winapi app and not call
SetProcessDPIAware then the program is like being tricked he works in 
lower resolution he really is

(i not readed into it into details but i may somewhat guess thet the
resolution he is tricked depends of windows scaling - the more scaling 
you get the more program is tricked he work in lower resolution)

calling this dpi aware makes app is not tricked and reckognizes real 
resolution

[toc] | [prev] | [next] | [standalone]

#402837

From	BGB <cr88192@gmail.com>
Date	2026-10-08 17:29 -0500
Message-ID	<11a95gb$912u$1@dont-email.me>
In reply to	#402834

On 10/8/2026 3:56 PM, fir wrote:
> BGB pisze:
>>
>> I also do have an issue of "small fonts at 100% zoom on a 4K monitor" 
>> means at times I fail to see or notice typos as easily (but then 200% 
>> UI scaling defeats the point of having a 4K monitor, and 125% or 150% 
>> causes many programs to look like blurry crap)
> 
> 
> its maybe kinda curious but if someone starts winapi app and not call
> SetProcessDPIAware then the program is like being tricked he works in 
> lower resolution he really is
> 
> (i not readed into it into details but i may somewhat guess thet the
> resolution he is tricked depends of windows scaling - the more scaling 
> you get the more program is tricked he work in lower resolution)
> 
> calling this dpi aware makes app is not tricked and reckognizes real 
> resolution

Dunno...

A lot of times, native Windows programs deal better with UI zoom.

But stuff that uses GTK or similar, or renders UI via raw bitmaps, or 
that goes through an X11 translation layer, tends to look pretty much 
awful when UI zoom is used.

But, I mostly end up accepting the comparably small text of default font 
sizes on a 4K monitor, even if at times it seems like my eyesight is not 
good enough to reliably see typos (particularly those involving similar 
looking characters).

Checking:
The tip of my index finger on my monitor covers roughly 5 lines of text.

Measures my finder, roughly 0.570 inches, so around 0.114" per line of 
text, read from a distance a little longer than the length of my arm.

Checking:
Length of arm: 28 inches;
Distance from head to monitor, roughly 36 inches.

Not sure the font Thunderbird uses, but it is slightly smaller and more 
difficult to read than the 9pt Fixedsys I am using in my text editor 
(but alas, Windows programs don't just let you use Fixedsys for 
everything, they seemingly want to use thin line and narrow variable 
width fonts for pretty much everything, and will then reset settings to 
defaults whenever the next time they update if you try to change these 
settings).

...

OTOH:
I realized after posting that my mention of issues with alexithymia and 
social difficulties was probably a little much for the topic at hand 
(too serious of a tone). It is hard sometimes to maintain a good balance 
in these areas.

...

[toc] | [prev] | [next] | [standalone]

#402841

From	fir <profesor.fir@gmail.com>
Date	2026-10-09 09:56 +0200
Message-ID	<11aa6np$j4va$1@dont-email.me>
In reply to	#402837

BGB pisze:
> On 10/8/2026 3:56 PM, fir wrote:
>> BGB pisze:
>>>
>>> I also do have an issue of "small fonts at 100% zoom on a 4K monitor" 
>>> means at times I fail to see or notice typos as easily (but then 200% 
>>> UI scaling defeats the point of having a 4K monitor, and 125% or 150% 
>>> causes many programs to look like blurry crap)
>>
>>
>> its maybe kinda curious but if someone starts winapi app and not call
>> SetProcessDPIAware then the program is like being tricked he works in 
>> lower resolution he really is
>>
>> (i not readed into it into details but i may somewhat guess thet the
>> resolution he is tricked depends of windows scaling - the more scaling 
>> you get the more program is tricked he work in lower resolution)
>>
>> calling this dpi aware makes app is not tricked and reckognizes real 
>> resolution
> 
> Dunno...
> 
> A lot of times, native Windows programs deal better with UI zoom.
> 
> But stuff that uses GTK or similar, or renders UI via raw bitmaps, or 
> that goes through an X11 translation layer, tends to look pretty much 
> awful when UI zoom is used.
> 
> But, I mostly end up accepting the comparably small text of default font 
> sizes on a 4K monitor, even if at times it seems like my eyesight is not 
> good enough to reliably see typos (particularly those involving similar 
> looking characters).
> 

those aps are probably assumed to be run in low res... windows realizes 
it (i guess) and it tricks the aplications  they are runing in low res
(like rea desktop res/scaling probably)

im writing on blitter so its in fact no problem to chnge resolution of
this inner bitmap/bitsvreen area even in runtime..i can increase it
and decrease in runtime like setting it to 320 pixels or 3200 pixels
and then it is mapped on desktop

i can also recreate fonts with those size changes and just use
frame_size_y/25 font height so fonts are also proper size

(small problem is the font creating api needs font height to be integer
so there are not fluid changes but ugly jumping infont sizes..but then
i need to worry to rescale those fonts probably on my side and i could 
eventually worry it also wouldnt look very fluid - i would need to check)

[toc] | [prev] | [next] | [standalone]

#402838

From	Janis Papanagnou <janis_papanagnou+ng@hotmail.com>
Date	2026-10-09 01:39 +0200
Message-ID	<11a99j6$2fkbd$1@dont-email.me>
In reply to	#402833

On 2026-10-08 22:09, BGB wrote:
> On 10/8/2026 7:56 AM, Tim Rentsch wrote:
>> [...]
>> 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. [...]

[ extensive personal/medical explanations deleted ]

All I have to say on that is that I'd wish all people write as good
as you, especially given that there's a couple pathological persons
around WRT (beyond typos) their writing peculiarities.

> 
>> What you are calling "depth" in your code is customarily called
>> "height".  The height of a (sub-)tree is the length of the longest
>> path from the root of the sub-tree to a leaf.  For a node in a tree,
>> the depth of the node is the length of the path from the root of the
>> tree to that node.  So height measures "down" whereas depth measures
>> "up".
>>
>> I have run some test cases and the code looks like it produces trees
>> that are well-structured.  I didn't do any tests to check for
>> whether the trees produced are balanced.
> 
> OK.
> 
> As can be noted, I typed it out directly in the post, no testing 
> involved here.
> 
> Didn't notice some of the typos until after I posted it.
> 
>> 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.
> 
> I had understood it as being more about them being a balanced binary 
> tree with the goal of maintaining a +/- 1 balance for the left and right 
> sub-trees (as opposed to, say, an unbalanced binary tree).

Concerning the height/balance property you are completely right, and
all sources I inspected are speaking about balancing factors - and
these can be "derived" directly from the stored height information.
(The invariants have to be guaranteed after insertion and deletion.)
I think the previous misconception was that the OP mixed AVL-property,
the definition of what constitutes an AVL tree, with the implementation
decision, the concrete model.

Online I found (for various languages) of course code with the height
attribute. There's also code descriptions (e.g. a Wirth book) that use
-1..+1 (probably with an implicit temporary +/-2 overflow to prevent
in some implementations I've seen).

(N.B.: I'm unsure what the intention of the OP actually is when he
explains "My interest here is to see how people would write the code."
where he knows how to write an implementation. - From his reply to you
I suspect he just wants to teach people how to do things "right" as to
his judgement. - Implementing such code in "C", so I'd suppose, would
also not show any fundamental new insights; most people here are more
or less "C" experts. - We need a 'struct' for the node, the attributes
key, some height/balance, and two pointers to nodes. The AVL-algorithms
are simple to copy/transfer from any book explaining this type of tree.
So what insights are to be expected? - It would have been helpful, as
so often, if the OP would have been less obscure and just say what he
concretely wants to learn from the responses.)

> 
> The tag bit or "node coloring" approach was (I thought) a different type 
> of tree (like a red/black tree).

RB-trees are like AVL-trees binary trees with dynamic adaption to not
let them degenerate arbitrarily but to guarantee some depth properties
(to thus get better access times). The AVL criterion is stricter. The
red/black color tags serve a similar purpose as the AVL-balance factor.

(I looked up my written notes from the lectures of R. Bayer back then;
he invented the B-trees and the RB-trees by another name ("symmetric
binary B-trees"). But RB-trees were obviously not part of his course
back then. Though I see that the Wikipedia entries are also okay.)

> 
>> 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.

N. Wirth, Ottmann/Widmayer, Denert/Franck (all about data-structures),
are some sources I have that explain them. And de.wikipedia.org and
web-searches also provide both, descriptions and concrete source code.

> 
> I read about them at some point when I was younger, and used them 
> occasionally.
> 
> Often their use-cases compete with B-Trees and hash-tables, which I more 
> often use.

While balanced trees and hash-tables are used for the implementation of
dictionary-like [semantical] data structures both are very different in
their properties and implementation; they don't quite compare per se.
B-trees (and B*-trees) have own different properties (and thus different
typical application cases). I won't expand on that further here.

BTW, I had intended to write (for another language than "C") an AVL-tree
implementation. (Just finished it, but yet it needs verification of the
AVL-invariants that I intended to add.) It also uses a height attribute
and a balance function (based on the height attributes) to determine the
necessary tree-balancing operations. - The OP's post at least made me
overcome my laziness and implement that beast. :-)

Janis

> [...]

[toc] | [prev] | [next] | [standalone]

#402840

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-10-09 00:03 -0700
Message-ID	<86fqyfjqy5.fsf@linuxsc.com>
In reply to	#402838

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:

> On 2026-10-08 22:09, BGB wrote:
>
>> On 10/8/2026 7:56 AM, Tim Rentsch wrote:
>>
>>> [...]
>>> A few comments.
>>>
>>> The posted code has a few typos.  They were easy to fix.

[...]

> (N.B.:  I'm unsure what the intention of the OP actually is when
> he explains "My interest here is to see how people would write the
> code."  where he knows how to write an implementation.

I meant what I said and I said what I meant.  And not more than
that.

> - From his reply to you I suspect he just wants to teach people
> how to do things "right" as to his judgement. [...]

You're wrong.  My interest here is in learning, not teaching.

[toc] | [prev] | [next] | [standalone]

#402839

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-10-08 23:53 -0700
Message-ID	<86jynrjrf3.fsf@linuxsc.com>
In reply to	#402833

BGB <cr88192@gmail.com> writes:

> On 10/8/2026 7:56 AM, Tim Rentsch wrote:
>
>> BGB <cr88192@gmail.com> writes:
>>
>>> 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):
>>>
>>> [.. 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.

[toc] | [prev] | [next] | [standalone]

#402842

From	David Brown <david.brown@hesbynett.no>
Date	2026-10-09 10:34 +0200
Message-ID	<11aa8vb$jk93$1@dont-email.me>
In reply to	#402839

On 09/10/2026 08:53, Tim Rentsch wrote:
> BGB <cr88192@gmail.com> writes:
> 
>> On 10/8/2026 7:56 AM, Tim Rentsch wrote:
> 
>>> 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.

I would not recommend that, any more than I would recommend "The C 
Programming Language" to someone wanting to learn C.

Knuth's detailed mathematical treatment of algorithms is second to none, 
and his contribution to computer science is legendary.  His writing 
style is wonderful, and I thoroughly enjoyed the TeXbook (though it left 
me with a serious disability - I am now unable to read text without 
being annoyed at typographic flaws or inconsistencies!).

But it is /not/ a book you use to learn a new topic.  It is not a book 
you use to learn about AVL trees (it does not even mention them by that 
name), either in terms of what they are used for, how they work, or how 
they may be implemented.  You will learn more that is relevant to you 
from an animated gif on the Wikipedia page than from reading the entire 
chapter in "Fundamental Algorithms".

If you want to understand how you can prove the algorithmic complexities 
of different tree structures and their algorithms, and to better 
understand how to prove the tree invariants, and to better understand 
how to make your own interesting tree structures - /then/ studying that 
part Knuth's book could be useful.  It is not a book you read, it is 
something you have to study.

And like "The C Programming Language", it suffers from age - you can't 
learn modern C from a 50 year old book, and you can't learn modern 
coding from a 60 year old book.  Far and away the biggest mistake of the 
books - IMHO - is the use of a mythical assembly as the language for the 
programs instead of a high-level pseudo-code that made the interesting 
stuff clear instead of bogging it down in irrelevant detail.

[toc] | [prev] | [next] | [standalone]

#402846

From	Janis Papanagnou <janis_papanagnou+ng@hotmail.com>
Date	2026-10-09 12:27 +0200
Message-ID	<11aafhp$cjm0$1@dont-email.me>
In reply to	#402842

On 2026-10-09 10:34, David Brown wrote:
> On 09/10/2026 08:53, Tim Rentsch wrote:
>> BGB <cr88192@gmail.com> writes:
>>> On 10/8/2026 7:56 AM, Tim Rentsch wrote:
>>
>>>> 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.
> 
> I would not recommend that, any more than I would recommend "The C 
> Programming Language" to someone wanting to learn C.
> 
> Knuth's detailed mathematical treatment of algorithms is second to none, 
> and his contribution to computer science is legendary.  His writing 
> style is wonderful, and I thoroughly enjoyed the TeXbook (though it left 
> me with a serious disability - I am now unable to read text without 
> being annoyed at typographic flaws or inconsistencies!).

(Hah! - And I thought I'm a rare case here, being [in my vicinity]
the only one who seems to be suffering from bad typesetting. - I
didn't need his book, though - actually I haven't read his book on
TeX - since these bad feelings appeared as soon as MS word came out,
and Ariel fonts, and similar typographical steps backwards.
It's characteristic; you look at a book and can immediately make an
educated guess whether it had been typeset using TeX, Nroff, MSWord,
or something else.)

> 
> But it is /not/ a book you use to learn a new topic.  It is not a book 
> you use to learn about AVL trees (it does not even mention them by that 
> name), either in terms of what they are used for, how they work, or how 
> they may be implemented.  You will learn more that is relevant to you 
> from an animated gif on the Wikipedia page than from reading the entire 
> chapter in "Fundamental Algorithms".
> 
> If you want to understand how you can prove the algorithmic complexities 
> of different tree structures and their algorithms, and to better 
> understand how to prove the tree invariants, and to better understand 
> how to make your own interesting tree structures - /then/ studying that 
> part Knuth's book could be useful.  It is not a book you read, it is 
> something you have to study.

I very much agree on everything you wrote here.

The unfortunate part of the story is that a lot of the literature on
that (unless referring to the original authors of the AVL tree) is
obviously [still] based on or inspired by Knuth's book. (One detail
is the already mentioned representation of the balancing property.
Even Wikipedia still shows that form, but at least they explicitly
mention that they based their representation on Knuth and that using
the height is an equivalent option.)

> 
> And like "The C Programming Language", it suffers from age - you can't 
> learn modern C from a 50 year old book, and you can't learn modern 
> coding from a 60 year old book.  Far and away the biggest mistake of the 
> books - IMHO - is the use of a mythical assembly as the language for the 
> programs instead of a high-level pseudo-code that made the interesting 
> stuff clear instead of bogging it down in irrelevant detail.

Indeed. - It's many years that I had TAOCP in my hands but I seem
to recall that he also wrote (in that specific language) everything
in iterative form. That is especially bad in case of recursive data
structures and algorithms - we recently discussed that here! - that
are (IMHO) a lot clearer than any iterative code on tree structures.

With the Internet resources we luckily have a rich source of more
recent and refined information about that topic. (The problem there
is only to sort the wheat from the chaff.)

Janis

[toc] | [prev] | [next] | [standalone]

#402848

From	David Brown <david.brown@hesbynett.no>
Date	2026-10-09 12:59 +0200
Message-ID	<11aahf6$n0f0$1@dont-email.me>
In reply to	#402846

On 09/10/2026 12:27, Janis Papanagnou wrote:
> On 2026-10-09 10:34, David Brown wrote:
>> On 09/10/2026 08:53, Tim Rentsch wrote:
>>> BGB <cr88192@gmail.com> writes:
>>>> On 10/8/2026 7:56 AM, Tim Rentsch wrote:
>>>
>>>>> 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.
>>
>> I would not recommend that, any more than I would recommend "The C 
>> Programming Language" to someone wanting to learn C.
>>
>> Knuth's detailed mathematical treatment of algorithms is second to 
>> none, and his contribution to computer science is legendary.  His 
>> writing style is wonderful, and I thoroughly enjoyed the TeXbook 
>> (though it left me with a serious disability - I am now unable to read 
>> text without being annoyed at typographic flaws or inconsistencies!).
> 
> (Hah! - And I thought I'm a rare case here, being [in my vicinity]
> the only one who seems to be suffering from bad typesetting. - I
> didn't need his book, though - actually I haven't read his book on
> TeX - since these bad feelings appeared as soon as MS word came out,
> and Ariel fonts, and similar typographical steps backwards.
> It's characteristic; you look at a book and can immediately make an
> educated guess whether it had been typeset using TeX, Nroff, MSWord,
> or something else.)

(MS Word destroyed the quality of the printed word by opening it to 
people with no training or guidance, and making it very easy to make 
poor-quality and inconsistent documents.

I would not recommend anyone use plain TeX - but I can recommend the 
TeXbook.  (Think of it like learning to understand assembly for a 
processor - it's interesting and useful to know, even though you usually 
want to use much higher level languages.)  Lamport's "LaTeX: A Document 
Preparation System" is also highly readable, albeit a bit dated now - 
for actual document writing, modern descendents like LuaTeX are usually 
better.)

> 
>>
>> But it is /not/ a book you use to learn a new topic.  It is not a book 
>> you use to learn about AVL trees (it does not even mention them by 
>> that name), either in terms of what they are used for, how they work, 
>> or how they may be implemented.  You will learn more that is relevant 
>> to you from an animated gif on the Wikipedia page than from reading 
>> the entire chapter in "Fundamental Algorithms".
>>
>> If you want to understand how you can prove the algorithmic 
>> complexities of different tree structures and their algorithms, and to 
>> better understand how to prove the tree invariants, and to better 
>> understand how to make your own interesting tree structures - /then/ 
>> studying that part Knuth's book could be useful.  It is not a book you 
>> read, it is something you have to study.
> 
> I very much agree on everything you wrote here.
> 
> The unfortunate part of the story is that a lot of the literature on
> that (unless referring to the original authors of the AVL tree) is
> obviously [still] based on or inspired by Knuth's book. (One detail
> is the already mentioned representation of the balancing property.
> Even Wikipedia still shows that form, but at least they explicitly
> mention that they based their representation on Knuth and that using
> the height is an equivalent option.)
> 

Wikipedia is usually a good first start for this kind of thing.  It has 
its limitations, of course, but typically you can start there and then 
move on to more detailed resources according to needs and interests. 
And Wikipedia is quite good at showing their references.

>>
>> And like "The C Programming Language", it suffers from age - you can't 
>> learn modern C from a 50 year old book, and you can't learn modern 
>> coding from a 60 year old book.  Far and away the biggest mistake of 
>> the books - IMHO - is the use of a mythical assembly as the language 
>> for the programs instead of a high-level pseudo-code that made the 
>> interesting stuff clear instead of bogging it down in irrelevant detail.
> 
> Indeed. - It's many years that I had TAOCP in my hands but I seem
> to recall that he also wrote (in that specific language) everything
> in iterative form. That is especially bad in case of recursive data
> structures and algorithms - we recently discussed that here! - that
> are (IMHO) a lot clearer than any iterative code on tree structures.
> 

TAOCP (books 1 to 3) are on my bookshelf, along with all sorts of books 
of different vintages - but it is a very long time since I made any use 
of it.  (My "The C Programming Language" should be there too, but I 
don't know where it has gone.  My "The C++ Programming Language" is 
there - also very readable, also completely useless for learning modern 
C++.)

> With the Internet resources we luckily have a rich source of more
> recent and refined information about that topic. (The problem there
> is only to sort the wheat from the chaff.)
> 

Indeed.

Websites can offer better graphics and animations than books, and much 
more scope for trying things out yourself - they can give far more than 
books for this kind of thing.  But editorial and quality control is 
often sadly lacking.

[toc] | [prev] | [next] | [standalone]

#402847

From	bart <bc@freeuk.com>
Date	2026-10-09 11:43 +0100
Message-ID	<11aaggn$mu6q$1@dont-email.me>
In reply to	#402842

On 09/10/2026 09:34, David Brown wrote:
> On 09/10/2026 08:53, Tim Rentsch wrote:
>> BGB <cr88192@gmail.com> writes:
>>
>>> On 10/8/2026 7:56 AM, Tim Rentsch wrote:
>>
>>>> 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.
> 
> I would not recommend that, any more than I would recommend "The C 
> Programming Language" to someone wanting to learn C.
> 
> Knuth's detailed mathematical treatment of algorithms is second to none, 
> and his contribution to computer science is legendary.  His writing 
> style is wonderful, and I thoroughly enjoyed the TeXbook (though it left 
> me with a serious disability - I am now unable to read text without 
> being annoyed at typographic flaws or inconsistencies!).
> 
> But it is /not/ a book you use to learn a new topic.  It is not a book 
> you use to learn about AVL trees (it does not even mention them by that 
> name), either in terms of what they are used for, how they work, or how 
> they may be implemented.  You will learn more that is relevant to you 
> from an animated gif on the Wikipedia page than from reading the entire 
> chapter in "Fundamental Algorithms".
> 
> If you want to understand how you can prove the algorithmic complexities 
> of different tree structures and their algorithms, and to better 
> understand how to prove the tree invariants, and to better understand 
> how to make your own interesting tree structures - /then/ studying that 
> part Knuth's book could be useful.  It is not a book you read, it is 
> something you have to study.
> 
> And like "The C Programming Language", it suffers from age - you can't 
> learn modern C from a 50 year old book, and you can't learn modern 
> coding from a 60 year old book.

When I first looked at it wasn't quite that old!

> Far and away the biggest mistake of the 
> books - IMHO - is the use of a mythical assembly as the language for the 
> programs instead of a high-level pseudo-code that made the interesting 
> stuff clear instead of bogging it down in irrelevant detail.

This 'MIX' language was something that astonished me even then. Not only 
was it assembly that would totally obscure whatever algorithm was being 
expressed, but it was a weird made-up assembly with unusual byte and 
word sizes.
I understand that more recent editions use an updated 'MMIX' language: 
now the registers are 64 bits, and there's a lot more of them. This is 
still like publishing a book of algorithms using ARM64 assembly to 
express them.

It's not clear what he had against HLLs; perhaps he thought an actual 
HLL would soon be superseded? Then pseudo-code should have been used.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3 [1] 2 3 Next page →

csiph-web

AVL tree insertion - programming exercise

Contents

#402780 — AVL tree insertion - programming exercise

#402799

#402805

#402806

#402828

#402844

#402845

#402822

#402829

#402833

#402834

#402837

#402841

#402838

#402840

#402839

#402842

#402846

#402848

#402847