Значение термина "Radix" в дереве Radix

Question

Хотя трудно найти единодушное определение "дерева радиксов", большинство принятых определений дерева корней указывают, что это сжатое дерево префиксов. Что я пытаюсь понять, так это значение термина "основание" в данном случае. Почему сжатые префиксные деревья так называются (то есть Radix Tree), а некомпактные не называются Radix Tree?

Answer 1

Википедия может ответить на это, https://en.wikipedia.org/wiki/Radix:

В математических системах счисления основание или основание - это число уникальных цифр, включая ноль, используемых для представления чисел в позиционной системе счисления. Например, для десятичной системы (самой распространенной системы, используемой сегодня) основание равно десяти, потому что она использует десять цифр от 0 до 9.

и дерево https://en.wikipedia.org/wiki/Radix_tree:

структура данных, которая представляет оптимизированное по пространству дерево, в котором каждый узел, являющийся единственным дочерним элементом, объединяется со своим родителем. В результате число дочерних элементов каждого внутреннего узла составляет, по крайней мере, основание r радикального дерева, где r - положительное целое число и степень x, равная 2, имеющая x ≥ 1

Наконец, проверьте словарь:

1.radix (существительное)

Примитивное слово, из которого происходят другие слова.

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

РЕДАКТИРОВАТЬ - разработка

число дочерних элементов каждого внутреннего узла, по крайней мере, основание r

Давайте рассмотрим слова "аба, ненормальные, прыщи и бездонные". В обычном префиксном дереве (или три) каждая дуга добавляет одну букву к слову, поэтому мы имеем:

-a-b-a-
   n-o-r-m-a-l-
   y-s-m-a-l-
  -c-n-e-

Мой рисунок немного вводит в заблуждение - при попытках буквы обычно располагаются на дугах, поэтому "-" - это узел, а буквы - ребра. Обратите внимание, что многие внутренние узлы имеют одного ребенка! Теперь компактная (и очевидная) форма:

-a-b  -a-
       normal-
       ysmal-
   cne-

Ну, теперь у нас есть внутренний узел (позади б) с 3 детьми! Основание - это положительная степень 2, так что в этом случае 2. Почему 2, а не сказать 3? Ну во-первых, обратите внимание, что корень имеет 2 детей. Кроме того, предположим, что мы хотим добавить слово. Опции:

• разделяет b префикс - ну, 4 больше, чем 2.
• разделяет край ребенка b - сказать "ненормально". Ну, как работает вставка, разделяемая часть будет разделена, и мы получим:

Соответствующая ветка:

-normal-ly-
       -

normal теперь является внутренним узлом, но имеет 2 дочерних элементов (один лист). - другой случай будет удаление прыщей, например. Но теперь свойство компактности говорит, что узел после b должны быть объединены назад, так как это единственный ребенок, поэтому дерево становится

дерево:

-ab-a
   -normal-ly-
          -
   -ysmal

Итак, мы все еще поддерживаем детей>2.

Надеюсь, что это проясняет!