Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #402838

Re: AVL tree insertion - programming exercise

Show all headers | View raw

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

> [...]

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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 scott@slp53.sl.home (Scott Lurndal) - 2026-10-11 15:24 +0000
  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