Solved

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

Posted on 2003-11-17
14
968 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 6
  • 2
14 Comments
 
LVL 15

Expert Comment

by:JakobA
ID: 9763483
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
 
LVL 1

Author Comment

by:dennisryan01
ID: 9763556
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
ID: 9763592
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
Creating Instructional Tutorials  

For Any Use & On Any Platform

Contextual Guidance at the moment of need helps your employees/users adopt software o& achieve even the most complex tasks instantly. Boost knowledge retention, software adoption & employee engagement with easy solution.

 
LVL 7

Accepted Solution

by:
grim_toaster earned 500 total points
ID: 9763656
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
 
LVL 1

Author Comment

by:dennisryan01
ID: 9764161
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
ID: 9764265
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
ID: 9764437
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
 
LVL 1

Author Comment

by:dennisryan01
ID: 9766541
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
 
LVL 1

Author Comment

by:dennisryan01
ID: 9766587
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
ID: 9766728
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
ID: 9769653
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
 
LVL 1

Author Comment

by:dennisryan01
ID: 9771244
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
ID: 9771804
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
 
LVL 1

Author Comment

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

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
This video teaches viewers about errors in exception handling.
Suggested Courses

752 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