Как манипулировать строкой (переместить подстроку в другую часть строки) в O(log n), используя веревку или дерево отображения статистики заказов
Две недели назад я закончил реализацию дерева сплайнов, которое позволяет выполнять базовые функции, такие как вставка, удаление, поиск ключа и получение суммы ряда элементов из трех. Вы можете найти эту реализацию здесь как ссылку на этот вопрос или из любопытства.
В качестве дополнительной задачи (она необязательна и просрочена, я решаю ее не для оценки, а потому, что считаю ее полезную структуру данных непростой для "Google по этому поводу"), меня попросили внедрить структуру данных Rope для манипулировать строками, так что если строка является "чернокнижником", а заданные ключи - 0 2 2, то строка будет "lowarck" (0 2 - это подстрока "war", "lock" - это то, что осталось после удаления "war", и вы вставляете оно после 2-го символа превращается в "lo"+"war"+"ck"). Это всего лишь один запрос, но он может содержать до 100 000 запросов для строки длиной 300 000 символов, поэтому наивное решение не будет работать.
Мое первое сомнение касается инициализации дерева (для тех, кто прочитал суть, я буду использовать 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().
Я не совсем уверен, правильно ли это инициализировано. Я сделал распечатку обхода с указанием ключа и размера и получил всю строку в порядке размера, чего я и ожидал.
После этого я изменил метод обновления из этого:
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;
}
}
Тогда метод поиска, из оригинала:
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)
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);
}
Однако у меня уже есть проблема на этом этапе, поскольку, как вы можете видеть, исходная находка возвращает NodePair, в то время как этот метод возвращает Node. Объяснение NodePair по словам инструкторов:
Возвращает пару результата и новый корень. Если найдено, результат - указатель на узел с данным ключом. В противном случае, результат - указатель на узел с наименьшим большим ключом (следующее значение в заказе). Если ключ больше, чем все ключи в дереве, то результат равен нулю.
Это усложняет мой метод разделения, так как он использует метод 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, поэтому из полученной мной информации я понял, что этот тип структуры данных более промежуточный. уровень эксперта (я уже удивлен, что смог реализовать предыдущее дерево сплайнов. Поэтому, пожалуйста, учтите мой уровень для начинающих в вашем ответе.
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