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().compareT o(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.getKe y()) == 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);
}
}
}
//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().compareT
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.getKe
// 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);
}
}
}
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;
}
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?
How exactly is it not working?
ASKER
my bad.
ASKER
I forgot to replace key.comareTo with cKey.compareTo
spoke to soon.
spoke to soon.
ASKER
tips on 2 or 3?
> for (;;){//THIS LINE
> //Loop contents here
> }
same as:
while (true) {
//Loop contents here
}
> //Loop contents here
> }
same as:
while (true) {
//Loop contents here
}
What class is _root?
ASKER
excelent. thanks very much
one left!!
one left!!
ASKER
wait...while WHAT is true?
ASKER
_root is class TreeNode
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
while 'true' is true :)
ie. loop forever
ASKER
ah, hence the break; statements inside this mock while loop.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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?
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.
children() is a method of TreeNode.
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.
I do have a method that I could possibly use instead of the enumeration that traverses a tree...let me check.
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());
}
}
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.
ok then you need to whatever methods it provides to loop thru all the child nodes.
ASKER
Thanks very much for all your help.
What program do you use to edit your Java code?
What program do you use to edit your Java code?
used to use ultraedit, but have been trialling jedit more recently.
ASKER
what are your thoughts on eclipse?
Have never actually used it, but would like to find the time.
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
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.
The object needs to be an instance of Comparable.