Splay trees

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.
LVL 9
D4LyAsked:
Who is Participating?
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.

zzynxSoftware engineerCommented:
1) - Remove the node (3)
    - 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)
0
zzynxSoftware engineerCommented:
Maybe it's better to follow this rule to become a better balanced tree:
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
0
D4LyAuthor Commented:
that looks good zzynx...i'm off to bed now 3:00am. I can't think anymore...but i'll hit it up hard tomorrow. thanks for what you've offered so far though!!!
0
Get expert help—faster!

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

zzynxSoftware engineerCommented:
:°) Good night
0
objectsCommented:
You need to split the tree in two by splaying it at the the node to be removed and then remove it.
Then find the largest node in the left subtree, and splay it.
Then finally join the two subtree back together.
0

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 trial
zzynxSoftware engineerCommented:
0
zzynxSoftware engineerCommented:
0
D4LyAuthor Commented:
I am here...in between classes...i'll take a look at about 11 tonight. thanks for all the input though, looks very promising.
0
D4LyAuthor Commented:

zzynx: 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?
0
zzynxSoftware engineerCommented:
>>what if i have this tree and want to remove 22? what are the rules for this?
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. ;°)
0
zzynxSoftware engineerCommented:
>>FOR MY INSERT::how does this sound?
Sounds OK.
>>This should work for all cases, right?
Right
0
D4LyAuthor Commented:
does my insert logic make sense? here's what I've done...now i'm onto digging into the remove and those links.

public void insert(Object key, Object item){
            TreeNode parentNode, n, newNode;
            if (_root == null) {
                _root = new TreeNode(key, item);
                return;
            }
            n = (TreeNode)grabNode(key,_root);
            if(n == null){
                  parentNode = findInsert(key,_root);
                  newNode = new TreeNode(key, item);
                  newNode.setParent(parentNode);
                  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(newNode);
                  }
                  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;
      }
0
D4LyAuthor Commented:
haha, speak of teh devil.
0
D4LyAuthor Commented:
zzynx, can you possibly answer this one while objects is away? its from his link:

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?
0
D4LyAuthor Commented:
This link made the most sense to me in terms of explaining the remove, but I am still unsure of a little bit.
0
objectsCommented:
i think your insert should be doing the splay first, what you have may come up with the same result but not sure.

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

removing it will give you two subtrees, you then join them
0
D4LyAuthor Commented:
splay what, the parent of the newNode before i add the newNode? why do you think that?


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.

0
objectsCommented:
Ideally I think your splay method should just take a key allowing you to splay() on a value.
0
D4LyAuthor Commented:
The interface I'm given has splay(TreeNode x), so i must use it.

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
0
objectsCommented:
And what does your splay() method do if the node does not exist?
0
D4LyAuthor Commented:
my splay() does absolutely nothing yet...i haven't gotten there...still trying to figure out the  Date: 11/09/2004 05:45PM EST post 4 or 5 up from here.  in my remove, insert, and find, if the key isn't found in the tree, the splay isn't called.
0
D4LyAuthor Commented:
for this insert, i 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!
0
objectsCommented:
I'd suggest first writing splay() as it is the basis of all other operations.
0
D4LyAuthor Commented:
ok, i'll take a look at it.

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

I'm in a different tz, not sure which u are referring to.
0
D4LyAuthor Commented:
splay what, the parent of the newNode before i add the newNode? why do you think that?


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.
0
objectsCommented:
> by saying that _root=null?

no you'll have two subtrees, one rooted at 18, and the other at 30.
0
D4LyAuthor Commented:
sow how do i connect these two root nodes to one another? splay the smallest from the right subtree to the root, and then attach the left tree where?
0
D4LyAuthor Commented:
also, in zzynx's link, i got this code: but the removeTop() is nowhere to be found in the source...what might it do?
      public Object remover(Object key)
    {
      if (isEmpty()) return null;
     
      if (key.equals(_root.getKey())) // delete root value
      {
          TreeNode newroot = removeTop(_root);
          _size--;
          Object result = _root.getItem();
          _root = newroot;
          return result;
      }
      else
      {
          TreeNode location = (TreeNode)grabNode(key,_root);

          if (key.equals(location.getKey())) {
            _size--;
            TreeNode parent = location.getParent();
            if (parent.getRight() == location) {
                parent.setRight(removeTop(location));
            } else {
                parent.setLeft(removeTop(location));
            }
            splay(_root = parent);
            return location.getItem();
          }
      }
      return null;
    }
0
zzynxSoftware engineerCommented:
>> in zzynx's link, i got this code: but the removeTop() is nowhere to be found in the source
In tha
0
D4LyAuthor Commented:
here's my new remove i've created: all cases should work except //IS THE ROOT, which I THINK i have an idea how to handle now. How does this sound:
                           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.getParent());
x.getParent().setLeft(x.getLeft());

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,_root);
                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.getRight());
                            x.getRight().setParent(x.getParent());
                      //now go as far left in the right subtree (until null is reached) = farLeft
                            farLeft = (TreeNode)getMin(x.getRight());
                      //now attach
                            farLeft.setLeft(x.getLeft());
                            x.getLeft().setParent(farLeft);
                            itemVal = x.getItem();
                            splay(x.getParent());
                      }else if((x.getLeft() == null) && (x.getRight() != null)){
                      //HAS A RIGHT CHILD ONLY
                            x.getParent().setRight(x.getRight());
                            x.getRight().setParent(x.getParent());
                            itemVal = x.getItem();
                            splay(x.getParent());
                      }else if((x.getRight() == null) && (x.getLeft() != null)){
                      //HAS A LEFT CHILD ONLY
                            x.getParent().setLeft(x.getLeft());
                            x.getLeft().setParent(x.getParent());
                            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(null);
                            }
                            itemVal = x.getItem();
                            splay(x.getParent());
                      }
                }
        _size--;
            return itemVal;
      }
0
D4LyAuthor Commented:
OKay guys, i think i'm done with my remove...i will reward points...onto my splay now, a few questions there, but i'll put in a new post. Thanks so far for all your help.
0
zzynxSoftware engineerCommented:
Thanks
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
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.