Разрежённый массив представленный деревом

Здравствуйте.

Меня зовут Александр Рулёв и я хочу рассказать вам о структуре данных, на которую я совершенно случайно наткнулся (на самом деле около трёх дней перебирал возможные комбинации, пока не получил что-то однозначное).

У меня просто была проблема, которая оказалась не проблемой в реальном мире, но кажется я решил её в мире абстрактном.

Проблема была следующая: есть список элементов определённой длины. Мы должны быстро получать элемент по индексу, а так же иметь возможность вставить/удалить с любой позиции элемент. Причём чтобы остальные «пододвинулись», либо схлопнулись. Очевидно, что ни линейный список, ни массив не подходят. А обычное дерево не имеет возможности получить элемент по индексу без обхода дерева, которое тоже O(N) и лучше мы бы использовали список.

И кажется я решил эту проблему. И в данный момент это что-то похожее на эйфорию, поскольку находится всё больше и больше вариантов применения придуманной структуры данных, а фундаментальных проблем всё ещё не видно.

Асимптоматика свойственная дереву: O(log N) на все операции. Вставка/удаление в наивной реализации O((log N)^2), но мне кажется, что это можно оптимизировать.

В этой статье (первой, надеюсь не последней) я опишу, что представляет из себя это дерево, а так же как совершать над ним операции. Если всё работает так, как мне кажется и вы не найдёте никаких проблем, которые нельзя починить — мир получает прекрасную (как мне кажется) структуру данных. Иначе мне будет стыдно.

Изначально у меня не было массива, а была некая функция, аргументом который был некий индекс. Я не мог загрузить всё оттуда в массив, ибо потенциально кол-во данных могло быть огромным. Поэтому мне нужен был способ как-то частично модифицировать эти данные, не изменяя сами данные. Надеюсь, вы поняли.

И я подумал, что довольно логично было бы иметь возможность получить смещение любого индекса. Т.е. например, изначально, все индексы смещаются на 0: 0 => 0, 1 => 1, 2 => 2 и так далее. Отлично, теперь нужно подобрать структуру данных, которая могла бы находить это смещение. Очевидно, что ни списки, ни массивы, ни хештаблицы не подходят. Остаются деревья. (Этот абзац никак не связан с текстом выше и ниже и лишь описывает предысторию).

После множества проб и неудач, но имея концепцию, медленно исправляя проблемы пришёл к следующему:

Свойства дерева

1. Каждый узел дерева имеет ключ, ссылки на левое и правое поддерево а так же ссылку на данные.
2. Дерево не является деревом поиска, т.е. левый узел может иметь ключ больше ключа текущего узла, а правый меньше и наоборот в любых комбинациях. Ключ, вообще говоря, используется для хранения служебной информации.
3. Далее полным ключом узла будет называться значение ключа узла увеличенного на единицу. Для пустого узла это значение равно нулю.
4. Далее остаточным размером узла будет называться разность между ключём узла и суммой полных ключей левого и правого узла.
5. Ключ узла всегда меньше либо равен сумме полных ключей левого и правого узлов.

Каждый узел дерева представляет собой один элемент массива. Полный ключ левого узла — сколько элементов есть перед элементом, который представляется текущим узлом. Остаточный размер узла — сколько элементов после текущего являются пустыми. Нарисуем какое-нибудь такое дерево:

Число перед двоеточием — ключ, после — данные. В дереве 7 элементов, это значит, что в массиве так же 7 элементов. Но по ключу корневого элемента видно, что на самом деле массив имеет длину равную 15, т.е. примерно половина элементов в массиве пусты.

Массив, описываемый этим деревом выглядит следующим образом:

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

Обход дерева для поиска элемента на нужном индексе выглядит довольно интуитивно:

1. Вычитаем из искомого индекса смещение нулевого элемента. Если оно отрицательно, можем тут же вернуть, что такого элемента в массиве нет.
2. Если искомый индекс меньше, чем полный ключ левого узла — переходим в него и продолжаем поиск. Если левого узла нет — возвращаем об отсутствии элемента.
3. Если искомый индекс равен полному ключу левого узла, возвращаем данные текущего узла.
4. Если предыдущие два пункта не были выполнены — вычитаем из искомого индекса полный ключ левого узла.
5. Если новый индекс меньше либо равен остаточному размеру — возвращаем, что такого узла нет (он попадает на пропуск).
6. Иначе вычитаем из индекса остаточный размер и единицу, перемещаемся к правому узлу и продолжаем поиск. Если правого узла нет — возвращаем, что элемент отсутствует.

Можете попробовать погулять по дерево по правилам выше, совершая поиск разных элементов по разным индексам.

Если вам удастся найти:

• Разряжённый массив, который нельзя представить таким деревом, в котором однозначно можно будет найти элемент по индексу.
• Дерево, удовлетворяющее свойствам выше и не имеющая однозначного разряжённого массива.

То я вас поздравляю, вы всё сломали. Но мне кажется, что выглядит довольно надёжно.

Кажется очевидным, что мы всегда можем построить сбалансированное дерево, удовлетворяющее правилам выше для любого разряжённого массива. Сначала нам нужен список заполненных индексов и значений, которые по ним располагаются. Затем вы выбираем центральный элемент и начинаем рекурсивно строить левое поддерево. У конечных узлов дерева ключ будет равен разности между следующим и текущим индексом минус один. У тех, у которых есть дети — сумма полного ключа левого поддерева, разности следующего индекса и текущего, единицы и полного ключа правого поддерева.

Как мы видим, если у нас получилось сбалансированное дерево — поиск элемента по индексу будет иметь сложность O(log N).

Однако я ещё говорил о возможности модифицировать данный массив. Здесь я ещё не закончил и всё ещё не имею реализации данной структуры, поэтому возможно скажу что-то не так.

Для того, чтобы вставить элемент, нам нужно сначала найти узел по индексу, куда мы хотим вставить новый.

Если мы должны были вставить элемент в левое поддерево, но его не оказалось, то одно из двух. Это или элемент перед нулевым, или где-нибудь в одном из правых поддеревьев. Если это до нулевого — вставляем узел слева, устанавливая ключ равным разнице между найденным узлом и индексом, куда вставляем и единицей. А так же уменьшаем нашу переменную смещения нуля. Если же это случай не перед нулём — так же создаём узел слева от текущего. В обоих случаях после создания нового узла нам необходимо подняться по узлам до корня и увеличить значения ключей на значение ключа добавленного узла плюс единица.

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

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

Если же должны вставить элемент в правое поддерево, а его нет — создаём узел справа и изменяем ключи на разницу между вставляемым индексом и тем, который представляется найденным узлом.

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

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

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

Если же было запрошено удаление элемента, которое должно быть в отсутствующем правом поддереве, то это значит только одно — что это значение выходит за границы нашего массива и мы находимся в самом правом узле дерева. И если честно, то я не знаю, как правильно обрабатывать эту ситуацию, как и ту, когда просят удалить элемент массива, когда в нём нет элементов. Скорее всего мы ничего не должны делать, если подобное происходит, ибо удаление одного null-элемента из бесконечности null-элементов даёт в результате бесконечность null-элементов.

Модификация элемента очень похожа на добавление. Только если мы попадаем на узел, который является представлением искомого индекса — мы просто изменяем данные этого узла. А если в пустоте — то делаем так же, как и при добавлении, с той лишь разницей, что значение добавленного ключа будет на единицу меньше.

Однако всё это очень хорошо работает для не балансирующихся деревьев, но нам такой случай не нужен. Поэтому в данный момент в концепте я совершаю операции добавления/удаления элементов за O((log N)^2), абстрагировавшись от конкретного дерева и рассматривая поворот дерева как набор отсоединений и присоединений узлов от родителей и к родителям. Когда узел отсоединяется — он вычитает из узлов всех родителей до корня значение своего полного ключа. Когда присоединяется — прибавляет. На картинках похоже, что малый поворот АВЛ-дерева не влияет на представление массива, при соблюдении правил выше. Ну а большой поворот — это два малых.

Но такой подход не эффективен, т.к. если дерево будет повёрнуто целиком до корня — будет совершён примерно квадрат логарифма операций. Здесь два варианта — или интегрировать реализацию дерева в реализацию дерева разряжённого массива и оптимизировать это на низком уровне, или придумать, как можно зная какие и в каком порядке были совершены действия поворотов над деревом пересчитать ключи за линейное время от кол-ва изменённых вершин, т.е. за логарифм от величины дерева. Я что-то придумал похожее, но оно пока что совсем мутное.

Работа над структурой ещё не окончена и у меня всё ещё нет полной и работающей реализации, возможно её не существует, потому что возможно, что я где-то совершил критическую ошибку. А возможно это уже общеизвестно и один я и мои друзья ничего не слышали о подобном.

Но в любом случае всем public domain и спасибо за внимание.

Автор: Rulexec

Источник ^[1]