8 Replies - 1471 Views - Last Post: 11 September 2012 - 09:10 AM Rate Topic: -----

#1 JavaLilly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 05-September 12

BST Lazy Deletion

Posted 10 September 2012 - 02:58 PM

My question is about lazy deletion. This is a homework question.

I have a binary search tree that works. If I wanted to implement lazy deletion, does it make sense in java (since I
know the point of lazy deletion is not to actually remove, but to "flag" the node as used) to simply change the data
in the node to a string called flag? Am I allowed to do that. So, basically, if my node has int data, can I just change
the data in the node to string and write "flagged"?

That is really the only way I can see going about it. Are there any other approaches.

Is This A Good Question/Topic? 0
  • +

Replies To: BST Lazy Deletion

#2 natecat  Icon User is offline

  • D.I.C Head

Reputation: 53
  • View blog
  • Posts: 225
  • Joined: 19-December 11

Re: BST Lazy Deletion

Posted 10 September 2012 - 03:31 PM

It would be better to have a certain number that represents flagged such as -12639
Was This Post Helpful? 1
  • +
  • -

#3 JavaLilly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 05-September 12

Re: BST Lazy Deletion

Posted 10 September 2012 - 03:50 PM

Wow, I can't believe I didn't think about that. That is a lot less work.
Thanks
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2117
  • View blog
  • Posts: 3,242
  • Joined: 21-June 11

Re: BST Lazy Deletion

Posted 10 September 2012 - 04:07 PM

View Postnatecat, on 11 September 2012 - 12:31 AM, said:

It would be better to have a certain number that represents flagged such as -12639


That only works if that number can not naturally occur as a value. If all possible ints can be used as regular values, you can't do that.

I don't see why you wouldn't just add a boolean variable to your nodes that signifies whether the node is flagged or not.
Was This Post Helpful? 2
  • +
  • -

#5 JavaLilly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 05-September 12

Re: BST Lazy Deletion

Posted 10 September 2012 - 05:11 PM

I can't do that because I'm trying to keep track of the occurences of each value, not just whether or not it is there.
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2117
  • View blog
  • Posts: 3,242
  • Joined: 21-June 11

Re: BST Lazy Deletion

Posted 10 September 2012 - 05:17 PM

Could you rephrase that? I'm afraid I don't follow.
Was This Post Helpful? 0
  • +
  • -

#7 JavaLilly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 05-September 12

Re: BST Lazy Deletion

Posted 10 September 2012 - 05:30 PM

Sorry. You said that you didn't see why I don't just add a boolean value to see if its flagged or not. Well, I need to keep track of the number of times a certain element appears in the tree. if I have a boolean value, I would need to keep track of that and the number times it occurs. I don't want to do that necessarily.

So for example, if i put five occurs two times, I want my program to return that it occurs two times not just "true".
Was This Post Helpful? 0
  • +
  • -

#8 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2117
  • View blog
  • Posts: 3,242
  • Joined: 21-June 11

Re: BST Lazy Deletion

Posted 10 September 2012 - 05:47 PM

I don't understand. You want to iterate over the tree and find out how many (non-deleted - I assume) nodes have a given value? So simply do that and ignore nodes whose deleted flag is true. Why would that mean that the result of your count method would suddenly be true rather than a number?

Or are you saying you want to represent duplicated values in the tree as one node with a counter? If that's what you're doing, then why not just set the counter to 0 to indicate that a node is deleted? That way you need neither a special value to indicate deleted nodes nor a boolean flag.
Was This Post Helpful? 2
  • +
  • -

#9 JavaLilly  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 05-September 12

Re: BST Lazy Deletion

Posted 11 September 2012 - 09:10 AM

"Or are you saying you want to represent duplicated values in the tree as one node with a counter? If that's what you're doing, then why not just set the counter to 0 to indicate that a node is deleted? That way you need neither a special value to indicate deleted nodes nor a boolean flag."

Right and right... I was just thinking too much and confusing myself.

I wanted to keep track of duplicate nodes and then as they were removed, if the count became zero, it became "flagged".

So...instead, the simplest thing to do was create a counter in the Node class and go from there.

Thank you for your help and sorry for any confusion.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1