StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>Updated:</strong> So you want to keep the ordering of the nodes, by replacing the node with its direct inorder successor or predecessor.</p> <p>Let's suppose the tree below is ordered. The order of the nodes is:</p> <pre><code>H < D < I < B < J < E < K < A < F < M < C < N < G < O </code></pre> <p>You want to delete a node (A) which has two children. You pull up either its inorder predecessor (K) or successor (F) child of the node in place of the original. Let's pick the successor. This is how you find it: you traverse the left children of C until you find one which has no left child; this is the direct inorder successor of A.</p> <pre><code> A B C D E F G H I J K M N O </code></pre> <p>So F is pulled up, and the left subtree of A is not touched. However, now M should be pulled up as well, to become the left child of C (this is done in your <code>extractMin()</code>).</p> <p>After all rearrangements, you get</p> <pre><code> F B C D E M G H I J K N O </code></pre> <p>In code, this is my solution. I added a NULL check to <code>extractMin()</code> to simplify the caller code, so I don't need <code>else if</code>.</p> <p><strong>Updated</strong> <code>extractMin()</code> to cover the case when <code>tree</code> has no children.</p> <pre><code>Tree *extractMin(Tree *parent, Tree *tree) { if (!tree) return NULL; Tree *prevPtr = NULL; Tree *currPtr = tree; while(currPtr->left) { prevPtr = currPtr; currPtr = currPtr->left; } if (prevPtr) { prevPtr->left = currPtr->right; } else if (parent) { parent->right = currPtr->right; } // inorder successor return currPtr; } // prevPtr is the parent, currPtr is the node to be deleted Tree *successor = extractMin(currPtr, currPtr->right); successor->left = currPtr->left; successor->right = currPtr->right; if (fromLeft) { prevPtr->left = successor; } else { prevPtr->right = successor; } // Now currPtr can be destroyed </code></pre> <p>Note that this code is not tested, so I don't guarantee anything :-)</p> <p>Note that repeated deletes like this may make the tree unbalanced (that is, some paths will get much longer than the others). Binary sort trees do deletions this way, but also use rebalancing after to keep the tree close to the ideal (where each leaf is at the same level, like in my first example above).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload