View Full Version : Rewrite!

11-01-2005, 02:51 PM
Critiques please. :) This is a very preliminary version (http://www.eternallyconfuzzled.com/tuts/bst.html). The code hasn't been fully debugged and the tutorial isn't presented with all of the frills that I like to add. But I'd like to know how this one compares to the other one (http://www.eternallyconfuzzled.com/tuts/bst1.html) before I finish the new one and replace the old one.


11-01-2005, 03:21 PM
My comments after reading it through once:

1) In your diagram showing leaf nodes, you left out some leaf nodes, which some people may find confusing.

2) In the first code example under the Search heading, you have root declared as "struct jsw_node root", but then compare it to NULL. Bwuh?

3) Same code example. You seem to be using pointer notation for referencing members of the structs, but they're not pointers. (Edit: you seem to be doing this in most examples).

4) In your insertion example code, you call the make_node() function, but don't define it. (Yes, it's trivial, but I'm feeling nitpicky).

At this point, the pointer arithmetic on non-pointers has started to hurt my brain, so I'm going to take a nap. I'm pretty sure I've just missed something, but I can't seem to figure out what.

11-01-2005, 03:58 PM
1) Hehe, gomen. :) I'll fix that straight away. (done)

2) You've discovered a bug in my auto-formatting program. They really are supposed to be pointers. ;) (fixed)

4) I'm pretty sure I describe how it works before that, but I'll double check. (added a quick comment to that effect)

11-01-2005, 04:00 PM
Regarding #4, you describe it later on in the article actually. Might want to move the description. (Specificly under the "Parent Pointers" section)

11-01-2005, 09:06 PM
Alrighty. I've read through it some more:

1) "int dir = root->data < data;"

I don't have any copies of the C standards, but is the "<" operator guaranteed to return 0 and 1? Or is it 0 and non-zero? Same thing with the "==" operator.

2) Your use of the comma operator may throw off some users. It's very rarely used, so not everyone will know what it does.

So far I've read up to Traversal. I'll read from there on tomorrow.

11-01-2005, 11:58 PM
I agree, avoid the comma operator. Especially because, IIRC, it's designed to be used where you can't seperate the statements (like between the " ; ; " in the top of a 'for' loop).

1) The 'heir' word. Theres two issues with this: A) It can confuse people who aren't good with english, or have trouble pronouncing words like this as they read it (me), and B) The word "child" is used in nearly every other example on trees - it's a bit of a convention.

2) While I agree the link[0/1] thing is faster and better than node->Left and node->Right, understanding it distracts from understanding the actual tree. You even devote a couple of paragraphs explaining why, and also why your comparrison operators are in reverse. Perhaps, for the sake of clarity in the tutorial, you could use 'Left' and 'Right' and add the link[0/1] thing at the end?

I guess what I'm getting at is the primary focus of the tutorial is meant to introduce BST's, so if you're a struggling college student with a test tommorow and you need to boslter your understanding, these extra conventions/practices (no matter how important they are) just add to the clutter.

Also, a style thing: I don't like the special starting capital letter of every paragraph. It's great for the start of a section, but I find it a little annoying paragraph after paragraph. Although, it's fun to try and make an "acrostic poem" out of the paragraphs. That's a personal thing though, YMMV.

I understand this can be frustrating though - there's an awful lot of knowledge in your head, you want to get it into everyone else's head, but if you try and teach too much it just makes it harder.

Prelude, have you ever considered becoming a published author? I'd certainly rather read a book on C/C++/Java by you than the boring, dry, fluffy text books out there.

11-02-2005, 07:30 AM
>is the "<" operator guaranteed to return 0 and 1?
Yes. That's actually an issue we've touched on here before, but in a different context (of someone trying to correct one of my answers ;)).

>Your use of the comma operator may throw off some users.
That's a good point. I think that in this case it's a safe and understandable usage, but it might be a good idea to either remove it or explain why it's used initially.

>The word "child" is used in nearly every other example on trees -
>it's a bit of a convention.
So is the right-left pointer idiom, and I'm not sure that's a good convention. In concept, yes, but in practice I think the array is better. I probably should change heir to something more obvious, like succ. ;)

>Perhaps, for the sake of clarity in the tutorial, you could
>use 'Left' and 'Right' and add the link[0/1] thing at the end?
I debated that with myself and ended up deciding that it would be better to avoid the common convention entirely in favor of what I consider to be better practice. It really is easier once you get used to it because all of those symmetric cases are removed. I think it's those symmetric cases that make trees daunting. First you have the trouble of making sure you don't make mistakes, which is very easy if the only difference between the left and right cases is the name of the link. Second, it can make the code much longer, which stops some people cold. By removing redundant code and making the functions shorter, I make them more accessible to beginners and people who don't want to wade through pages of source to understand what's going on. A couple of paragraphs to help them understand the idiom is worth the benefit from the idiom, no? :)

>have you ever considered becoming a published author?
Yes, in fact I have a book in the works and a publisher is interested in it. But it's a fantasy series, not a programming text. ;) I'm not sure I could collect all of my thoughts together in such a way as to make a good programming book.

11-02-2005, 09:12 PM
I would certainly buy a programming book written by Prelude! :D

One quick question about you 'Deletion' section under Binary Search trees. Shouldn't the 5 be a 7?

11-03-2005, 06:52 AM
>Shouldn't the 5 be a 7?
Yep. :)

The Brain
11-03-2005, 03:10 PM
I would rather read a Prelude book on Prelude.. ;)