[Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Splay trees

Posted on 2004-11-08
35
Medium Priority
?
560 Views
Last Modified: 2009-12-16
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.
0
Comment
Question by:D4Ly
  • 17
  • 10
  • 8
35 Comments
 
LVL 37

Expert Comment

by:zzynx
ID: 12530736
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
 
LVL 37

Expert Comment

by:zzynx
ID: 12530788
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
 
LVL 9

Author Comment

by:D4Ly
ID: 12530805
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 37

Expert Comment

by:zzynx
ID: 12530820
:°) Good night
0
 
LVL 92

Expert Comment

by:objects
ID: 12530955
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
 
LVL 92

Accepted Solution

by:
objects earned 800 total points
ID: 12531375
0
 
LVL 37

Expert Comment

by:zzynx
ID: 12531466
0
 
LVL 37

Assisted Solution

by:zzynx
zzynx earned 1200 total points
ID: 12531471
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12535687
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
 
LVL 9

Author Comment

by:D4Ly
ID: 12537733

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
 
LVL 37

Expert Comment

by:zzynx
ID: 12539156
>>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
 
LVL 37

Expert Comment

by:zzynx
ID: 12539198
>>FOR MY INSERT::how does this sound?
Sounds OK.
>>This should work for all cases, right?
Right
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12539208
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
 
LVL 9

Author Comment

by:D4Ly
ID: 12539212
haha, speak of teh devil.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12539275
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
 
LVL 9

Author Comment

by:D4Ly
ID: 12539280
This link made the most sense to me in terms of explaining the remove, but I am still unsure of a little bit.
0
 
LVL 92

Expert Comment

by:objects
ID: 12539310
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
 
LVL 9

Author Comment

by:D4Ly
ID: 12539372
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
 
LVL 92

Expert Comment

by:objects
ID: 12539427
Ideally I think your splay method should just take a key allowing you to splay() on a value.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12539483
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
 
LVL 92

Expert Comment

by:objects
ID: 12539500
And what does your splay() method do if the node does not exist?
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12539535
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
 
LVL 9

Author Comment

by:D4Ly
ID: 12539561
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
 
LVL 92

Expert Comment

by:objects
ID: 12539704
I'd suggest first writing splay() as it is the basis of all other operations.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12539728
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
 
LVL 92

Expert Comment

by:objects
ID: 12539766
> (Date: 11/09/2004 05:45PM EST)??

I'm in a different tz, not sure which u are referring to.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12539782
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
 
LVL 92

Expert Comment

by:objects
ID: 12539858
> by saying that _root=null?

no you'll have two subtrees, one rooted at 18, and the other at 30.
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12539975
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
 
LVL 9

Author Comment

by:D4Ly
ID: 12539982
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
 
LVL 37

Expert Comment

by:zzynx
ID: 12541868
>> in zzynx's link, i got this code: but the removeTop() is nowhere to be found in the source
In tha
0
 
LVL 9

Author Comment

by:D4Ly
ID: 12545523
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
 
LVL 9

Author Comment

by:D4Ly
ID: 12547117
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
 
LVL 37

Expert Comment

by:zzynx
ID: 12554031
Thanks
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
Suggested Courses
Course of the Month20 days, 10 hours left to enroll

867 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question