May 28th, 2002


(no subject)

yeah, you're going to need not only a lot about me, but a lot about the story of the comic to know why this page is so painful to me.

and I don't think there's anybody out there who knows both (and precious few who know either).

On the other hand, I'm posting it anyway . . . ask me in private if you want me to explain, I guess, because I can't do it here right now.

(no subject)

<Yuhjn> I'm reading a TOC for a datastruct book and one section is on "non-recursive binary tree traversal" ... this is obviously impossible so do you think they are talking about using your own stack to do your own recursion? (ie, no system stack)
<ZorbaTHut> it's not entirely impossible
<ZorbaTHut> if the tree has a "parent" node, it's quite possible.
<Yuhjn> hmm
<ZorbaTHut> though a little tricky to work out the logic :P but possible.
<ZorbaTHut> and how on earth do I know that?
<Yuhjn> naaa, using a parent pointer cannot avoid recursion as far as i can tell
<ZorbaTHut> I think it can.
<ZorbaTHut> *considers*
<Yuhjn> hrm, yes
<Yuhjn> appreanly it can
<ZorbaTHut> just takes some work. :)
<Yuhjn> you have to use a linked list as well
<ZorbaTHut> I think it may be possible to do it without the linked list also
<ZorbaTHut> I'm just not sure.
<ZorbaTHut> *considers*
<Yuhjn> you need it for your loop condition
<ZorbaTHut> if( curnode->right ) { curnode = curnode->right; while( curnode->left ) { curnode = curnode->left; } } else { . . . something nasty here involving which side of the parent this node is on . . . }
<ZorbaTHut> I think it may be possible.
<ZorbaTHut> can you prove it isn't? ;)
<Yuhjn> I've yet to see one that suggests a solution without a linked list
<Yuhjn> but no i probably cant prove it :)
<ZorbaTHut> ooh, I bet I can find one
<ZorbaTHut> yep. bingo.
<ZorbaTHut> MSVC.NET's iterator for trees contains, as data, _Nodeptr _Ptr; // pointer to node
<ZorbaTHut> and that's all.
<ZorbaTHut> and, yeah, the logic is the same as I was working out
<Yuhjn> O
<Yuhjn> I'm not convinced yet
<ZorbaTHut> if( curnode->right ) { curnode = curnode->right; while( curnode->left ) { curnode = curnode->left; } } else { while( curnode->parent && curnode->parent->right == curnode ) curnode = curnode->parent; curnode = curnode->parent; } return curnode->data;
<ZorbaTHut> and, yeah, that matches the algorithm in the MSVC STL. :P

where do I come up with this stuff? I know I've never seen the algorithm before . . . I might have heard it mentioned as possible, but I certainly don't remember it.


welcome to my life.