• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Implementation of the methods remove() and put() in a Dictionary

 
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have to create a dictionary in java using search trees.

I have problems with the methods put() and remove().
Working properly, ie correctly adds a new element and eliminates correctly. But I should improve a few things.

As you can see from the interface, both methods must return an element of type V, that is:

- case put(): returns the previous value associated with key (or null if the key was not associated with any value)
- case remove(): returns the value associated with the key (or null if the key was not present in the dictionary)

I do not understand how come my put method always returns null even though in reality I make him return node.getElement().

Instead, the remove() method does not know how to modify it to make sure it returns the value associated with the key.
If I change the helper method return value in V (instead of Node<K, V>) method does not work anymore...

How can I then edit these two methods?
Thank you very much!

Class SearchTree:


Class Node:


Interface Dictionary:
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I had to break your long lines because they make the code so difficult to read. Use /*…*/ comments for those long comments. Sorry it is awkward to reformat your code.

I'm not sure whether you can work out the remove method by reading the code. Start by drawing a diagram of your tree and draw what happens when you remove something.
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry for the problem of the comments, I'll be more careful next time.

I already tried to do as you say but I could not solve too...
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Alicia,

have you tested your code?

I just put the lot in NetBeans, and it gives me the following errors:

1) SearchTree is not abstract, yet it does not implement the method 'V get(K key)' from
the interface 'Dictionary'.

And indeed, I cannot find it, but then again, I may have made some copy error

2) it complains that the following method



does not return anything

And talking about the method remove(). Campbell already mentioned it.
Suppose you want to remove a Node, that has Nodes to its left and right.
Now, removing that Node would leave these 'children' parentless. So you
must come up with something that repairs this situation.
For instance, if you are to remove the root, then you end up with a loose
left subtree and a loose right subrtree. So, one of the 'roots' of these subtrees
must become the new 'head' root.

Well, that's what I saw so far. Interesting assignment, but not so easy.

Greetz,
Piet
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:hi Alicia,

have you tested your code?

I just put the lot in NetBeans, and it gives me the following errors:

1) SearchTree is not abstract, yet it does not implement the method 'V get(K key)' from
the interface 'Dictionary'.

And indeed, I cannot find it, but then again, I may have made some copy error

2) it complains that the following method



does not return anything

And talking about the method remove(). Campbell already mentioned it.
Suppose you want to remove a Node, that has Nodes to its left and right.
Now, removing that Node would leave these 'children' parentless. So you
must come up with something that repairs this situation.
For instance, if you are to remove the root, then you end up with a loose
left subtree and a loose right subrtree. So, one of the 'roots' of these subtrees
must become the new 'head' root.

Well, that's what I saw so far. Interesting assignment, but not so easy.

Greetz,
Piet




Hello, thanks for the reply. Yes, I tested it before I change the remove() method. I deleted the return value of null because obviously there is no point did so but otherwise it does not compile.
However, leaving the method done this way:

The class compiles and by testing it, both the method (put and remove) work but they return a wrong value...

(Sorry for my bad english)
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Alicia,

as Dutchman, I can't fault your English

I'll try to find out what is happening in all the code (it's quite some code!),
but my first idea is that it would be very handy to include a method

and

That would make it much easier to remove a node, since you get easy
access to the node-to-be-removed, and the parent of that node,
so you can then relatively easy adjust the necessary pointers.
That will make the code in 'remove' much more readable.

Again, you may have implemented this already, I'll check (although that
maybe tomorrow, it's getting late here). And maybe someone else will step in.

Greetz,
Piet
 
Alicia Perry
Ranch Hand
Posts: 66
Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:hi Alicia,

as Dutchman, I can't fault your English

I'll try to find out what is happening in all the code (it's quite some code!),
but my first idea is that it would be very handy to include a method

and

That would make it much easier to remove a node, since you get easy
access to the node-to-be-removed, and the parent of that node,
so you can then relatively easy adjust the necessary pointers.
That will make the code in 'remove' much more readable.

Again, you may have implemented this already, I'll check (although that
maybe tomorrow, it's getting late here). And maybe someone else will step in.

Greetz,
Piet



Thank you so much for the advice. You're right the remove method is a bit complicated.

I did not understand, however, how can I solve my problem of returns using the remove method that you suggested...
 
Piet Souris
Bartender
Posts: 5465
212
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Alicia,

well, starting with a fresh mind.... see how long that lasts.

I've been looking at your V put(K key, V value).
I could not see anything wrong here, so I ran the code with a debugger.
And indeed, if the Key k is not the root key, then the insertion goes
fine, nothing wrong with that, but it returns indeed null.

If you look at the lines 52 and 63 of your original code, you see that
it has:

You see that there is no 'return' in front of this line. So what happens is that
the code goes on from here, skipping all the if's, and ending at the last line of
the method (line 69):

And that's why you get a null as return value.
As said, the process itself works as it should, it was just that the wrong value
was returned.

The remedy is therefore: add 'return' to your lines 52 and 63.
NetBeans is then complaining that line 69 is 'unreachable', so remove that line.

So far from now, I'll have a look at the remove() method asap.

Greetz,
Piet
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
EDIT: Global Health Warning: forget the rest of this reply, for it is utter nonsense! See next reply, please!

Just had a quick look at your 'remove' method.

See in your original listing the lines 77 onwards. This is the code:



In this case, you have found the node that goes with the key 'key'.
Here, you are testing if the node is a leaf, and if so, you decrement size
and you return null.
But, first of all, you should at least return the value of the leaf. So, it should
be something like


But this is the least problem. What if this node has a parent? That parent is still
pointing to your node, so in effect you did not delete it at all. You only have that
the size is now incorrect.

One simple remedy is to include an extra member to your <Node> class, something
like 'boolean isDeleted'.

Then in fact, the only thing you have to do, having found the node to delete, is
to set this boolean to 'true'.
This has some consequences. For instance, when printing the contents of the search tree,
you must inspect the node to see if it is not deleted. When searching for this node,
you must report 'not found' if 'isDeleted' == true. Et cetera.

If that is not what you want, but you want to have a genuine delete, then things get
more complicated.

To picture what must be done, I would like you to draw a binary tree, with rectangles
representing the nodes. Draw it for a couple of layers (not too many, or you run out of
paper).
Make sure that every node has both left and right members, except of course for the leaves.

Now, pick one recctange, somewhere in the middle, and put a big cross througt it.
Then, look at all the pointers. Can you see what pointers must be adjusted?

Imagine you are to remove the root (big cross through the top rectangle).
You see that you now have nothing that points to the left and right subtrees. Yet, a new
root must be there, somehow.

Think about it, and let us know what you think.

Greetz,
Piet

 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:well, starting with a fresh mind.... see how long that lasts.


@Alicia: And I'm going to add a third point of view. Unfortunately, it may not be one you want to hear.

You have (almost certainly) written far too much code without testing properly.

Dictionaries (or, in Java terminology, Maps) are complicated structures, so you can't just bash out code and expect it to all "come together" at the end. You need to implement gradually.

At the very least, in order to work properly, a Dictionary is likely to need:
  • A method for listing its contents in "Node sequence" (see the "PS:" at the end).
  • A method for adding mappings (possibly more than one).
  • A method for getting the value associated with a key.
  • A method for removing mappings (possibly more than one).
  • A method for changing a mapping (your put() method).
  • and if I was doing this, I would deal with each of those in turn (and probably in the order I listed).

    And by "deal with" I don't just mean write until they compile OK; I mean test them until you know absolutely that they work in every single case - including "invalid" ones. And don't move onto the next stage, until you can prove it.

    Now, how closely does your development follow that style?

    If you're interested, you may find the WhereDoIStart page worth reading, because it describes a technique called "stubbing", which I think you may find very useful.

    HIH

    Winston

    PS: The first method I listed above is more of a testing aid than anything, but it's vital if you actually want to know that your code works, which is why I put it first.
     
    Piet Souris
    Bartender
    Posts: 5465
    212
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    hi Alicia,

    well after the nonsense of my previous reply, I must say: I just gave your remove() code
    a thorough test, as best as I could, using a debugger and a single stepper, and I can't fault it.
    No matter what I tried, I got a correct SearchTree back after some deleting! No matter if
    I deleted a leaf or the root.

    Compliments, also on the clear programming style, that made it relatively easy to follow
    what was happening. If I had the power to award a cow for this, I would have given
    a cattle.

    Then the problem of returning that Value of the deleted Node.
    I must admint that I saw no clear direct way of doing that, so I took the indirect
    'brute force' way, so to speak.

    First, I added an extra method, one that I was mentioning earlier.

    After this, I changed the remove method itself slightly:

    I used a small testprogram for this:

    Greetz,
    Piet
     
    Piet Souris
    Bartender
    Posts: 5465
    212
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Winston Gutkowski wrote:
    @Alicia: And I'm going to add a third point of view. Unfortunately, it may not be one you want to hear.

    You have (almost certainly) written far too much code without testing properly.

    (.....)


    As usual, lets agree to disagree, and I hope you don't disagree

    Well, the code is indeed quite complicated, but then again, writing code for
    mutable binary trees is not for the faint hearted.

    As I wrote few minutes ago, I gave the code a thorough test, and I couldn't fault it.
    It worked no matter what I threw at it.
    Now, given the complexity of the code, it would be a miracle if Alicia got all this
    first time right. So I can only assume that she has spent an awfull lot of time testing it
    (and correcting it...).

    But let's await Alicia's answer.

    Greetz,
    Piet
     
    Alicia Perry
    Ranch Hand
    Posts: 66
    Chrome Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hello, I wanted to thank you very much for the advice, you were all very kind!

    I modified the method put () and now it works (thanks Piet Souris).

    I then tested the remove method that is called as auxiliary method the find() method.
    It works in the sense that it returns the correct value but modifies the tree in the wrong way.
    I could see this by printing the tree.

    To test it I used the key of type int and the value associated with key of type String.
    So I made some insertions and I got this tree:


    Then I removed the node with key = 1 and the tree has become this one:


    Then I removed the node with key = 5 and the tree has become this one:


    It seems that the removal modifies the tree properly.

    Instead testing the method of Piet Souris and doing the same tasks, I get this tree by eliminating the node with key = 1 and then the node with key = 5.

    (Has not eliminated any node.)
    and then

    (It has eliminated too many nodes..)

    So I know that there is something wrong...
    Anyway thanks for the help ;)
     
    Piet Souris
    Bartender
    Posts: 5465
    212
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    hi Alicia,

    I don't get it. I used your example:
    package javaranch;



    The tree gives me:

    and I get the expected output:

    debug:
    removed: 1
    removed: 5
    ready

    And the tree is giving me:


    Just what it should be. Note by the way, that the "10" goes to the left of "4",
    since "10" < "4".

    What was it that you tested?

    Greetz,
    Piet
     
    Alicia Perry
    Ranch Hand
    Posts: 66
    Chrome Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Piet, this is strange.. I used this class for testing:




    The display method is this:


     
    Piet Souris
    Bartender
    Posts: 5465
    212
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    hi Alicia,

    it gets more interesting with every reply!

    I'll try your test program in my next reply, what I did right now was to add some convenience methods
    to the class SearchTree. Here goes:

    That prints just the SearchTree in the prefix way, so that we can easily check if
    the order is correct, and that some subtrees are not incorrectly added to the
    wrong (side of a) node.

    I used this testing program:

    and I got, in one of the runs, the following outcomes:

    So you see, the size is incorrect, but I can't fault the outcomes.

    As you see, I don't care what subtrees I have, as long as the infix printorder is okay.
    After having solved the issues, it might be interesting to add some methods that inspect
    the lengths of all the subtrees, to check if all subtrees are about equal in length.
    But that is for later, and only if you think it is of interest.

    So, I will look at your testing code as soon as possible.

    Greetz,
    Piet

    PS: have you considered adding a boolean 'isDeleted' to your Node class?
    The advantage is that it greatly simplifies removing elements.
     
    Bartender
    Posts: 1810
    28
    jQuery Netbeans IDE Eclipse IDE Firefox Browser MySQL Database Chrome Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Piet, you've gone above and beyond in helping Alicia with this one so I've awarded you a cow. Nice work
     
    Piet Souris
    Bartender
    Posts: 5465
    212
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Piet Souris wrote:(....)
    As you see, I don't care what subtrees I have, as long as the infix printorder is okay.
    (...)


    Aaarghhh... I was sure I corrected 'infix' to 'prefix' before clicking the 'submit' button, but
    unfortunately, it's not the first time that my "I am sure..." was a tad on the optimistic side.
    And it won't be the last time, I'm afraid. But then again, who was that great philosofer who wrote
    "I err, therefore I am"?

    @ J. Kevin Robbins
    Thanks! At an earlier cow, I wrote I started feeling like Rowdy Yates, still have that feeling...
     
    Piet Souris
    Bartender
    Posts: 5465
    212
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    hi Alice,

    just ran your testprogram (slightly adjusted to eliminate all possibilities),
    but I see nothing wrong here.
    This is the testprogram I used. I must say, I saw your display() method
    after I was finished, so I included it at the end. You see that your display
    method prints the searchtree sideways, with the root utter left, and there's
    nothing wrong with that.
    Used testprogram:

    And to make this reply nearly endless, here's the output:

    And I must say, I see absolutely nothing wrong.

    So I await your comments.

    Just one question out of curiosity: is this some assignment that you got?
    Because, although this topic is in the "Beginning Java" forum, writing
    generic binary trees is not something I would consider "beginning Java",
    to say it carefully...

    Greetz,
    Piet

     
    Alicia Perry
    Ranch Hand
    Posts: 66
    Chrome Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Piet!
    I found the error and now it works as it should.
    I was wrong to copy the remove() method written by you a few posts above.
    I was stupid and I'm sorry I wasted your time.
    Thank you very much! However I will try to improve the class using your advice ;)
    Thanks again!
     
    Piet Souris
    Bartender
    Posts: 5465
    212
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    hi Alicia,

    you're very welcome and no, you didn't waste my time!
    On the contrary, if you used a copy of my faulty remove(),
    then I'm sorry I wasted YOUR time.

    I found it a pleasure to be of any help, and I myself learned a
    thing or two (or three, or four, or ....)

    So, success with your further labour!

    Greetz,
    Piet
     
    Winston Gutkowski
    Bartender
    Posts: 10780
    71
    Hibernate Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Alicia Perry wrote:I found the error and now it works as it should.
    I was stupid and I'm sorry I wasted your time.


    Never say that. It's what we're here for.

    What I hope Piet has showed you is just how much testing you need to do to prove that a class as complex as a collection will work.

    Winston
     
    Campbell Ritchie
    Marshal
    Posts: 79177
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    You can never test code and prove it works. You can only test and prove it doesn't work.
     
    Winston Gutkowski
    Bartender
    Posts: 10780
    71
    Hibernate Eclipse IDE Ubuntu
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:You can never test code and prove it works.


    Not quite true, but I take your point. What you can do, with good testing however, is "prove" it to a point where you're confident enough to leave it alone and get on with something else.

    Winston
     
    Campbell Ritchie
    Marshal
    Posts: 79177
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Agree. Good testing can show that it works well enough. That is subtly different from proving it works, but if it is “good enough” it is good enough.
     
    reply
      Bookmark Topic Watch Topic
    • New Topic