Making a multiway tree a heap after a node's key has changed?

Question

The tree has invariance that the parent node must always be smaller than its child, like the image shown above. Now suppose some of the node's key has changed and breaks the invariance and I want to maintain the invariance. I think it's basically compare-swap every child of a parent node but I can't figure out how to write the recursion to traverse the tree. It seems different from binary tree I learnt before...

Btw each node has no index but only three pointers: parent, leftChild, rightSibling. If the node is root, its parent point to NULL; if the node is the right most node, its rightSibling points to NULL... Can anyone shed some light on this? Thx in advance!

Answer 1

For starters, the representation of this multiway tree as a binary tree is called the left-child/right-sibling representation and has some tradeoffs with the normal multi-way tree representation. This older question/answer might give some background about how to recursively traverse these trees.

As to your question: there are two possible outcomes for a node's value changing:

• If the node's value has gone down, then you might need to swap it upward until its value is no longer less than its parent.
• If the node's value has gone up, then you might need to swap it with its smallest child until the value is no longer larger than any of its children.

One way to write this recursion would be to process the tree in two passes, in each pass checking for one of these two cases. There is no fundamental reason that these passes cannot be combined together, but for simplicity of explanation I'll treat each independently.

In the first case, we might need to swap a node with its parent node because its value has decreased. In that case, we need to simulate some sort of tree traversal in which we process all the child nodes first, then process the node itself. That way, if a value needs to get swapped up to the root across many levels, we can recursively bring it up to the highest level possible without crossing the root, then promote it one more level. If we had a standard multiway tree, the recursion would look like this:

void FixTreeUpward(TreeNode curr) {
    /* If the current node is null, we're done. */
    if (curr == null) return;

    /* Process each child. */
    for (TreeNode child that is a child of curr) {
        FixTreeUpwardRec(child);
    }

    /* If we need to swap values with our parent, do so here. */
    if (curr.parent != null && curr.value < curr.parent.value) {
        swap(curr.value, parent.value);
    }
}

Since we are using the left-child, right-sibling representation of a multi-way tree, the for loop in the middle will look a bit weird. We first descend to the left child, then keep going right until we run out of nodes. In pseudocode:

void FixTreeUpward(TreeNode curr) {
    /* If the current node is null, we're done. */
    if (curr == null) return;

    /* Process each child. */
    for (TreeNode child = curr.left; child != null; child = child.right) {
        FixTreeUpwardRec(child);
    }

    /* If we need to swap values with our parent, do so here. */
    if (curr.parent != null && curr.value < curr.parent.value) {
        swap(curr.value, parent.value);
    }
}

That's all there is to it! Conceptually the recursion isn't all that hard, and the only weird part about it is how we visit the children.

Let's think about the second part of the algorithm, where we have to bubble down if necessary. To do that, we would do the following: for each node, look at all its children and find the child with the least value. If that value is smaller than the root node's value, swap the root of the tree with that child, then repeat. In pseudo-ish code:

void FixTreeDownward(TreeNode root) {
    /* If the root is null, we have nothing to do. */
    if (root == null) return;

    /* Find the smallest child. */
    TreeNode smallChild = (root's first child, or null if none exists);

    for (TreeNode child in the children of the root) {
        if (child.value < smallChild.value) {
            smallChild = child.value;
        }
    }

    /* If we have a smallest child and it's smaller than our value,
     * swap values and recursively repeat this.
     */
    if (smallChild != null && smallChild.value < root.value) {
        swap(smallChild.value, root.value);
        FixTreeDownward(smallChild);
    }
}

So the only question here is now to iterate over all the children, and fortunately, that's not that hard! As before, we descend to the left subtree, then keep going right until we run out of nodes. This is shown here:

void FixTreeDownward(TreeNode root) {
    /* If the root is null, we have nothing to do. */
    if (root == null) return;

    /* Find the smallest child. */
    TreeNode smallChild = root.left;

    for (TreeNode child = root.left; child != null; child = child.right) {
        if (child.value < smallChild.value) {
            smallChild = child;
        }
    }

    /* If we have a smallest child and it's smaller than our value,
     * swap values and recursively repeat this.
     */
    if (smallChild != null && smallChild.value < root.value) {
        swap(smallChild.value, root.value);
        FixTreeDownward(smallChild);
    }
}

And we should be all set!

Hope this helps!