C2K C2K - 10 days ago 6
C++ Question

Modify a binary search tree

I am trying to write a method for a binary search tree class to modify a balanced a normal tree which makes the tree have nodes only on one side.

From the order in which the elements are appearing in the unbalanced tree, to me there seems to be some relation between the In Order Traversal (Left, Middle, Right).

Answer
void unbalance(Node **pp) {
    Node *p;
    while ((p = *pp)) {
        if (!p->left) {
            pp = &p->right;
        } else {
            Node *tmp = p->left->right;
            *pp = p->left;
            p->left->right = p;
            p->left = tmp;
        }
    }
}

...
Node *tree = ...;
unbalance(&tree);

This code is based on @templatetypedef's answer. It uses a pointer-to-pointer to avoid orphaning nodes (which also gets rid of finalRoot, whose only purpose is to avoid orphaning the original root passed in by the caller).

The idea is to walk down the tree along the rightmost branch. If there never are any left children, we only enter the first part of the if statement and exit without doing anything.

The else part is used when there is a left subtree. In that case we rotate the tree right. animated tree rotation

This has the effect of pulling one node up from the left subtree, i.e. our left subtree is now one node smaller. We repeat this until the left subtree is completely gone, at which point we enter the first part of the if again. Then we go down to the remaining right subtree and repeat the whole thing.

Pointer-to-pointers are often useful when modifying the structure of a linked list or tree. They let us work directly on the original pointers instead of making a copy of them. In this case, the assignment *pp = ... modifies a pointer elsewhere (the one pp is pointing to). This is either the original root (as passed in by the caller), or one of the right pointers within the tree (as set by pp = &p->right). This repointing is needed because the tree rotation in the else branch shuffles nodes around, so what used to be the root of a subtree gets moved further down, and the former left node gets pulled up to become the new root. We update *pp to preserve the invariant that the pointer higher up (either the tree variable in our caller or the right member of our parent node) points to the (new) root of the subtree.