Реализация Trie - вставка элементов в Trie

Question

Я разрабатываю Trie структуру данных, где каждый узел представляет слово. Так слова st, stack, stackoverflow и overflow будут расположены как

root
--st
---stack
-----stackoverflow
--overflow

My Trie использует HashTable внутри, поэтому поиск всех узлов будет занимать постоянное время. Ниже приведен алгоритм, который я выбрал, чтобы вставить элемент в дерево.

1. Проверить наличие предмета в дереве. Если существует, вернитесь, иначе перейдите к шагу 2.
2. Выполните итерацию каждого символа в key и проверьте наличие слова. Делайте это, пока мы не получим узел, где новое значение может быть добавлено как дочернее. Если узел не найден, он будет добавлен в корневой узел.
3. После вставки переставьте братьев и сестер узла, под которым был вставлен новый узел. Это будет проходить через всех братьев и сестер и сравнить с вновь вставленным узлом. Если любой из узлов начинается с тех же символов, что и у нового узла, он будет перемещен оттуда и добавлен как дочерний узел нового узла.

Я не уверен, что это правильный способ реализации дерева. Любые предложения или улучшения приветствуются.

Используемый язык: C ++

Answer 1

Три должно выглядеть так

                      ROOT
             overflow/    \st
                    O      O
                            \ack
                             O
                              \overflow
                               O

Обычно вам не нужно использовать хеш-таблицы как часть дерева; само по себе это уже эффективная структура данных индекса. Конечно, вы можете сделать это.

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

Я полагаю, что шаг (3) неправильный, вам не нужно переставлять три и, на самом деле, вы не должны этого делать, потому что вы храните только дополнительные строковые фрагменты. в три; см. рисунок выше.

Answer 2

Ниже приведен код Java для алгоритма вставки.

public void insert(String s){
  Node current = root; 
  if(s.length()==0) //For an empty character
   current.marker=true;
  for(int i=0;i<s.length();i++){
   Node child = current.subNode(s.charAt(i));
   if(child!=null){ 
    current = child;
   }
   else{
    current.child.add(new Node(s.charAt(i)));
    current = current.subNode(s.charAt(i));
   }
   // Set marker to indicate end of the word
   if(i==s.length()-1)
    current.marker = true;
  } 
 } 

Более подробное руководство см. здесь .

Answer 3

У вас была возможность взглянуть на это .. http://linux.thai.net/~thep/datrie/datrie.html#Insert