Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 989
  • Last Modified:

incrementing a count in a binary search tree insert word count method

I am searching a string of text for word, putting the words in a bst, and if the word reappears, tring to increment a count in the node. Here is the method and would appreciate advice. The node should keep the word and the count as well as left and right.
Here is some of the code, and I have high lited where it is not operating as I want. Advice would be appreciated. Thanks

class BST
{
      BSTNode root;
                   Integer count, test, value;

      public BST()
      {
               root = null;
      }

      public void insert(String newVal)
      {
            BSTNode newNode = new BSTNode(newVal);

      if (root == null){
                      root = newNode;
                  root.count = 1;
                  System.out.println(root.info+"("+root.count+")");
      }

                      else if (newVal.equals(root.info)){
                      root.count+=1;
                      System.out.println(root.info+"("+root.count+")");              
                      }

      else
      {
            BSTNode p, prev;
            p = root;
            prev = p;
//****** this section does not work as I (expect)(want)*******
                                       while (p != null)
                 {
                  prev = p;

                                           if (newVal.equals(p.info))
                                       {
                                          p.count+=1;
                                System.out.println(p.info+"("+p.count+")");
                                               }
                                           if (newVal.compareTo(p.info) < 0)
                        p = p.left;
                        else
                        p = p.right;
                   }

            if (newVal.compareTo(prev.info) < 0)
                        prev.left = newNode;
                  else
                        prev.right = newNode;
//************************************************            }
      }

}

class BSTNode
{
        String info;
        int count;
        BSTNode left, right;

      public BSTNode(String newVal)
      {
            info = newVal;
                                int count = 1;
            right = null;
            left = null;
      }
}

 
0
dennisryan01
Asked:
dennisryan01
  • 6
  • 6
  • 2
1 Solution
 
JakobACommented:
If you write a few comments in your code we (and you) wil have a better chance of knowing what your are trying to do.

In this sort of algorithm the object references (prev and p) are key. they contain different objects at different times through the iteration, so a debug method that often work is to track them.

say to yourself  "I am now tracking 'prev'!"   (later you track 'p' the same way)
go thrugh your code and every place 'prev' is used consider what you are doing there and why
     what value are you setting in prev?
     what will it be used for?
     should it be set earlier?
     are you setting it too early? (losing a reference you will need later)
     what value are you getting from prev here?
     is it the right one?
     etc.
it is ok to take notes while doing this :-))

regards JakobA
0
 
dennisryan01Author Commented:
good point. The code is hard to read (and it would help if I had a better handle on what I was doing) It will take me a couple of hours until I can get back to it. thks
0
 
grim_toasterCommented:
What do you mean by not operating as you want?  There is one small problem, your counter variable in your BSTNode class is being initialised to 0, not the 1 as you would think by quickly glancing at the constructor, as the constructo is:

     public BSTNode(String newVal)
     {
          info = newVal;
                                int count = 1;
          right = null;
          left = null;
     }

When it should be:

     public BSTNode(String newVal)
     {
          info = newVal;
          count = 1;
          right = null;
          left = null;
     }
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
grim_toasterCommented:
Also, there are a few other things you could do to improve your code, for example, do you want to handle the same words but different case, also your call to compareTo could be used once to also cater for your equals (avoids the same checks twice), by comparing to 0.  But I think I know what your problem is, usually these sort of tree node approach's are carried out using some form of recursive call (method calls itself) to go through the list, your approach will work, but I'm presuming that if the word exists you only want to increment a counter, not create a new instance of it?  In which case, when you increment the counter, you would probably want to exit out of the method:

 if (newVal.equals(p.info))
                                     {
                                         p.count+=1;
                                System.out.println(p.info+"("+p.count+")");
                                return;
                                             }

Although not the most elegant way to do things, it should work.  Also, whilst you are commenting your code, it might be helpful to distinguish between you System.out calls, as they all look identical, so how would you know which one is called?
0
 
dennisryan01Author Commented:
grim_toaster
I think you hit exactly what I want to do, exit out, but my logic does not support it.  I could probably have used flags as well. Will try later to see if it executes, and let you know.  

If it were elegant, how does it look?
0
 
grim_toasterCommented:
Your logic does support it, the return statement can be used to exit out of the method.  The reason it's not perfectly elegant is that it's best to only have one exit point from a method as it makes the code more readable.  As for the recursive thing, it would depend upon how large your tree will get, your method is fine, as recursion is only really effective for finite sized trees (as you can get stack problems).

I'll see if I can knock together a quick example for you.
0
 
grim_toasterCommented:
Here's some code for you to think over anyway:

import java.util.StringTokenizer;

public class Thing
{
    public static void main(String args[])
    {
        String text = "the quick brown fox jumped over the lazy old cat quick the jumped";
        StringTokenizer st = new StringTokenizer(text);
        Thing tmp = new Thing();
       
        while (st.hasMoreTokens())
        {
            String next = st.nextToken();
            tmp.insert(next);
        }
    }

    BSTNode root = null;

    public void insert(String newVal) {
        if (root == null) {
            root = new BSTNode(newVal);
        }
        else {
            BSTNode p = root;

            while (p != null) {
                int compared = newVal.compareToIgnoreCase(p.info);

                if (compared == 0) {
                    p.count++;
                    break;
                }
                else if (compared < 0) {
                    if (p.left == null) {
                        p.left = new BSTNode(newVal);
                        break;
                    }
                    else {
                        p = p.left;
                    }
                }
                else {
                    if (p.right == null) {
                        p.right = new BSTNode(newVal);
                        break;
                    }
                    else {
                        p = p.right;
                    }
                }
            }
        }
    }
}

class BSTNode
{
    final String info;
    int count = 1;
    BSTNode left;
    BSTNode right;

    public BSTNode(String newVal)
    {
        this.info = newVal;
    }    
}
0
 
dennisryan01Author Commented:
excellent  "return" worked

almost finished here, but what makes this wrong?

class BSTNode
{
        String info;
        int count;
        BSTNode left, right;

     public BSTNode(String newVal)
     {
          info = newVal;
          int count = 1;  <- what did this do

          right = null;
          left = null;
     }
}
0
 
dennisryan01Author Commented:
grim_toaster

(opps   pushed wrong button )

almost finished here, but what makes this wrong?

class BSTNode
{
        String info;
        int count;
        BSTNode left, right;

     public BSTNode(String newVal)
     {
          info = newVal;
          count = 1;     <- what did this do
          int count=1;   <-instead of this(besides work properly, I mean)
          right = null;
          left = null;
     }
}
0
 
JakobACommented:
when you write
     int count
you are declaring a new wariable to live in the current scope. ie, you ar creating a variable local to the BSTnode constructor. An entirely different variable than the  count  that is declared as a variable outside the constructor.
0
 
grim_toasterCommented:
Exactly!

Also, as a seperate point, if you want to be able to do this sort of thing just using the standard libraries. you can use the code below, considerably smaller and easier to maintain, and also less likely to have a bug in there (the stadard API's are tried and tested methods!), then you can use the TreeMap to get a list of the keys (keySet()), get an iterator on it, to go through the list:

    TreeMap treeMap = new TreeMap();

    public void insert(String newVal) {
        Object out = treeMap.get(newVal);
       
        if (out != null) {
            ((BSTNode) out).count++;
        }
        else {
            treeMap.put(newVal, new BSTNode());
        }
    }

    private class BSTNode {
        int count = 1;    
    }
0
 
dennisryan01Author Commented:
Thank you for your help yesterday.  Unfortunately we are doing it the hard way, and now that I can increment, I want to search the tree to find the info string with the greatest length.  I can search the tree for the highest count (most often used word) successfully, but am in trouble on recursively searching and returning the string.  It is a separate question which I will be posting in about 30 minutes.

again, thanks for your time and assistance.
0
 
grim_toasterCommented:
Not a problem!  But to actually search for the largest String, the code to iterate through the list would be no different from what you would have used to get the highest count, the only difference would be that you are using a different item to search on, so instead of

if (obj.count > highestCount)

you would use:

if (obj.info.length() > highestLength)
0
 
dennisryan01Author Commented:
of course, I did it the highest count differently
posting question in a minute
0

Featured Post

Ask an Anonymous Question!

Don't feel intimidated by what you don't know. Ask your question anonymously. It's easy! Learn more and upgrade.

  • 6
  • 6
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now