![[H]ard|Forum](/styles/hardforum/xenforo/logo_dark.png){kind=logo}
I've been working on a Splay Tree assignment for my Advanced Data Structures class and putting some code together, which seems to work, but my professor quickly told me that my implementation is wrong but without a reason of why it wouldn't work. When inserting, I'm basically splaying every time when I come up, if the call went right I'd splay left, if it went left I'd splay right, same thing with search. I've tested it a number of times and it seems to work. Would anyone have an idea of why my implementation wouldn't work? (With insert, he said not to worry if the node is already in the tree).
Here's my code, if it'll help understand my implementation more:
Here's my code, if it'll help understand my implementation more:
Code:
public StringNode search(String s) {
StringNode val = search(s, root);
if (val != null)
root = val;
return val;
}
private static StringNode search(String sv, StringNode n) {
StringNode rtn = null;
if(n == null) { //easiest case
rtn = null; //empty tree
} else {
if(sv.equals(n.getString())) {
rtn = n; //found the node, so return it
}
if(sv.compareTo(n.getString()) > 0) {
rtn = search(sv, n.getRight()); //keep searching right
if(rtn != null) {
if(sv.equals(rtn.getString())) {
StringNode pt = n.getRight(); //step to the right
n.setRight(pt.getLeft());
pt.setLeft(n);
n = pt;
}
}
}
if(sv.compareTo(n.getString()) < 0) {
rtn = search(sv, n.getLeft()); //keep searching left
if(rtn != null) {
if(sv.equals(rtn.getString())) {
StringNode pt = n.getLeft(); //step to the left
n.setLeft(pt.getRight());
pt.setRight(n);
n = pt;
}
}
}
}
return rtn;
}
public void insert(String s) {
root = insert(s, root);
}
private static StringNode insert(String sv, StringNode n) {
StringNode rtn;
if(n == null) //easiest case, no tree
rtn = new StringNode(sv);
else { //determine where to put the node
if(sv.compareTo(n.getString()) > 0) {
System.out.println("greater");
n.setRight(insert(sv, n.getRight()));
StringNode pt = n.getRight(); //step to the right
n.setRight(pt.getLeft());
pt.setLeft(n);
n = pt;
}
if(sv.compareTo(n.getString()) < 0) {
n.setLeft(insert(sv, n.getLeft()));
StringNode pt = n.getLeft(); //step to the left
n.setLeft(pt.getRight());
pt.setRight(n);
n = pt;
}
rtn = n;
}
return rtn;
}