Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It seems to me that the counterexample shown in Vivin's answer is the sole case of non-commutativity, and that it is indeed eliminated by the restriction that only nodes with two children can be deleted. </p> <p>But it can also be eliminated if we discard what appears to be one of Vivin's premises, which is that we should traverse the right subtree as little as possible to find any acceptable successor. If, instead, we always promote the smallest node in the right subtree as the successor, regardless of how far away it turns out to be located, then even if we relax the restriction on deleting nodes with fewer than two children, Vivin's result <PRE> 7 / 6 </PRE> is never reached if we start at </p> <p><PRE> 4 / \ 3 7 / 6 </PRE></p> <p>Instead, we would first delete 3 (without successor) and then delete 4 (with 6 as successor), yielding <PRE> 6 \ 7 </PRE></p> <p>which is the same as if the order of deletion were reversed.</p> <p>Deletion would then be commutative, and I think it is always commutative, given the premise I have named (successor is always smallest node in right subtree of deleted node).</p> <p>I do not have a formal proof to offer, merely an enumeration of cases:</p> <ol> <li><p>If the two nodes to be deleted are in different subtrees, then deletion of one does not affect the other. Only when they are in the same path can the order of deletion possibly affect the outcome.</p> <p>So any effect on commutativity can come only when an ancestor node and one of its descendants are both deleted. Now, how does their vertical relationship affect commutativity?</p></li> <li><p><strong>Descendant in the left subtree of the ancestor.</strong> This situation will not affect commutativity because the successor comes from the right subtree and cannot affect the left subtree at all. </p></li> <li><p><strong>Descendant in the right subtree of the ancestor.</strong> If the ancestor's successor is always the smallest node in the right subtree, then order of deletion cannot change the choice of successor, no matter what descendant is deleted before or after the ancestor. Even if the successor to the ancestor turns out to be the descendant node that is also to be deleted, that descendant too is replaced with the the next-largest node to it, and that descendant cannot have its own left subtree remaining to be dealt with. So deletion of an ancestor and any right-subtree descendant will always be commutative.</p></li> </ol>
    singulars
    1. This table or related slice is empty.
    1. PODeletion procedure for a Binary Search Tree
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USЯegDwight
    1. USbrannerchinese
    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. COThe example of non-commutativity that I provided is based on the standard deletion algorithm; when a node has only one child, it can be deleted and replaced with that child node. In my case 4 has only one child (7) and so can be replaced by that child. This is because we don't really need to traverse the entire height of the sub-tree (which costs `O(log n)` in the worst case) unless the node has two children. But with your premise, it is true that deletion would be commutative but with an increased performance-cost.
      singulars
      1. PO
      1. USVivin Paliath
 

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