Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am developing an academic project about graph and tree theory.I searched a lot but I didn't find a clear answer. In a part of project we want to delete some nodes from tree for example we want to delete nodes A and B.I want to know that if we Delete A and then B does It give us exactly the same tree that We will produce when We Delete B and then A and if yes is there any proof or anything that can make sure us about that.

share|improve this question
    
What do you mean exactly by deleting? What kind of search tree are you using (balanced?, keys in all nodes or just the leaves?) –  A.Schulz Nov 25 '12 at 7:49
    
a simple binary search tree keys in all nodes(include leaves).being balance is not required. –  CoderInNetwork Nov 25 '12 at 12:27
    
deleting means that for example detele('4') removes node with key 4 from our tree. –  CoderInNetwork Nov 25 '12 at 12:30
add comment

1 Answer 1

finally i will find the answer! Deletion (in general) is not commutative. Here is a counterexample:

    4
   / \
  3   7
     /
    6

What if we delete 4 and then 3?

When we delete 4, we get 6 as the new root:

   6
  / \
 3   7

Deleting 3 doesn't change the tree, but gives us this:

  6
   \
    7

What if we delete 3 and then 4?

When we delete 3 the tree doesn't change:

 4
  \
   7
  /
 6

However, when we now delete 4, the new root becomes 7:

  7
 /
6

The two resulting trees are not the same, therefore deletion is not commutative.

reference and more details : http://stackoverflow.com/questions/2990486/deletion-procedure-for-a-binary-search-tree

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.