• Post Reply Bookmark Topic Watch Topic
  • New Topic

identifying if word in already in binary search tree (recursion) working extremely slow/inaccurately  RSS feed

 
Jesse Aphridion
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am not sure what is wrong with my containsKey() method in the following code. I have a BSTMap class and an inner TreeNode class (every word being a TreeNode key, and the number of times the word appears being the TreeNode value).  Please help!! I think it has to do with the recursion in line 183, but I don't know what I am doing wrong. The comparator is supposed to speed up the amount of time it takes to find the word, because it is not traversing the whole tree.

 
Mark Spencers
Ranch Hand
Posts: 51
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Searching a binary search tree for a specific key can be programmed recursively
We begin by examining the root node. If the tree is null, the key we are searching for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and we return the node. If the key is less than that of the root, we search the left subtree. Similarly, if the key is greater than that of the root, we search the right subtree. This process is repeated until the key is found or the remaining subtree is null. If the searched key is not found after a null subtree is reached, then the key is not present in the tree
 
Jesse Aphridion
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mark Spencers wrote:Searching a binary search tree for a specific key can be programmed recursively
We begin by examining the root node. If the tree is null, the key we are searching for does not exist in the tree. Otherwise, if the key equals that of the root, the search is successful and we return the node. If the key is less than that of the root, we search the left subtree. Similarly, if the key is greater than that of the root, we search the right subtree. This process is repeated until the key is found or the remaining subtree is null. If the searched key is not found after a null subtree is reached, then the key is not present in the tree


I have adjusted my containsKey() method so that it looks like

However, this means that I am attempting to look at a null node before I check to see if it is null, so I get a null pointer exception...
 
Campbell Ritchie
Marshal
Posts: 56545
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Don't call your class XYZ<Key, Value>. Call it XYZ<K, V>. Use single letters for the formal type parameters. You may have to change those names throughout. You might do well to make the Node class a private inner class in the Tree class; there is probably no need to access Nodes outwith the Tree and the Node constitutes a part of the Tree.
Please format your code correctly. You are trying to squeeze methods all onto single lines which might work when you are restricted by the size of a sheet of paper to print it on, but it unnecessary on screen. It also makes the code much more difficult to read.
Have you understood how trees are usually filled? Remember a tree is a standard data structure, so we all know about them. What you do is start with no nodes at all. Every time you add a value, if this is an implementation of a Set, you have two options:-
  • 1: Create a new node
  • 2: Decide you already have the value and ignore it
  • Regard a sorted map implemented as a tree as a special kind of set whose elements are key‑value pairs, so when I said value, you are going to read key‑value pair, and, “decide you already have the value,” becomes, “decide you already have a pair with the same key.” Now your algorithm for adding becomes:-
  • 1: See whether you have a root node at all.
  • 2: If you have no root node, create a root node with that pair. Your addition process is now complete. Don't create a root node until you have a value/pair to put into it.
  • 3: If you already have a root node, see whether the key is same, more or less than that in the root node.
  • 4: That determines whether you stay in this node or go right or go left.
  • 5: If no node exists in the desired direction (== null) create a new node with the new pair. Your addition process is now complete.
  • 6: If you are in a node with the same key, replace the value. Your addition process is now complete.
  • 7: If you are in a node with a different key, repeat the above procedure.
  • You appear to have grasped the recursive algorithm here
    Whenever you create a new Node, its left and right fields will always be null, so don't pass null to its constructor. Simply remove those two parameters; you don't need them.
    Why have you got an ifContain field in the node class? The result of whether a node contains a certain value or not will differ every time you call that method, so a field will contain the last result and that can be incorrect. I think that result ought to be local to the contains method. I am sure you can simplify the formula for calculating whether left contains the key. Something like this:-Please read this Java™ Tutorials section, about the Comparable<T> interface and the Comparator<T> interface. Please find out the following things:-
  • 1: What definition of equality you are using for keys.
  • 2: What it means by, “consistent with equals”.
  • Also decide the following things:-
  • 1: What are you going to do if null is passed as a key?
  • 2: What are you going to do if null is passed as the Comparator argument?
  • 3: Whether I have got key and pair.getKey() in the right order in line 1 of the code I posted.


  • Alternative version of my first two options inspired by the return type of the Collection#add() method:-
  • 1: Create a new node. Return true.
  • 2: Decide you already have the value and ignore it. Return false.
  •  
    Campbell Ritchie
    Marshal
    Posts: 56545
    172
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    My apologies: your formatting is better than I thought. But still not quite right; you said the node class is an inner class, but it doesn't look like an inner class from here.
    Please work out what I meant with all the && and || operators. Work out what would happen if you put the operands in a different order. Work out whether you can use that as a general form for your contains() methods.
     
    Don't get me started about those stupid light bulbs.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!