Training Wheels

2009/12/10

I’m frustrated today because, yet again, I’m trying to get “add” to work on my Red-Black Tree.

And really, the difficulty has nothing to do with the logic of my algorithm. My pseudo-code pseudo-works. The problem is learning the real, true behaviors of pointers and references, because my recursive call loses half my tree.

I want to swap out one node for another without referencing its parent and without having its parent lose track of it. My dog-eared, broken-spine Data Structures and Algorithm Analysis in C++ told me, in the section on AVL trees, about a little trick with reference pointers to do just that. I remember reading the section, thinking “Ah, that will work!” and closing the book. And now I really, really don’t want to open the book again to double check my understanding. The misbehavior of my function falls directly out of the properties of references, and it fails because I don’t understand them on a fundamental level. Recopying the book’s algorithm will NOT help me grasp reference pointers any better.

This my current issue:

template<class K, class T> void RBTree<K,T>::_rotateCounterClockwise(RBNode<K,T> *&grandParent)
{
RBNode<K,T>*& parent = grandParent->childRight;
parent->childRight->color = RBNode<K,T>::black;
grandParent->childRight = parent->childLeft; //??
parent->childLeft = grandParent;
grandParent = parent;
}

This changes the “parent” to the location of parent->childLeft, which implies that the reference to parent is just looking exactly at the location of grandparent->childRight. Which is what I told it to do… But when I just have a node pointer (instead of a node pointer reference), the grandparent is looking right where it’s supposed to–but the great-grandparent apparently decides to disown it during some part of the process. Hence the losing half my tree.

The frustrating thing is that these are very, very basic mistakes. It’s like a third grader being very confused about why 5 times 3 is the same as 3 times 5. (Although, come to think of it, I don’t think I could prove the transitive property right now, either.) But it has to do with the very basic functioning of small parts, and I will not give up until I get it.

Maybe, instead of trying to guess where to draw my arrows and boxes representing memory locations, I’ll curl up with Stoustrup for a bit, and let him spin some yarns about references.

>>>>>>

Can’t find my Stoustrup book, but have been kicking around new ideas about my code. Maybe the problem is that I’m passing the grandparent node directly, rather than as greatGrandParent->child.

AH it is so tempting to keep stabbing around in the dark! I am going to wipe clean a new white board, write out my memory addresses and step through line by line. I really don’t want to just slap code together until something seems to work; I have to know why it works and THEN build up.

I’m glad we had that talk.

>>>

Oh but now, in order for this to work on my whole tree, I’ll need a null header. And null headers… I’m sorry, but they feel like hacks to me in a way that special-casing the first element does not. But I think… if pointer pointers/ reference pointers work the way I think they do (which is probably not right, given all current evidence!), the root pointer will still point to the right thing. Because it’s just a node pointer, the way the rest of the links are node pointers. No, but if I change to needing great-grandparents, it won’t work anymore!

What was that about clearing a whiteboard and drawing it all out? Let’s start there.

>>>

…and I get distracted by browsing job boards, and an internship posting says “2 years of computer science degree completed–no other degrees allowed”. And I can choose how I react to this! I can be annoyed at the injustice of it all (who says CS majors are the only ones who can code?), or I can move on by focusing on improving my skills. I’m a completely nontraditional applicant, and I can’t expect traditional (or, rather, stereotypical; do we even know people who get jobs anymore through job boards?) avenues of employment to work for me at all.

FOCUS!

>>>

So my code was perfect–except, way at the top, I called “add” on a pointer instead of a pointer reference, so my beautiful references failed all the way down. This doesn’t change the fact that I need some more Stroustrup so I can predict why my references fail and quickly solve the problem–but this is a good lesson. When something fails further down, check back up the stack to make sure you’re passing things right!


Scaling Back

2009/12/04

One of my good friends always talks about starting a blog about his current passions. “That would make a great blog post!” he’ll say in the middle of conversations. But he still hasn’t taken the plunge–mostly because he’s not ready to write a Blog, the kind that’s linked to and commented on and requires maintenance and diligence and care. I’ve been having the same problem; I want to write about something, maybe in a public way, but I don’t want to Blog about it.

So I’m scaling back, in my mind, the purpose of my writing here. It will help keep me focused on my goals and accountable for my work, but it will not be a PR campaign. And I will allow myself the occasional tangent, such as:

This morning I went for a run and the sun was shining, and now the fog has rolled in–but I am going to surprise a good friend this evening by delivering a load of fireplace to her apartment (fireplaces help the winter blues), and then, hot cider toddy in hand, I’ll hit the the caroling festival in downtown Seattle.

But first, I will implement add in my red black tree. It’s taken me longer than it should have, because I really believe there’s a way to do it iteratively without keeping a stack of the path or maintaining parent pointers—but I haven’t yet figured out how. At this point, I need to just make it work so I can make sure my test methods work, and then I’ll tease out efficiencies in the next round. Even if I have to rewrite it all when I find this elusive algorithm, it’ll be good practice for developing consistent interfaces; my black-box tests should be the same regardless of the implementation.

And when I say “find” the algorithm, I mean “figure out”, because I am too proud to just search for the answer. Honestly, what would be the point? The world has no immediate need for my own version of a red black tree; the only purpose of implementing it is to stretch and strengthen my brain. So even if my brain is too rigid and weak for this task, I will not let it stay that way for long. Onward, ho!