Link to home
Start Free TrialLog in
Avatar of D4Ly
D4Ly

asked on

Splay trees and compareTo

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);
            }
            }
      }
Avatar of Mick Barry
Mick Barry
Flag of Australia image

compareTo() is a method of Comparable, *not* Object.
The object needs to be an instance of Comparable.
Avatar of D4Ly
D4Ly

ASKER

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;
            }
Does the key implement Comparable?
How exactly is it not working?
Avatar of D4Ly

ASKER

my bad.
Avatar of D4Ly

ASKER

I forgot to replace key.comareTo with cKey.compareTo

spoke to soon.
Avatar of D4Ly

ASKER

tips on 2 or 3?
> for (;;){//THIS LINE
> //Loop contents here
> }

same as:

while (true) {
//Loop contents here
}
What class is _root?
Avatar of D4Ly

ASKER

excelent. thanks very much

one left!!
Avatar of D4Ly

ASKER

wait...while WHAT is true?
Avatar of D4Ly

ASKER

_root is class TreeNode
Avatar of D4Ly

ASKER

and out of curiosity, what program do you edit your Java with?
> wait...while WHAT is true?

while 'true' is true :)
ie. loop forever
Avatar of D4Ly

ASKER

ah, hence the break; statements inside this mock while loop.
ASKER CERTIFIED SOLUTION
Avatar of Mick Barry
Mick Barry
Flag of Australia image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of D4Ly

ASKER

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?
Yes, Enumeration is an interface from java.util package
children() is a method of TreeNode.
Avatar of D4Ly

ASKER

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.
Avatar of D4Ly

ASKER

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());
      }
}
> which doesnt contain a children() method

ok then you need to whatever methods it provides to loop thru all the child nodes.
Avatar of D4Ly

ASKER

Thanks very much for all your help.

What program do you use to edit your Java code?
used to use ultraedit, but have been trialling jedit more recently.
Avatar of D4Ly

ASKER

what are your thoughts on eclipse?
Have never actually used it, but would like to find the time.
Avatar of D4Ly

ASKER

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
yes that sounds correct.