Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The textbook answer is to replace the node in question with it's left-most right descendant.</p> <pre><code> 6 3 8 2 4 7 9 1 5 10 </code></pre> <p>If we want to remove 3, we can replace it with 4, and then pull 5 into the hole where 4 went. We can always do this, and it will preserve the in-order traversal.</p> <p>OK. looking at your code, this is what you want:</p> <pre><code>//in your function else if (/*has 2 nodes*/) { currPtr-&gt;item = extractMin(currPtr-&gt;right, &amp;(currPtr-&gt;right))-&gt;item; } Tree *extractMin(Tree *tree, Tree ** back) { Tree *currPtr = tree; while(currPtr-&gt;left) { back = &amp;(currPtr-&gt;left); currPtr = currPtr-&gt;left; } *back = currPtr-&gt;right; // inorder successor return currPtr; } </code></pre> <p>The ** argument allows us to handle the case where we use the deleted nodes immediate right child:</p> <pre><code> 3 &lt;--deleting this node / \ &lt;--back points to this edge. 2 4 &lt;--extractMin is called on this node and returns this node, \ 5 &lt;-- (*back) now points to this node. </code></pre> <p>Think about the new ExtractMin in 2 cases.</p> <ol> <li>In the first case, we go through the loop at least once. If we had left prevPtr in the code, we would see that after the loop, <code>back == &amp;(prevPtr-&gt;left);</code> (e.g. modifying *back will modify prevPtr->left). So it's the same as your code above.</li> <li>In the second case we don't go through the loop. In this case, <code>back</code> points to a link that we couldn't get in any other way (unless we modified extractMin to start one level higher). </li> </ol> <p>Another way to think about it is that (*back) always points to currPtr (take a moment and check this), so back points to the edge we need to modify if we're removing currPtr.</p>
    singulars
    1. This table or related slice is empty.
    1. POFixing pointers in binary tree delete function (node with 2 children)
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USKyle Butt
    1. USKyle Butt
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI already know that, I even described it in my question that I was doing just that. Or trying to... The problem is not understanding what to do, is how to do it, based on my code and tree structure.
      singulars
      1. PO
      1. USRicardo Amaral
    2. COIt's not immediately clear from your question that's what you're trying to do. I added a code section.
      singulars
      1. PO
      1. USKyle Butt
    3. COSorry, I tried my best at explaining my problem. Your solution is a little trickier... I have to think about it to see if I can understand it.
      singulars
      1. PO
      1. USRicardo Amaral
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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