Two weeks ago I've finished an implementation of a splay tree that allows basic functions, like insert, delete, find key and and obtain the sum of a range of elements of the three. You can find this implementation here as reference for this question or out of curiosity.
As an extra task (its optional and its past due, I'm solving this not for a grade but because I believe its a useful data structure not easy to "Google about it"), I was asked to implement a Rope data structure to manipulate strings so if the string is "warlock" and the keys given are 0 2 2, then the string would be "lowarck" (0 2 is substring "war", "lock" is whats left after removing "war" and you insert it after 2nd char so turns into "lo"+"war"+"ck"). This is just one query but it can be up to 100k queries for a 300k character long string, so a naive solution wouldnt work.
My first doubt is about initializing the tree( For the ones who have read the gist,I'll use Node instead of Vertex in order to be easy to understand for most).
This is the Node class and the NodePair class:
class Node {
char key;
int size;
Node left;
Node right;
Node parent;
Node(char key, int size, Node left, Node right, Node parent) {
this.key = key;
this.size = size;
this.left = left;
this.right = right;
this.parent = parent;
}
}
class NodePair {
Node left;
Node right;
NodePair() {
}
NodePair(Node left, Node right) {
this.left = left;
this.right = right;
}
}
After that, I create the tree this way:
StringBuffer sb = new StringBuffer(br.readLine());
Node left=null;
for (int i=0;i<sb.length();i++){
root=new Vertex(sb.charAt(i), i+1, left, null, null);
if (i!=sb.length()-1){
left=root;
}
}
This creates a very unbalanced tree where the first char of the string (as node.key) has node.size 1 and is the leftmost child; and the last char of the string is the root with size=sb.length().
I am not completely sure if this is correctly initialized. I did an inorder traversal print with key and size and I got the whole string in size order, which is what I expected.
After that I have modified the Update method from this:
void update(Node v) {
if (v == null) return;
v.sum = v.key + (v.left != null ? v.left.sum : 0) + (v.right != null ? v.right.sum : 0);
if (v.left != null) {
v.left.parent = v;
}
if (v.right != null) {
v.right.parent = v;
}
}
To this: (based on CLRS chapter 14.1)
void update(Node v) {
if (v == null) return;
v.size = 1 + (v.left != null ? v.left.size : 0) + (v.right != null ? v.right.size : 0);
if (v.left != null) {
v.left.parent = v;
}
if (v.right != null) {
v.right.parent = v;
}
}
Then the find method, from the original:
NodePair find(Node root, int key) {
Node v = root;
Node last = root;
Node next = null;
while (v != null) {
if (v.key >= key && (next == null || v.key < next.key)) {
next = v;
}
last = v;
if (v.key == key) {
break;
}
if (v.key < key) {
v = v.right;
} else {
v = v.left;
}
}
root = splay(last);
return new NodePair(next, root);
}
to this:(Based in the Order Statistics-SELECT of CLRS Chapter 14.1)
Node find(Node r, int k){
int s = r.left.size + 1;
if (k==s) return r;
else if (k < s) {
return find(r.left,k);
}
return find(r.right,k-s);
}
However I already have a problem at this point since, as you can see, the original find returns a NodePair while this method returns a Node. The explanation of the NodePair according to instructors is:
Returns pair of the result and the new root.If found, result is a pointer to the node with the given key.Otherwise, result is a pointer to the node with the smallest bigger key (next value in the order). If the key is bigger than all keys in the tree, then result is null.
This complicates my split method since it uses Find method to look for the node to split. Besides this, I'm obtaining NullPointerException at this find method and from other students I understand that to avoid other error we should use a non-recursive version, so basically I need to implement a non-recursive version of OS-Select that returns a NodePair as the previous find method or modify my split method which is:
NodePair split(Node root, int key) {
NodePair result = new NodePair();
NodePair findAndRoot = find(root, key);
root = findAndRoot.right;
result.right = findAndRoot.left;
if (result.right == null) {
result.left = root;
return result;
}
result.right = splay(result.right);
result.left = result.right.left;
result.right.left = null;
if (result.left != null) {
result.left.parent = null;
}
update(result.left);
update(result.right);
return result;
}
As you can see, the find method is assigned to the NodePair findAndRoot. I believe that besides the OS-Select conversion to non-recursive my main problem is to understand the way NodePair is used by the previous find method and split method.
Finally, this is my implementation of the method to receive the tree and keys and manipulate them:
Node stringManip(Node v, int i, int j, int k){
Node left;
Node right;
NodePair middleRight =split(v,j+1);
left=middleRight.left;
right=middleRight.right;
NodePair leftMiddle = split(left,i);
Node start = leftMiddle.left;
Node substr = leftMiddle.right;
Node tmp = merge(start, right);
NodePair pairString = split(tmp,k+1);
Vertex fLeft =pairString.left;
Vertex fRight = pairString.right;
root = merge(merge(fLeft,substr),fRight);
root = splay(root);
update(root);
return root;
}
As you must realize from my code, I'm a beginner with only have 5 months that started learning to program and I picked Java, so from the info I've gathered I get that this type of data structure is more in the intermediate-expert level (I'm already surprise I was capable of implementing the previous splay tree. So please, consider my beginner level in your answer.
PD: Here's a pseudocode version of the nonrecursive OS-Select, still having NullPointerException..
OS-SELECT(x, i)
while x != null
r <- size[left[x]]+1
if i = r
then return x
elseif i < r
x = left[x]
else
x = right[x]
i = i - r
