9 Replies Latest reply: Apr 25, 2009 11:21 PM by 807588 RSS

    Need help with some code ... Searching a tree and inserting data

    807588
      I'm trying to write code for the addIterative method below.
      My problem is that I also need to search the list or node to see if the word exists.

      The method add(word,line,position,iterative) validates the parameters; and, in order to update the tree and/or any relevant linked-list, calls either the incomplete method addIterative(word,line,position) or the incomplete method addRecursive(word,line,position). Note the following: if the word is not contained currently in the tree, then all of the (word,line,position) triplet needs to be added to the data structure; otherwise, only the (line,position) pair needs to be added to the data structure. The result must be the same regardless of the algorithmic strategy employed.

      any suggestions would be greatly appreciated, new to java, and very lost.

      regards,
      Jimmy


      /**
      * Write a description of class Tree091 here.
      *
      * @author (your name)
      * @version (a version number or a date)
      */
      class Tree091 /*(i.e., WordTree)*/
      { private char[] word=null;
      private List091 list=null;
      private Tree091 precursor=null; /*(i.e., leftSubTree)*/
      private Tree091 successor=null; /*(i.e., rightSubTree)*/
      public Tree091(char[] word,
      List091 list,
      Tree091 precursor, /*(i.e., lexicographically < word)*/
      Tree091 successor) /*(i.e., lexicographically > word)*/
      { if (word==null) return;
      if (word.length<1) return;
      if (list==null) return;
      this.word=word;
      this.list=list;
      this.precursor=precursor;
      this.successor=successor;
      }
      public void add(char[] word,
      int line,
      int position,
      boolean iterative)
      { if (word==null) return;
      if (word.length<1) return;
      if (line<0) return;
      if (position<0) return;
      if (iterative)
      this.addIterative(word,line,position);
      else
      this.addRecursive(word,line,position);
      }
      private void addIterative(char[] word,
      int line,
      int position)
      {
      /* something goes here*/





      }
      private void addRecursive(char[] word,
      int line,
      int position)
      {
      /* something goes here*/
      }
      private int compare(char[] array1,
      char[] array2)
      { if (array1==null) return -2;
      if (array2==null) return -2;
      int length1=array1.length;
      if (length1==0) return -2;
      int length2=array2.length;
      if (length2==0) return -2;
      int minLength=length1<length2?length1:length2;
      for (int i=0; i<minLength; i++)
      { if (array1[i]<array2) return -1;
      if (array1[i]>array2[i]) return 1;
      }
      return length1==length2 ? 0 : length1<length2 ? -1 : 1;
      }
      public boolean contained(char[] word)
      { int compare=compare(this.word,word);
      if (compare==1&&this.precursor!=null)
      return this.precursor.contained(word);
      if (compare==0) return true;
      if (compare==-1&&this.successor!=null)
      return this.successor.contained(word);
      return false;
      }
      public int listNodeCount(boolean iterative)
      {
      /* something goes here*/
      return 24;
      }
      public int maximumWordLength(int currentLength)
      {
      /* something goes here*/
      return 25;
      }
      public String toString()
      { String string="";
      if (this.precursor!=null) string+=this.precursor;
      string+="\""+(new String(this.word))+"\""+this.list;
      if (this.successor!=null) string+=this.successor;
      return string;
      }
      public int treeNodeCount()
      {
      /* something goes here*/
      return 26;
      }
      public String wordArray(int length)
      {
      /* something goes here*/
      return "hey hey wordarray";
      }
      }
        • 1. Re: Need help with some code ... Searching a tree and inserting data
          JoachimSauer
          Hy and welcome to the forums.

          You seem to have missed two minor points in your post:

          1.) When you post code, you shoud always use the CODE-Button (1. copy-and-paste code, 2. select the code, 3. press "CODE" just above the text field).
          2.) You didn't write an actual question.
          • 2. Re: Need help with some code ... Searching a tree and inserting data
            807588
            My question in case anyone missed it is:
            how do I write the additerative method.
            I have no idea how to go about doing this.

            thanks,
            Jimmy
            • 3. Re: Need help with some code ... Searching a tree and inserting data
              JoachimSauer
              allergy01 wrote:
              My question in case anyone missed it is:
              how do I write the additerative method.
              "How do I write ...?" alone is not really a good question.

              What have you tried?

              Answering those question should help you get started:

              * What should the method do. Describe it in detail! What are its preconditions and what should be true afterwards.
              * What are the seprate steps of doing it? (Forget about Java for a second, describe the steps you'd do "manually")
              * How can I translate each single step into Java code?
              • 4. Re: Need help with some code ... Searching a tree and inserting data
                807588
                ah, I understand you now.

                I have the following method, that accpets the following parameters, that I need to write:
                private void addIterative(char[] word, int line, int position)
                I need to search the tree for the parameter received "word", if the word exists, then only the (line,position) pair needs to be added to the data structure. If the word is not contained currently in the tree, then all of the (word,line,position) triplet needs to be added to the data structure.

                But I'm not sure how to do this.

                The following pieces of code are roughly how it needs to be done, but the node name is wrong, but I'm not sure how to apply this to my existing code above:
                  { //find which (if any) node of this SLL contains an element
                    //equal to target; return a link to the matching node or null
                    for (SLLNode curr = this.first;
                         curr != null; curr = curr.succ)
                    { if (word.equals(curr.element))
                      // insert (line, position) into tree
                else
                // insert (word,line,position);
                         }
                      }
                
                //insert could be something like this
                { // Insert elem at a given point in this SLL,
                  // either after the node pred,
                  // or before the first node if pred is null.
                // again SLLNode is the wrong name for the SLL (single linked list)
                // but I cant figure out what it should be from the original code above.
                  SLLNode ins = new SLLNode(elem, null);
                  if (pred == null)
                  { ins.succ = this.first;
                    this.first = ins;
                  }
                 else
                 { ins.succ = pred.succ;
                   pred.succ = ins;
                  }
                }
                Any ideas?

                cheers,
                Jimmy
                • 5. Re: Need help with some code ... Searching a tree and inserting data
                  JoachimSauer
                  allergy01 wrote:
                  ah, I understand you now.

                  I have the following method, that accpets the following parameters, that I need to write:
                  private void addIterative(char[] word, int line, int position)
                  I need to search the tree for the parameter received "word", if the word exists, then only the (line,position) pair needs to be added to the data structure. If the word is not contained currently in the tree, then all of the (word,line,position) triplet needs to be added to the data structure.
                  Ok, that's better.
                  But I'm not sure how to do this.
                  Do you know how a Tree works? Can you describe that quickly?
                  The following pieces of code are roughly how it needs to be done, but the node name is wrong, but I'm not sure how to apply this to my existing code above:
                  That's not your code. So ignore it, you should do your homework on your own.

                  I wanted you to describe the necessary steps in english. Let me give you an example:

                  * find the correct position
                  * if there's no existing node for the word create it
                  * add the line/position to that nodes list

                  That is a very high-level overview over what you have to do.

                  Now you try explaining how each of those steps could be done, again in simple english.
                  • 6. Re: Need help with some code ... Searching a tree and inserting data
                    807588
                    Hello Joachim,
                    I've read over all your comments and I've realised I shouldn't have started another post. You were trying to help me but I didn't understand.
                    If it's ok with you I'd like to try again. I know I can figure this out with a little guidance.

                    ok, to find the correct position.
                    * we would need to search the tree
                    * assuming it's a binary search tree
                    * we compare the word to the top most node
                    * if it's higher or lower determines whether we look to the right or left of the tree
                    * we for loop through the tree (iteratively or recursively, assignment requires both) until we find the word or have searched all nodes.
                    * if we find the word we insert the line position into the corresponding nodes list
                    * with the list insertion, I dont think it matters how we do that, because it does not matter if the line and position values are at the start or end of the list, assuming many values, as loingas they can be associated with the correct node is all that matters.
                    * If we dont find the word then we must seacrh the tree for the correct position to insert it
                    * this we would do by searching for the word, this should lead to a null link, we can then replace that link to anode containing the word.
                    * or by setting parent to null, set current to the bst's root
                    * then looping through:
                    - if current is null, replace null link which curent had with newly created leaf node with word
                    - if word is equal to current then terminate // word exists
                    - if word is less than current, set parent to current and set current to currents left child
                    - if word is greater than current, set parent to current and set current to currents right child
                    - then need to insert line position for this node in the List

                    Good stuff Joachim, this is helping me understand whats going at least!!!!
                    Thanks.

                    ok, now what should I do?

                    Jimmy

                    Edited by: allergy01 on Apr 24, 2009 8:26 PM
                    • 7. Re: Need help with some code ... Searching a tree and inserting data
                      800308
                      allergy01 wrote:
                      Hello Joachim,
                      I've read over all your comments and I've realised I shouldn't have started another post.
                      You have to admit it was pretty funny though... "Help me Obe Wan!", and who should appear but the very man himself... LMAO.

                      Hint: Use &#123;code} tags when posting pseudo-code, bullet lists, etc... it allows you to indent stuff...
                      to insert an entry(word,line,position) into the binary search we would need to search by:
                      1. set the current node to the top most node (aka the root)
                      2. compare this word to the current node
                          if it's equal then we append the (line,position) to this node's list, and we're done; else
                          if it's higher then look right; otherwise
                          it's lower, so look left
                      
                      
                      or have searched all nodes.
                      Q: How the hell do we know that the word isn't in the tree?      Ergo: how do we know when we've "searched all nodes"        * Is it left is higher && right is lower than word, or        * when left and right are both null? or what?      I honestly can't recall off the top of my head, and I'm too lazy to knutt-it-out.
                      HTH. Keith.
                      • 8. Re: Need help with some code ... Searching a tree and inserting data
                        JoachimSauer
                        allergy01 wrote:
                        Hello Joachim,
                        I've read over all your comments and I've realised I shouldn't have started another post. You were trying to help me but I didn't understand.
                        If it's ok with you I'd like to try again. I know I can figure this out with a little guidance.
                        Yes, sure. Let's do this.
                        ok, to find the correct position.
                        * we would need to search the tree
                        * assuming it's a binary search tree
                        * we compare the word to the top most node
                        * if it's higher or lower determines whether we look to the right or left of the tree
                        * we for loop through the tree (iteratively or recursively, assignment requires both) until we find the word or have searched all nodes.
                        Uhm ... almost correct. You don't do any "for loop" in this example. A for loop is usually used when you know exactly how many iterations you'll do before entering the loop. That's not the case here.

                        For the recursive version you don't need any loop at all (you're using recursion instead).

                        For the iterative version, I'd probably use a while-loop.

                        Also note: you don't need to search all the node to see if a word is in the tree. You only need to search down one "path" in the tree where the word should have been. And if it's not there, then you don't need to look in the rest of the tree.
                        * if we find the word we insert the line position into the corresponding nodes list
                        * with the list insertion, I dont think it matters how we do that, because it does not matter if the line and position values are at the start or end of the list, assuming many values, as loingas they can be associated with the correct node is all that matters.
                        * If we dont find the word then we must seacrh the tree for the correct position to insert it
                        Almost correct: when you see that there is no correct node, then you already know where you need to insert the node. No need to search again.
                        * this we would do by searching for the word, this should lead to a null link, we can then replace that link to anode containing the word.
                        * or by setting parent to null, set current to the bst's root
                        * then looping through:
                        - if current is null, replace null link which curent had with newly created leaf node with word
                        - if word is equal to current then terminate // word exists
                        - if word is less than current, set parent to current and set current to currents left child
                        - if word is greater than current, set parent to current and set current to currents right child
                        - then need to insert line position for this node in the List

                        Good stuff Joachim, this is helping me understand whats going at least!!!!
                        Thanks.
                        You're welcome. It looks good so far.
                        ok, now what should I do?
                        You can start translating that into Java code. You might possibly specify some things in more detail, but that's a solid point to start coding.

                        Also try to find out if any parts are easily extracted into their own methods (inserting into the list for example).
                        • 9. Re: Need help with some code ... Searching a tree and inserting data
                          807588
                          hey,
                          ok, wow, that was intense, my brain hurts!!!!
                          And now I've got to go do a graduate program test, argh!!!
                          :)
                          A problem I keep getting is trying to figure out what my lecturer is doing in the start of the Tree091 class,
                          that is, I can see that he is constructing the list and tree but it appears that he is doing it all at the same time, and I'm getting confused with what actually gets inserted into the list, and do we insert the word, line and position, or just the line and position?
                          Also, I didnt use a 'while loop', I'm not sure how, but I found a 'for loop' in the text book, what do you think of it? Is it ok for now?
                          And I'm getting an error at this line:
                          Tree091 ins = new Tree091(char[] word); // getting error '.class' expected here
                          any ideas?

                          heres what I've got so far:
                          private void addIterative(Comparable char[] word,int line, int position){
                          // Insert char[] word into the this BST     
                               int direction = 0;     
                               Tree091 parent = null, curr = root;
                               for (;;) {     
                                    if (curr == null) {
                                         Tree091 ins = new Tree091(char[] word); // getting error '.class' expected here
                                         // word found so we call insertList method
                                         insertList091(line, position, List091 precursor);
                                         if (root) == null)
                                              root = ins;
                                         else if (direction < 0)     
                                              parent.left = ins;
                                         else // direction > 0
                                              parent.right = ins;
                                         return;
                                    }
                                    direction = elem.compareTo(curr.element);
                                    if (direction == 0)
                                         return;
                                    parent = curr;
                                    if (direction < 0)
                                         curr = curr.left;
                                    else // direction > 0
                                         curr = curr.right;
                               }
                          }
                          And heres an attempt at the insertList method
                          private void insertList(char[] word, int line, int position, List091 precursor){
                          // Insert line and position at a given point in this List091, either after the node
                          // precursor, or before the first node if precursor is null
                          // Looking at assignment question we may need a double linked list
                               List091 ins = new List091 (char[] word, line, position, null);
                               if precursor == null) { //insert before first node (if any).
                                    ins.successor = first;
                                    first = ins;
                               } else {
                                    ins.successor = precursor.successor;
                                    precursor.successor = ins;
                               }
                          }
                          How far off am I Joachim?

                          cheers,
                          Jimmy

                          ps. heres the tree091 class again:

                          class Tree091 /*(i.e., WordTree)*/
                          { private char[] word=null;
                            private List091 list=null;
                            private Tree091 precursor=null; /*(i.e., leftSubTree)*/
                            private Tree091 successor=null; /*(i.e., rightSubTree)*/
                            public Tree091(char[] word,
                                           List091 list,
                                           Tree091 precursor, /*(i.e., lexicographically < word)*/
                                           Tree091 successor) /*(i.e., lexicographically > word)*/
                            { if (word==null) return;
                              if (word.length<1) return;
                              if (list==null) return;
                              this.word=word;
                              this.list=list;
                              this.precursor=precursor;
                              this.successor=successor;
                            }
                            public void add(char[] word,
                                            int line,
                                            int position,
                                            boolean iterative)
                            { if (word==null) return;
                              if (word.length<1) return;
                              if (line<0) return;
                              if (position<0) return;
                              if (iterative)
                                this.addIterative(word,line,position);
                              else
                                this.addRecursive(word,line,position);
                            }
                            private void addIterative(char[] word,
                                                      int line,
                                                      int position)
                            {
                              /* students to complete */
                            }
                            private void addRecursive(char[] word,
                                                      int line,
                                                      int position)
                            {
                               /* students to complete */
                            }
                            private int compare(char[] array1,
                                                char[] array2)
                            { if (array1==null) return -2;
                              if (array2==null) return -2;
                              int length1=array1.length;
                              if (length1==0) return -2;
                              int length2=array2.length;
                              if (length2==0) return -2;
                              int minLength=length1<length2?length1:length2;
                              for (int i=0; i<minLength; i++)
                              { if (array1<array2[i]) return -1;
                          if (array1[i]>array2[i]) return 1;
                          }
                          return length1==length2 ? 0 : length1<length2 ? -1 : 1;
                          }
                          public boolean contained(char[] word)
                          { int compare=compare(this.word,word);
                          if (compare==1&&this.precursor!=null)
                          return this.precursor.contained(word);
                          if (compare==0) return true;
                          if (compare==-1&&this.successor!=null)
                          return this.successor.contained(word);
                          return false;
                          }
                          public int listNodeCount(boolean iterative)
                          {
                          /* students to complete */
                          }
                          public int maximumWordLength(int currentLength)
                          {
                          /* students to complete */
                          }
                          public String toString()
                          { String string="";
                          if (this.precursor!=null) string+=this.precursor;
                          string+="\""+(new String(this.word))+"\""+this.list;
                          if (this.successor!=null) string+=this.successor;
                          return string;
                          }
                          public int treeNodeCount()
                          {
                          /* students to complete */
                          }
                          public String wordArray(int length)
                          {
                          /* students to complete */
                          }
                          }
                          Edited by: allergy01 on Apr 25, 2009 9:19 PM
                          
                          Edited by: allergy01 on Apr 25, 2009 9:20 PM