Solved

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

Posted on 2003-11-17
14
943 Views
Last Modified: 2010-03-31
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
Comment
Question by:dennisryan01
  • 6
  • 6
  • 2
14 Comments
 
LVL 15

Expert Comment

by:JakobA
Comment Utility
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
 

Author Comment

by:dennisryan01
Comment Utility
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
 
LVL 7

Expert Comment

by:grim_toaster
Comment Utility
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
 
LVL 7

Accepted Solution

by:
grim_toaster earned 500 total points
Comment Utility
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
 

Author Comment

by:dennisryan01
Comment Utility
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
 
LVL 7

Expert Comment

by:grim_toaster
Comment Utility
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
 
LVL 7

Expert Comment

by:grim_toaster
Comment Utility
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
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

Author Comment

by:dennisryan01
Comment Utility
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
 

Author Comment

by:dennisryan01
Comment Utility
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
 
LVL 15

Expert Comment

by:JakobA
Comment Utility
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
 
LVL 7

Expert Comment

by:grim_toaster
Comment Utility
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
 

Author Comment

by:dennisryan01
Comment Utility
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
 
LVL 7

Expert Comment

by:grim_toaster
Comment Utility
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
 

Author Comment

by:dennisryan01
Comment Utility
of course, I did it the highest count differently
posting question in a minute
0

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Suggested Solutions

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now