Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #402846
| From | Janis Papanagnou <janis_papanagnou+ng@hotmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: AVL tree insertion - programming exercise |
| Date | 2026-10-09 12:27 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <11aafhp$cjm0$1@dont-email.me> (permalink) |
| References | (3 earlier) <11a6qi4$3cv2b$1@dont-email.me> <86wlrsjqq9.fsf@linuxsc.com> <11a8ta9$6463$1@dont-email.me> <86jynrjrf3.fsf@linuxsc.com> <11aa8vb$jk93$1@dont-email.me> |
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
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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