Как хранить неуравновешенное дерево в матрице

Question

Я работаю с деревом лексики, структурой данных дерева k-ary с глубиной L, что является результатом итеративного запуска иерархического k-means кластеризации. Это несимметричная структура, поскольку процесс кластеризации может прекратиться, когда количество назначенных точек данных в кластере меньше, чем количество кластеров.

Моя проблема заключается в том, что мне требуется хранить это дерево в матричном формате.

Я думал о простом хранении его в первом порядке, но отходы памяти могут быть слишком высокими, если разница между фактическим количеством узлов, скажем n, и теоретическое число узлов в сбалансированном дереве увеличивается, что является:

n << (1-k^L)/(1-k) 

есть ли способ эффективного хранения несбалансированного дерева в виде матрицы, не теряя память или тратить меньше можно?

Answer 1

Кажется, было бы довольно сложно не тратить какое-либо пространство. Тем не менее, довольно простой подход описан ниже и требует только O (N log_k N) пространства или O (k N log_k N), если пространство для листьев всегда выделено (полезно в некоторых случаях), где N - число элементов в дереве. Стоимость заключается в том, что для доступа к элементу требуется O (log_k N).

Точная реализация довольно изменчива, так как зависит от ряда факторов. Идея состоит в том, чтобы просто обобщить представление сбалансированного двоичного дерева как массива, работать как неуравновешенное n-арное дерево в качестве матрицы. Это делается тем, что матричные ячейки действуют как узлы. Информация, содержащаяся в узле, может быть либо расположена в одной ячейке со структурой данных, либо разбросана по следующим нескольким ячейкам. Главное, что каждый узел должен содержать информацию для этого конкретного узла, а также информацию о местонахождении любых его дочерних элементов. Затем инкрементный указатель используется для отслеживания местонахождения следующего свободного места для детей.

В целом, это всего лишь массив с меньшим или равным r * c элементами, который был разбит на матрицу из r строк и c столбцов. Список списков может быть более полезным, поскольку строка L будет содержать узлы на глубине L. В противном случае там не так много полезного.