Implementing Rotations
I'm not feeling super confident about writing code to do rotations, and I'm worried that if I get it wrong, nothing will work right.
Yeah, mate, a bad rotation could make a real dog's breakfast of your tree.
No worries, we can write
rightRotatetogether!
What's that about a dog's breakfast?
-
Sssh.
Let's begin with a bit of review. Our TreeStringSet encoding looks like
class TreeStringSet {
public:
...
private:
Node* root_;
};
And our Node struct looks like
struct Node {
std::string value_;
Node* left_;
Node* right_;
};
Also, remember that we wrote insert as
:
void TreeStringSet::nodeInsert(Node*& node, const string& key) {
if (node == nullptr) {
node = new Node{key};
} else if (key < node->value_) {
nodeInsert(node->left_, key);
} else if (node->value_ < key) {
nodeInsert(node->right_, key);
} else {
throw std::logic_error("duplicate key");
}
}
-
Wait… That
Node*&thing still freaks me out… 
It freaked me out, too, but remember: in its base case,
nodeInsertneeded to be able to change the value ofnode, which is aNode*!-
Too right, mate. That meant that we couldn't just pass in a
Node*like we did for lookup, because we'd be changing a copy! -
Having a reference to the pointer lets us change the value in the parent node so that it points to the new node we created.
-
Oh! That makes so much more sense now!
-
It's like you don't even need us anymore!
When we implement rotations, we're changing a part of the tree, so we want to make sure that we're acting on references to Node*s, not copies.
The signature for our right-rotation function will look like
void TreeStringSet::rotateRight(Node*& top) {
// To be determined ...
}
Our rotation function will have to rearrange pointers so that the structure of the tree is correct.
As a reminder, here's our image summarizing how a right rotation should behave:
There's no “right” order to change the pointers around, but we need to make sure that we don't lose the addresses of any of our Nodes while we're working. Here's one possible order:
:
/**
* Rotates the tree to the right.
* \param top is d in the diagram.
*
* d b
* / \ / \
* / \ / \
* b E ==> A d
* / \ / \
* / \ / \
* A C C E
*/
void TreeStringSet::rotateRight(Node*& top) {
// Save a temporary pointer to d and b so we don't lose it.
Node* d = top;
Node* b = top->left_;
// Make a copy of the Node* to give a name that matches the diagram.
Node* C = b->right_;
// Change d's left child to be C
d->left_ = C;
// Change b's right child to be d
b->right_ = d;
// Make b the new top.
top = b;
}
/**
* Rotates the tree to the left.
* \param top is b in the diagram.
*
* b d
* / \ / \
* / \ / \
* A d ==> b E
* / \ / \
* / \ / \
* C E A C
*/
void TreeStringSet::rotateLeft(Node*& top) {
// You have to do this one!
}
Hay! Would you mind if I just copied this code?
-
If you give attribution, it's fine!
But in the homework, you also need to keep the sizes of subtrees up to date as you perform rotations, so there is a little more left to do.
-
Well, thank you, anyway! This is certainly a good start.
(When logged in, completion status appears here.)