两周前，我完成了一个展开树的实现，它允许基本功能，如插入、删除、查找键和获取三者的一系列元素的总和。您可以在此处找到此实现作为此问题的参考或出于好奇。
作为一项额外的任务（它是可选的，它是过期的，我解决这个问题不是为了一个成绩，而是因为我相信它是一个有用的数据结构不容易“谷歌关于它”），我被要求实现一个 Rope 数据结构来操作字符串，因此如果字符串是“warlock”并且给定的键是 0 2 2，那么字符串将是“lowarck”（0 2 是子字符串“war”，“lock”是删除“war”后剩下的内容，然后插入它在第二个字符之后变成“lo”+“war”+“ck”）。这只是一个查询，但对于 300k 字符长的字符串，它最多可以查询 100k，所以一个简单的解决方案是行不通的。
我的第一个疑问是初始化树（对于那些已经阅读要点的人，我将使用 Node 而不是 Vertex，以便大多数人易于理解）。
这是 Node 类和 NodePair 类：
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;
}
}
之后，我以这种方式创建树：
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;
}
}
这会创建一个非常不平衡的树，其中字符串的第一个字符（作为 node.key）具有 node.size 1 并且是最左边的孩子；字符串的最后一个字符是 size=sb.length() 的根。
我不完全确定这是否正确初始化。我用键和大小做了一个中序遍历打印，我得到了整个字符串的大小顺序，这是我所期望的。
之后，我修改了 Update 方法：
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;
}
}
为此：（基于 CLRS 第 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;
}
}
然后是find方法，来自原文：
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);
}
为此：（基于 CLRS 第 14.1 章的 Order Statistics-SELECT）
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);
}
但是，此时我已经遇到了问题，因为如您所见，原始 find 返回一个 NodePair，而此方法返回一个 Node。根据讲师对 NodePair 的解释是：
返回结果和新根的对。如果找到，result 是指向具有给定键的节点的指针。否则，result 是指向具有最小较大键的节点的指针（顺序中的下一个值）。如果键大于树中的所有键，则结果为空。
这使我的拆分方法变得复杂，因为它使用 Find 方法来查找要拆分的节点。除此之外，我在这个 find 方法中获得了 NullPointerException，从其他学生那里我了解到，为了避免其他错误，我们应该使用非递归版本，所以基本上我需要实现 OS-Select 的非递归版本，它返回一个NodePair 作为以前的 find 方法或修改我的 split 方法是：
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;
}
如您所见，find 方法被分配给 NodePair findAndRoot。我相信除了将 OS-Select 转换为非递归之外，我的主要问题是要了解 NodePair 使用之前的 find 方法和 split 方法的方式。
最后，这是我接收树和键并操作它们的方法的实现：
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;
}
正如您必须从我的代码中意识到的那样，我是一个只有 5 个月开始学习编程的初学者，我选择了 Java，所以从我收集到的信息中，我了解到这种类型的数据结构更多地处于中间状态 -专家级别（我已经很惊讶我能够实现以前的 splay tree。所以请在你的回答中考虑我的初学者级别。
PD：这是非递归 OS-Select 的伪代码版本，仍然有 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