Re: AVL tree insertion - programming exercise

From	cross@spitfire.i.gajendra.net (Dan Cross)
Newsgroups	comp.lang.c
Subject	Re: AVL tree insertion - programming exercise
Date	2026-10-12 18:26 +0000
Organization	PANIX Public Access Internet and UNIX, NYC
Message-ID	<11aj8p9$k21$1@reader2.panix.com> (permalink)
References	<86ece2kppv.fsf@linuxsc.com> <11aasbg$r60s$1@dont-email.me> <11abge0$dkj$1@reader2.panix.com> <11adef7$1ol9b$1@dont-email.me>

Show all headers | View raw

In article <11adef7$1ol9b$1@dont-email.me>,
David Brown  <david.brown@hesbynett.no> wrote:
>On 09/10/2026 21:48, Dan Cross wrote:
>> In article <11aasbg$r60s$1@dont-email.me>,
>> David Brown  <david.brown@hesbynett.no> wrote:
>>> [snip]
>>> It would undoubtedly have been less astonishing in 1968 (when the first
>>> book was published) than in 1991 (when I first saw it), but I would have
>>> thought that even people familiar with 1960's mainframes would see it as
>>> strange to use a limited and highly specific artificial assembly that
>>> matched poorly with existing systems.
>> 
>> That's the thing: I don't know that it did match poorly against
>> many of those systems.  Word oriented machines, with word sizes
>> that were not powers-of-two, abstruse IO instructions; all of
>> that was fairly common back then.  True, the IBM 360 had bucked
>> that trend and would set the precedent for what came later, but
>> that hand't happened yet.
>
>You misunderstand me, I think.  Yes, cpus had widely varying 
>architectures, word sizes, data representations, etc., and could have 
>instructions dedicated to particular hardware devices - and if all else 
>failed in your code, a "halt and catch fire" instruction.  It's not so 
>much that MIX matched poorly to existing systems - they all matched 
>poorly to each other.  Implementing an algorithm on different 
>processors' assemblies meant figuring out how to make it work with that 
>particular word size, or how to make efficient use of the particular 
>indexing registers and addressing modes that the cpu used.  Translating 
>from one assembly to another on a radically different architecture means 
>two steps - you first have to figure out what the original code is 
>really trying to do, and abstract away from the messy implementation 
>details.  Then you have to fit it into the new architecture, and add the 
>new messy implementation details.
>
>So by using MIX, rather than a higher level, more abstract pseudo-code, 
>anyone trying to use the code in the book on a real cpu has to do twice 
>the work.

I mean, maybe?  I believe he thought that MIX was close enough
to the other common processors of the day that someone familiar
with them would be able to translate relatively easily; whether
that was true or not, I can't say.  I don't know what he was
thinking other than what he's said about it publicly.

>> Moreover, assembly language programming for applications was
>> still common.  Using assembler would have had a lot of reach,
>> even if it's a fairly opaque way to present algorithms.
>
>Sure, assembly was very commonly used for applications - and for a long 
>time afterwards.  It's a major reason why the computing world is 
>dominated by the polished turd that is the modern x86 processor - 
>translating assembly programs into anything else is difficult, expensive 
>and risky, so it is rarely done.

Yup.  Funnily, he mentions this in Volume 1; in section 1.4.3.1,
he builds a MIX simulator (in MIX, naturally).  The prefatory
material includes,

|The motivation for simulators is simple: A computer
|installation buys a new machine and still wants to run programs
|written for the old machine (rather than rewriting the
|programs).  However, this usually costs more and gives poorer
|results than if a special task force of programmers were given
|temporary employment to do the reprogramming.  For example, the
|author once participated in such a reprogramming project, and a
|serious error was discovered in the original program, which had
|been in use for several years; the new program worked at ﬁve
|times the speed of the old, besides giving the right answers
|for a change!  (Not all simulators are bad; for example, it is
|usually advantageous for a computer manufacturer to simulate a
|new machine before it has been built, so that software for the
|new machine may be developed as soon as possible.  But that is
|a very specialized application.)  An extreme example of the
|ineﬃcient use of computer simulators is the true story of
|machine _A_ simulating machine _B_ running a program that
|simulates machine _C_!  This is the way to make a large,
|expensive computer give poorer results than its cheaper cousin.

YMMV, but this seems to make clear his position on the matter.
:-D

(Of course, the counter argument was that a high-level language
could be presented to a compiler targetting a new CPU, or a high
level pseudocode could be translated to a concrete
implementation by hand.)

>>> I am sure people were already
>>> familiar with the pain of converting code written in assembly for one
>>> system into assembly for a very different system - the only advantage of
>>> the MIX code was that it was equally useless to everyone, and favoured
>>> no one!
>> 
>> Ha; great description.  But had he chosen Burroughs, or IBM 360,
>> or PDP-6, or the GE-635, or whatever else, it would have been
>> seen as favoring a particular vendor (and therefore irrelevant
>> to those using other machines) or too specific to be considered
>> general.
>
>I can fully understand neutrality here.  He may even have wanted to 
>avoid favouring one existing high-level language for another.  But the 
>guy was pretty smart - he could easily have invented his own 
>hypothetical high-level language to use instead of such a low-level one.

Probably!  He clearly thought that assembly language was an
important use case, but if I were speculating about why he did
not use a HLL or pseudocode beyond what he's already said would
just be guessing.  *shrug*

>>> [snip]
>>> My bookshelves are too scattered for me to easily see what I have.  But
>>> I am not convinced that books are good references at all these days, for
>>> most purposes.  They are, however, still good for study if you are doing
>>> courses or really learning a subject.
>> 
>> Oh?  Nowdays we have far more available resources, so I can see
>> how one wouldn't necessarily reach for a book the way one would
>> have in days past, but what do you see as the alternative?
>
>I don't know that there is one right answer - it depends on the depth 
>you want to go into, how specialist the topic is, and what you are 
>trying to get out of it all in the end.  And it depends on how you 
>personally want to learn.  For deeper study and for more specialist 
>topics, books are still the top choice for me.  And I much prefer to 
>read books than websites over breakfast.
>
>But if I want a reference or refresher on AVL trees (to pick a random 
>topic :-) ), my first port of call is Wikipedia.  If that is not enough, 
>I might be looking for videos - there's plenty around that can give nice 
>animations to help you understand what is going on, from five minute 
>quick introductions to hour-long lectures.  I'd look for sample code in 
>a high level language - typically Python, but it might be interesting to 
>look at implementations in Haskell or other significantly different 
>languages.  There are webpages full of explanations of them, and 
>comparisons to other tree structures.  And there are online courses for 
>those looking for more academic treatment of data structures and algorithms.
>
>The internet is full of resources like this.  Of course the quality is 
>varied - you definitely want to look at more than one site to get a 
>balanced view, and to minimise the risk of missing something important. 
>But for technical and non-controversial subjects like this, you are 
>going to be fairly safe with Wikipedia and a google search.

Yeah, that's all fair.

>[snip]
>I wonder how CSP is taught now that people wave bank cards or mobile 
>phones at vending machines instead of inserting coins...
>
>(There's a fun family of microcontrollers with CSP at their heart from 
>XMOS.)

Since you mentioned CSP _and_ videos, this talk from Rob Pike
is pretty good, if indirect:
https://www.youtube.com/watch?v=oV9rvDllKEg

	- Dan C.

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 cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-12 18:26 +0000
                Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-12 21:17 +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
  Re: AVL tree insertion - programming exercise "chine.bleu" <chine.bleu@yahoo.com> - 2026-10-13 01:38 -0700
    Re: AVL tree insertion - programming exercise David Brown <david.brown@hesbynett.no> - 2026-10-13 11:42 +0200
      Re: AVL tree insertion - programming exercise cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-13 10:55 +0000
      Re: AVL tree insertion - programming exercise Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-10-13 04:29 -0700
    Re: AVL tree insertion - programming exercise James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-10-13 06:20 -0400
    Re: AVL tree insertion - programming exercise Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-13 03:52 -0700

csiph-web