C2K - 1 year ago 102
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).

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

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download