Insert and Move to Root

We won't literally insert directly at the root of a subtree.

Instead, we will insert our key in a leaf (as usual) and then use rotations to move the new node up to the root of the subtree.

The algorithm will be very similar to our usual BST insertion, with just a bit of extra code for the rotations.

Implementing insertAndMoveToRoot

Below is an unfinished function for insertAndMoveToRoot. Right now, it just does ordinary BST insertion.

/**
 * \brief Inserts the given key into the subtree rooted at the given node,
 *        and moves the key to the root of the subtree.
 * \param node A reference to a pointer to the root node of the subtree
 * \param key  A constant reference to the key to be inserted
 */
void insertAndMoveToRoot(Node*& node, const string& key) {
    if (node == nullptr) {
        node = new Node{key};
    } else if (key < node->value_) {
        insertAndMoveToRoot(node->left_, key);
        // New line goes here
    } else {
        insertAndMoveToRoot(node->right_, key);
        // New line goes here
    }
}

Okay, so it's almost there. Now, let's remind ourselves of the concept we saw last week, tree rotations:

And in particular, imagine we've got two functions rotateLeft and rotateRight that do the following take a tree node and perform the appropriate rotation.

Because in this case our new value is just to the left of the root, we need a right rotation to get the new value to the root of the whole tree.

In the else case, when we've inserted into the right subtree, we'd have to do the opposite.

An Example

Just to help you visualize this algorithm, here's a quick video example:

Optional: A Connection

(When logged in, completion status appears here.)