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.
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!