Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

I have two questions. If i need to post more code, let me know (grabNode() returns the node corresponding to the given key value)...each node has a pointer to its parent, left and right children. I am learning about splay trees...and am having trouble with the remove and insert methods.

First, for the remove method:

public Object remove(Object key){

TreeNode x, temp;

Object itemVal;

itemVal = null;

temp = (TreeNode)grabNode(key,_root);

if(temp!=null){

itemVal = temp.getItem();

splay(temp.getParent());

//CHANGE OF POINTERS HERE SOMEHOW?

}

return itemVal;

}

Now, if this method finds the node exists in the tree, it will splay

the parent node, and return the value of the node to be removed.

However, I don't understand logically what I must do to delete the

desired node. (I can't just tell the node to be null, since if its a

tree like this:

5

/ \

3 6

/ \

1 4

and I want to remove 3, I must somehow have a way to make 4's _left = 1).

Since the pointers that must change will be different for each case

(depending on how the tree is set up), how can I generalize this, or

know all cases? any help would be great.

More simply, I understand how to find the node to remove and splay its

parent, but don't understand how to deal with removing the node and

maintaining the tree's integrity.

Second, for the insert method:

public void insert(Object key, Object item){

TreeNode n, newN;

int c;

if (_root == null) {

_root = new TreeNode(key, item);

return;

}

n = (TreeNode)grabNode(key,_root);

if(n == null){

//Insert new node

newN = new TreeNode(key, item);

//RIGHT HERE

splay(newN);

}else{

//replace item value

n.setItem(item);

splay(n);

}

_size++;

}

Similar to the remove(), I don't understand how to change my pointers

in a general fashion that would work for all cases of the tree's

structure at any given point. I know this code must go //RIGHT HERE. I

know that I must find the place for the newN to go...but where I get

this node that will be the new parent node of newN i don't understand

(another method maybe?)

Hope this makes sense...thanks very much. I know its a lot at once.

First, for the remove method:

public Object remove(Object key){

TreeNode x, temp;

Object itemVal;

itemVal = null;

temp = (TreeNode)grabNode(key,_ro

if(temp!=null){

itemVal = temp.getItem();

splay(temp.getParent());

//CHANGE OF POINTERS HERE SOMEHOW?

}

return itemVal;

}

Now, if this method finds the node exists in the tree, it will splay

the parent node, and return the value of the node to be removed.

However, I don't understand logically what I must do to delete the

desired node. (I can't just tell the node to be null, since if its a

tree like this:

5

/ \

3 6

/ \

1 4

and I want to remove 3, I must somehow have a way to make 4's _left = 1).

Since the pointers that must change will be different for each case

(depending on how the tree is set up), how can I generalize this, or

know all cases? any help would be great.

More simply, I understand how to find the node to remove and splay its

parent, but don't understand how to deal with removing the node and

maintaining the tree's integrity.

Second, for the insert method:

public void insert(Object key, Object item){

TreeNode n, newN;

int c;

if (_root == null) {

_root = new TreeNode(key, item);

return;

}

n = (TreeNode)grabNode(key,_ro

if(n == null){

//Insert new node

newN = new TreeNode(key, item);

//RIGHT HERE

splay(newN);

}else{

//replace item value

n.setItem(item);

splay(n);

}

_size++;

}

Similar to the remove(), I don't understand how to change my pointers

in a general fashion that would work for all cases of the tree's

structure at any given point. I know this code must go //RIGHT HERE. I

know that I must find the place for the newN to go...but where I get

this node that will be the new parent node of newN i don't understand

(another method maybe?)

Hope this makes sense...thanks very much. I know its a lot at once.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

if removing a left node: first add the right node then the left

if removing a right node: first add the left node then the right

So to give an example:

35

/ \

22 46

/ \

18 30

/ \ \

9 20 33

a) remove node 22 (a left one)

35

\

46

b) add the (right) node 30 (and descendants) again:

35

/ \

30 46

\

33

c) Add the (leftt) node 18 again:

35

/ \

30 46

/ \

18 33

/ \

9 20

Then find the largest node in the left subtree, and splay it.

Then finally join the two subtree back together.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialzzynx: thanks for the visual, its helps quite a bit, but I am still having issues with conceptually gathering all of the possible cases for the removal in terms of the structure of the tree, and the rules to follow to handle each. ie, your example (modified):

35

/ \

22 46

/ \

18 30

/ \ / \

9 20 28 33

what if i have this tree and want to remove 22? i now have a left node 28 which will be in the way of 18, 9 and 20. what are the rules for this? i think i still pop the whole subtree up, and then attach the 18 subtree onto the left of 28, but i don't understand a general logical rule to handle this.

Objects- Thanks for the links: For the remove, this seems to make most sense for my application. So I splay the node to be deleted. It becomes the root. I then remove it (How? change pointers? just set it to null??). Now I have two subtrees and splay the smallest element in the right subtree (ie. go right from the root and then left as far as I can). "and then go from there"...what does this mean? and the node i removed, how do i account for its left and right children pointing to the now null root node?

quoted:

The delete(i, S) operation can be implemented by calling splay(i, S) to bring i to the root. When

this node is deleted, you’ll have two subtrees to join. One easy way to join is to use to splay

operation to bring the smallest element in the right subtree to the root, and go from there.

FOR MY INSERT::how does this sound?

I will create a method similar to my grabNode() method which will find the proper place for the node to insert. ie, take the tree above. I want to now insert 26.

look at 33, go left, look at 22, go right, look at 30, go left look at 28 go left, and reach null. so now this is where i place my new TreeNode with key value of 26. I setLeft of 28 to be 26 and setParent of 26 to be 28. splay(26). done.

This should work for all cases, right?

You could follow the same method as I said before. That left node 28 is no problem.

a) remove node 22 (a left one)

35

\

46

b) add the (right) node 30 (and descendants) again:

35

/ \

30 46

/ \

28 33

c) Add the (leftt) node 18 again:

35

/ \

30 46

/ \

28 33

/

18

/ \

9 20

So, you're right:

>>i think i still pop the whole subtree up, and then attach the 18 subtree onto the left of 28

>>but i don't understand a general logical rule to handle this.

Well, this still follows my intuitive rule:

>>if removing a left node: first add the right node then the left

>>if removing a right node: first add the left node then the right

But, you might be better off following the rules stated in the links we've given you. ;°)

public void insert(Object key, Object item){

TreeNode parentNode, n, newNode;

if (_root == null) {

_root = new TreeNode(key, item);

return;

}

n = (TreeNode)grabNode(key,_ro

if(n == null){

parentNode = findInsert(key,_root);

newNode = new TreeNode(key, item);

newNode.setParent(parentNo

Comparable cKey = (Comparable)key;

Comparable tKey = (Comparable) parentNode.getKey();

if(cKey.compareTo(tKey) < 0){

parentNode.setLeft(newNode

}else if(cKey.compareTo(tKey) > 0){

parentNode.setRight(newNod

}

splay(newNode);

}else{

n.setItem(item);

splay(n);

}

_size++;

}

public TreeNode findInsert(Object key, TreeNode x){

Comparable cKey = (Comparable)key;

Comparable tKey = (Comparable) x.getKey();

if(cKey.compareTo(tKey) < 0){

//Place somewhere to the left of this node

if(x.getLeft()!=null){

findInsert(key,x.getLeft()

}

}else if(cKey.compareTo(tKey) > 0){

//Place somewhere to the right of this node

if(x.getRight()!=null){

findInsert(key,x.getRight(

}

}

return x;

}

quoted:

The delete(i, S) operation can be implemented by calling splay(i, S) to bring i to the root. When

this node is deleted, you’ll have two subtrees to join. One easy way to join is to use to splay

operation to bring the smallest element in the right subtree to the root, and go from there.

Objects- Thanks for the links: For the remove, this seems to make most sense for my application. So I splay the node to be deleted. It becomes the root. I then remove it (How? change pointers? just set it to null??). Now I have two subtrees and splay the smallest element in the right subtree (ie. go right from the root and then left as far as I can). "and then go from there"...what does this mean? and the node i removed, how do i account for its left and right children pointing to the now null root node?

> I then remove it (How? change pointers? just set it to null??).

removing it will give you two subtrees, you then join them

and so, i am left with 2 subtrees, or

22

/ \

18 30

/ \ / \

9 20 28 33

say i wanted to remove 22, and ^^THIS^^ is the tree AFTER i've splayed 22 to the root from where ever it was in the tree. I then remove 22...by saying that _root=null?

null

/ \

18 30

/ \ / \

9 20 28 33

and now must join these two trees. i can now splay 28? what happens to the _root being null? or 18's and 30's parent pointer no longer existing?

When I set 22 = null, do i also say 18.setParent(null) and 30.setParent(null)? I hope my confusion is understood, if i have an empty slot in a place on the tree other than an external leaf node.

This is why i made the grabNode method, which takes that key you would ideally like the splay() to have, and finds the corresponding node, and passes IT to the splay

a) a new node

b) the node that exists with the desired key, but with a new item value (which MUST exist)

for the remove, which i'm still trying to understand the logic of as in previous questions, i check whether the node exists or not...if it doesn't, return null (DON'T SPLAY), and if it does exist, splay it!

can you offer any input on my confusion in the comment above (Date: 11/09/2004 05:45PM EST)??

and so, i am left with 2 subtrees, or

22

/ \

18 30

/ \ / \

9 20 28 33

say i wanted to remove 22, and ^^THIS^^ is the tree AFTER i've splayed 22 to the root from where ever it was in the tree. I then remove 22...by saying that _root=null?

null

/ \

18 30

/ \ / \

9 20 28 33

and now must join these two trees. i can now splay 28? what happens to the _root being null? or 18's and 30's parent pointer no longer existing?

When I set 22 = null, do i also say 18.setParent(null) and 30.setParent(null)? I hope my confusion is understood, if i have an empty slot in a place on the tree other than an external leaf node.

public Object remover(Object key)

{

if (isEmpty()) return null;

if (key.equals(_root.getKey()

{

TreeNode newroot = removeTop(_root);

_size--;

Object result = _root.getItem();

_root = newroot;

return result;

}

else

{

TreeNode location = (TreeNode)grabNode(key,_ro

if (key.equals(location.getKe

_size--;

TreeNode parent = location.getParent();

if (parent.getRight() == location) {

parent.setRight(removeTop(

} else {

parent.setLeft(removeTop(l

}

splay(_root = parent);

return location.getItem();

}

}

return null;

}

>> in zzynx's link, i got this code: but the removeTop() is nowhere to be found in the source

In tha

In tha

In that code SplayTree extends BinarySearchTree.

Here's the code of BinarySearchTree:

http://www.cs.williams.edu/~bailey/JavaStructures/bailey/structure/BinarySearchTree.java

and

http://www.cs.williams.edu/~bailey/JavaStructures/bailey/structure/OrderedStructure.java

http://www.cs.williams.edu/~bailey/JavaStructures/bailey/structure/AbstractStructure.java

http://www.cs.williams.edu/~bailey/JavaStructures/bailey/structure/Structure.java

8

/ \

5 10

/ \ / \

3 6 9 18

/ \

1 4

remove(8);

Find the smallest in the right side of the tree...(9).

splay(9);

9

/ \

8 10

/ \

5 18

/ \

3 6

/ \

1 4

when doing this, the node to remove (the old root) will always be the left child of the new root node, so the deletion is now easy.

x = the node 8

x.getLeft().setParent(x.ge

x.getParent().setLeft(x.ge

8 will also never have a right child, so these are the only two swaps i must make, and 8 has now been removed from the tree, with the best replacement (9) in its place in the root.

I don't THINK another splay is necessary after this, but I COULD BE WRONG!!!!

public Object remove(Object key){

TreeNode x, farLeft;

Object itemVal = null;

x = (TreeNode)grabNode(key,_ro

if(x == null){

//DOES NOT EXIST IN THE TREE

return null;

}else if(x == _root){

//IS THE ROOT

//TODO

}else{

if((x.getLeft() != null) && (x.getRight() != null)){

//has 2 children

//attach the right subtree of x to the left of x's parent

x.getParent().setLeft(x.ge

x.getRight().setParent(x.g

//now go as far left in the right subtree (until null is reached) = farLeft

farLeft = (TreeNode)getMin(x.getRigh

//now attach

farLeft.setLeft(x.getLeft(

x.getLeft().setParent(farL

itemVal = x.getItem();

splay(x.getParent());

}else if((x.getLeft() == null) && (x.getRight() != null)){

//HAS A RIGHT CHILD ONLY

x.getParent().setRight(x.g

x.getRight().setParent(x.g

itemVal = x.getItem();

splay(x.getParent());

}else if((x.getRight() == null) && (x.getLeft() != null)){

//HAS A LEFT CHILD ONLY

x.getParent().setLeft(x.ge

x.getLeft().setParent(x.ge

itemVal = x.getItem();

splay(x.getParent());

}else if((x.getRight() == null) && (x.getLeft() == null)){

//HAS NO CHILDREN (IS AN EXTERNAL LEAF NODE)

if(x == x.getParent().getLeft()){

//it is a left node of the parent

x.getParent().setLeft(null

}else if(x == x.getParent().getRight()){

//it is a right node of the parent

x.getParent().setRight(nul

}

itemVal = x.getItem();

splay(x.getParent());

}

}

_size--;

return itemVal;

}

Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

- add the left direct child again to the tree as if it would be a new add (1)

- add the right direct child again to the tree as if it would be a new add (4)