[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Splay trees and compareTo

Posted on 2004-11-06
26
Medium Priority
?
424 Views
Last Modified: 2012-05-05
Three questions. 1 and 3 should be very simple, and that's why i am not breaking them up into three q's.

//QUESTION 1 (Line marked below)
I get this error:
The method compareTo(Object) is undefined for the type Object

why? _root.getKey returns the key value in the root (type TreeNode), which is type Object, the same as key, and the value that compareTo expects.

//QUESTION 2 (Line marked below)
I have a splay method which must have the contract splay(TreeNode t), not splay(Object t).  So, assuming the TreeNode with the _key value == key, how do I get this TreeNode so that I can pass it to the splay method? As I am writing this, I realize I have also created a find(Object key) method which looks like this:
        public Object find(Object key){
            if (_root == null) return null;
            splay(key);
              if(_root.getKey().compareTo(key) != 0) return null;
              return _root.getKey();
      }
but I am unable to make the mental connection as to how I might use find (if possible) to get a TreeNode existing in my splayTree that I could pass to my splay(TreeNode t) method.  Suggestions??


//QUESTION 3
What does this mean as a for loop?
for (;;){//THIS LINE
//Loop contents here
}

The Code:

      public Object remove(Object key){
            TreeNode x;
            splay(key);                   //QUESTION 2
            if (key.compareTo(_root.getKey()) == 0) {   //QUESTION 1
            // Now delete the root
            if (_root.getLeft() == null) {
                _root = _root.getRight();
            } else {
                x = _root.getRight();
                _root = _root.getLeft();
                splay(key);                  //QUESTION 2
                _root.setRight(x);
            }
            }
      }
0
Comment
Question by:D4Ly
  • 15
  • 11
26 Comments
 
LVL 92

Expert Comment

by:objects
ID: 12516168
compareTo() is a method of Comparable, *not* Object.
The object needs to be an instance of Comparable.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516208
This does not work.  I am assuming this is what you were telling me to do.

                Comparable cKey = (Comparable)key;
            Comparable tKey = (Comparable) _root.getKey();
            if ((c = key.compareTo(tKey)) == 0) {      
                  _root.setItem(item);
                return;
            }
0
 
LVL 92

Expert Comment

by:objects
ID: 12516215
Does the key implement Comparable?
How exactly is it not working?
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 9

Author Comment

by:D4Ly
ID: 12516216
my bad.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516221
I forgot to replace key.comareTo with cKey.compareTo

spoke to soon.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516222
tips on 2 or 3?
0
 
LVL 92

Expert Comment

by:objects
ID: 12516234
> for (;;){//THIS LINE
> //Loop contents here
> }

same as:

while (true) {
//Loop contents here
}
0
 
LVL 92

Expert Comment

by:objects
ID: 12516236
What class is _root?
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516238
excelent. thanks very much

one left!!
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516241
wait...while WHAT is true?
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516242
_root is class TreeNode
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516247
and out of curiosity, what program do you edit your Java with?
0
 
LVL 92

Expert Comment

by:objects
ID: 12516248
> wait...while WHAT is true?

while 'true' is true :)
ie. loop forever
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516255
ah, hence the break; statements inside this mock while loop.
0
 
LVL 92

Accepted Solution

by:
objects earned 2000 total points
ID: 12516257
public TreeNode getNode(Object key)
{
   return getNode(_root, key);
}

public TreeNode getNode(TreeNode parent, Object key)
{
   TreeNode result = null;
   // compare parent with key for a match
   // if is the required node then do:
   if (match)
   {
     result = parent;
   }
   else
   {
     Enumeration i = parent.children();
     while (result==null && i.hasMoreElements())
     {
        TreeNode child = (TreeNode) i.nextElement();
        result = getNode(child, key);
     }
   }
   return result;
}
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516281
so when i want to call splay, i will now splay(getNode(key));, correct?

Can you explain what type Enumeration is? and where children comes from?
0
 
LVL 92

Expert Comment

by:objects
ID: 12516323
Yes, Enumeration is an interface from java.util package
children() is a method of TreeNode.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516330
I've created my own TreeNode class....which doesnt contain a children() method....must I include java.util.*?

I do have a method that I could possibly use instead of the enumeration that traverses a tree...let me check.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516336
I could possibly manipulate this computeSize class to traverse the tree searching, instead of increasing the count:

children() here comes from an iterator interface.

public class ComputeSize {
      int i;
      
      public ComputeSize(){
            i = 0;
      }
      
      private int doIt(Tree t,Position root) {
      if (t.isExternal(root))
            i=i+1;
      else {
            i=i+1;

            Iterator it = t.children(root);
            while(it.more()) {
                  Position kid = (Position)it.get();
                  doIt(t,kid);
                  it.next();
            }
            }
            return i;
      }
      public int doIt(Tree t) {
            return doIt(t,t.root());
      }
}
0
 
LVL 92

Expert Comment

by:objects
ID: 12516354
> which doesnt contain a children() method

ok then you need to whatever methods it provides to loop thru all the child nodes.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12516357
Thanks very much for all your help.

What program do you use to edit your Java code?
0
 
LVL 92

Expert Comment

by:objects
ID: 12516419
used to use ultraedit, but have been trialling jedit more recently.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12517478
what are your thoughts on eclipse?
0
 
LVL 92

Expert Comment

by:objects
ID: 12519118
Have never actually used it, but would like to find the time.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12525821
objects, because I have a splay tree, I could use this logic I think, to find my node:

say I have this tree:
i want to splay 5 in this tree, I simply grab
my root, compare if 5 is greater (YES), now move to the right, test greater
again (YES), move right, test (NO), move left, test (NO), move left, and now
return my node? just trying to think out loud...this seems about
right. Let me know, and thanks for your help.

       3
      /  \
    2    4
  /         \
1           7
            /  \
          6    8
         /        \
       5          10
                  /
                9
0
 
LVL 92

Expert Comment

by:objects
ID: 12530677
yes that sounds correct.
0

Featured Post

How to Use the Help Bell

Need to boost the visibility of your question for solutions? Use the Experts Exchange Help Bell to confirm priority levels and contact subject-matter experts for question attention.  Check out this how-to article for more information.

Question has a verified solution.

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

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
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 learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Suggested Courses

834 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