Придумал тут структуру данных для своих извращенных целей (AMR), не могу понять как ее обозвать/классифицировать.
Вопрос не в том что бы ПРИДУМАТЬ название (с этим я как нить справлюсь), а с тем что бы понять - к какому УЖЕ ИЗВЕСТНОМУ виду деревьев это относится (или это что то абсолютно новое).
Мои попытки загуглить че то похожее ничего разумного не дали, но я не специалист.
Это дерево, но больше похоже на всякие зонтичные растения.
-
есть листья и узлы. Данные лежат в листьях.
-
Узлы не содержат ссылок на родителей, поиск всегда идет от корня.
-
Узлы могут быть трех разных типов:
3.1. обычный узел - 2^D потомков (D - размерность пространства), потомками являются как листья так и узлы в перемешку
3.2. толстый У-узел - 2^{RD} потомков-узлов, R>1 но неограничено сверху
3.3. толстый Л-узел - 2^{RD} потомков-листьев, R>1 но неограничено сверху
R могут меняться от узла к узлу.
В толстых узлах данные конечно лежат по Z-кривой;-)
Ключем является целое число (ID листа) связанное с положением листа в пространстве и размером листа. Листья это D-мерные кубы кратных размеров в которых что то лежит (структура юзера типа T).
Из бонусов реализации - высокая локальность данных (все листья лежат в одном массиве, узлы в другом), минимальные накладные расходы и возможность сериализации на лету (нет пойнтеров). И минусов - относительно дорогое перестроение, но это редкая операция.
