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

Question

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

Answer 1

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

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

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

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

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

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

примитивный слово, от которого другие слова весной.

Радиус в дереве оснований определяет баланс между количеством детей (или глубины) дерева и «разреженности» или количеством суффиксов уникальным.

EDIT - разработка

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

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

-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- 
     - 

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

дерево:

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

так, мы по-прежнему поддерживать детей> 2.

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