Я снова изобрел велосипед?

Дерево остатков


Недавно в голову пришла следующая идея:

Если взять список простых чисел 2,3,5,7…
Можно построить дерево, где каждый уровень дерева соответствует простому числу, и у всех узлов данного уровня количество дочерних элементов равно этому числу. Позиция в дереве определяется путем взятия остатка от деления на простое число. Можно сказать, что мы кодируем число в системе остаточных классов(СОК).
Допустим число 15 можно закодировать так:
15 % 2 = 1
15 % 3 = 0
15 % 5 = 0
Значит маршрут поиска элемента в дереве будет 1 0 0

Вот пример полного дерева для основания (2,3)
dl.dropbox.com/u/20772796/tree.png

Выскажие ваше экспертное мнение, встречались ли вы с такими структурами данных?

Если кому-то интересно, я набросал первый вариант реализации на Scala github.com/netslow/rtree
  • Вопрос задан
  • 3091 просмотр
Пригласить эксперта
Ответы на вопрос 7
SabMakc
@SabMakc
Необходимо провести оценку сложности добавление / удаления и поиска элемента в таком дереве.
Потом сравнить со стандартными реализациями (Бинарное, Б-Дерево, АВЛ и т.д.) и тогда уже судить о применимости данного дерева к задачам.
Вполне может оказаться, что при реальном использовании сложность будет крайне высока (взятие целой части — не такая простая задача, выполняется гораздо дольше простого сравнения 2х чисел).
Ответ написан
@yeputons
Не встречался. А вы уже придумали этому какое-нибудь применение? Идея красивая
Ответ написан
sainnr
@sainnr
Мне кажется, стоит разобрать конкретный вариант применения (лучше 2 — удачный и не очень). Тогда на примере решения какой-нибудь задачи уже можно будет оценить сложность использования данного решения и сравнить с другими вариантами решения поставленной задачи.
Ответ написан
@IlyaPodkopaev
в ИППМ РАН целый институт этим занят. некоторые вещи очень быстро считаются. а если еще логарифметику добавить… в общем, этому методу лет 50 не меньше
Ответ написан
okazymyrov
@okazymyrov
Какова цель этого дерева? Приведи ещё пару примеров для других чисел (например, 7, 12, 14).
Ответ написан
BuriK666
@BuriK666
Компьютерный псих
идея интересная, но не практичная для большого кол-ва данных.
Для большого дерева, необходимо иметь большой список простых чисел
Ответ написан
NikoM
@NikoM
огромные затраты на память, думаю в чистом виде алгоритм не применим в реальной жизни.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы