Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #402848
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: AVL tree insertion - programming exercise |
| Date | 2026-10-09 12:59 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <11aahf6$n0f0$1@dont-email.me> (permalink) |
| References | (4 earlier) <86wlrsjqq9.fsf@linuxsc.com> <11a8ta9$6463$1@dont-email.me> <86jynrjrf3.fsf@linuxsc.com> <11aa8vb$jk93$1@dont-email.me> <11aafhp$cjm0$1@dont-email.me> |
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.
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