Мне нужен контейнер, который поддерживает эффективный произвольный доступ и вставку и удаление O (k)

Question

Я снова попытался задать тот же вопрос , но в итоге я задал другой вопрос, не предоставив необходимой информации о моей проблеме.

Я реализую структуру данных, которая являетсядерево.Каждый узел этого дерева имеет массив / вектор / (структуру произвольного доступа) со всеми его дочерними элементами, которых может быть произвольно много.Вставка / удаление элементов проста, так как мы всегда удваиваем / делим на два количество элементов в этом массиве.

Вот что означает в этом контексте вставка / удаление O(k).У нас есть k элементов, и мы добавляем k more или удаляем k/2.Восстановление всей структуры данных пока хорошо.A dynamic array (или vector) работает.

Операция, которая поднимает вопрос, заключается в следующем.Иногда нам нужно "split" узел, имеющий n потомков, что означает, что мы "делим" потомков между различными узлами.Мы погружаемся в непрерывных группах.Я полагаю, что наиболее эффективный способ такого разделения состоит в том, чтобы иметь один указатель для каждого нового узла в позиции, где находятся его дочерние элементы, и сколько их существует (скажем, каждый узел принимает k дочерних элементов).Но тогда число этих потомков может измениться, и это не должно влиять на его братьев и сестер (или, что еще хуже, на целое дерево), т.е. время выполнения вставки должно быть O(k), а не O(n).Как мы это сделаем?

Простой, но неэффективный обходной путь будет таким: каждый раз, когда мы разделяем узел, мы заменяем «большой» массив children на многие (столько, сколько разделяемые части)«маленькие» динамические массивы.

Каждый из следующих «блоков» является структурой произвольного доступа.

Answer 1

Как насчет hashmap ?

Амортизируется O(1) Доступ, вставка и удаление среднего случая; O(n) худший случай.

Answer 2

Мне кажется, что вы пытаетесь заново изобрести B + Tree ...

Существует вариант B + Tree, который заключается в хранении числа подэлементов вместоправильного ключа, это обеспечивает эффективный произвольный доступ (log n), который вы фактически контролируете.

Например, общий коэффициент для баз данных составляет около 1000, что означает, что на первом уровне дерева находитсяroot, второй может содержать до 1000 дочерних элементов, третий - до 1 000 000 и т. д. *

Если у вас менее 1 000 000 000 объектов, это означает не более 3 разыменований, что весьма эффективно.

Был написан модуль python, написанный с использованием этой техники, под названием blist , цель которого - заменить традиционный класс list (реализованный как C ++ vector) на дерево B +, чтобы повысить эффективностькрупные предметы.Измерения производительности можно найти здесь .

Answer 3

Из описания, которое вы дали для древовидной структуры, которую вы реализуете, может быть лучше создать новую структуру данных для имитации вашего дерева.Особенно, если вы уже отслеживаете указатели между узлами.

Если я понимаю ваше утверждение, каждый узел в вашем дереве будет содержать вектор дочерних указателей на узлы.Когда вам нужно разделить узел, вы можете создать новые узлы, каждый из которых получает сегмент вектора дочерних указателей, и вновь созданные узлы будут вставлены в вектор узла родительского узла.

дляпример:

N1->N2->(n3,n4,n5,n6,n7,n8) разделить N2 на два узла: N1->(N2_1, N2_2) с N2_1->(n3,n4,n5) и N2_2->(n6,n7,n8)

(Извините, я не знаю, как легко рисовать деревья ...)

Таким образом, вы только перезаписываете память, а не копируете, и доступ, как правило, будет log n.Кроме того, это дает правильное представление древовидной структуры в коде.

edit, добавление примера:

Предположим, снова у нас есть N1->N2->(n3,n4,n5,n6,n7,n8).Если N1 необходимо добавить новые узлы, единственное влияние - на узел N1: N1->(N2,N9)->(n3,n4,n5,n6,n7,n8)

Структура узла может быть такой (очень упрощенной):

class Node {
  vector<Node *> children;
  Node * parent;
};

Более крупная древовидная структура будет состоять из множества узлов, очень похожих на двоичное дерево.Чтобы добавить узлы к любому узлу в дереве, нужно добавить только элементы к члену children этого узла.Ничего другого не затронуто.