Мне нужно реализовать Trie (на Java) для проекта колледжа. Trie должен иметь возможность добавлять и удалять строки (для фазы 1).

Я тратил несколько часов каждый день (в течение последних нескольких дней), пытаясь понять, как это сделать, и каждый раз терпел неудачу.

Мне нужна помощь, примеры в Интернете и мой учебник (Структуры данных и алгоритмы в Java, Адам Дроздек) не помогают.

Информация

1. Классы узлов, с которыми я работаю:

   class Node {
       public boolean isLeaf;
   }
   
   class internalNode extends Node {
       public String letters;  //letter[0] = '$' always.
       //See image -> if letter[1] = 'A' then children[1] refers to child node "AMMO"
       //See image -> if letter[2] = 'B' then children[2] refers to internal node "#EU"
       public TrieNode[] children = new TrieNode[2];
   
       public TrieInternalNode(char ch)
       {
           letters = "#" + String.valueOf(ch);//letter[0] = '$' always.
           isLeaf = false;
       }
   }
   
   class leafNode extends Node
   {
       public String word;
       public TrieLeafNode(String word)
       {
           this.word = new String(word);
           isLeaf = true;
       }
   }
   

2. И вот псевдокод для вставки, которому мне нужно следовать: (предупреждение, это очень расплывчато)

   trieInsert(String K)
   {
       i = 0;
       p = the root;
       while (not inserted)
       {
           if the end of word k is reached
               set the end-of-word marker in p to true;
           else if (p.ptrs[K[i]] == 0)
               create a leaf containing K and put its address in p.ptrs[K[i]];
           else if reference p.ptrs[K[i]] refers to a leaf
           {
               K_L = key in leaf p.ptrs[K[i]]
               do
               {
                   create a nonleaf and put its address in p.ptrs[K[i]];
                   p = the new nonleaf;
               } while (K[i] == K_L[i++]);
           }
           create a leaf containing K and put its address in p.ptrs[K[--i]];
           if the end of word k is reached
               set the end-of-word marker in p to true;
           else
               create a leaf containing K_L and put its address in p.ptrs[K_L[i]];
           else
               p = p.ptrs[K[i++]];
       }
   }
   

3. Мне нужно реализовать следующие методы.

   public boolean add(String word){...}//adds word to trie structure should return true if successful and false otherwise
   
   public boolean remove(String word){...}//removes word from trie structure should return true if successful and false otherwise
   

4. Я не могу найти псевдокод для удаления, но если вставка не работает, удаление мне не поможет.

5. Вот изображение того, как должен выглядеть Trie, который мне нужно реализовать.

6. Я знаю, что Trie по-прежнему будет неэффективным, если будет реализован таким образом, но на данный момент мне не нужно беспокоиться об этом.

7. В книге представлена ​​реализация, похожая на то, что мне нужно сделать, но не использует конец слова char ('$') и сохраняет только слова без их префиксов в дочерних узлах http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java

Ограничения

1. Мне нужно реализовать три в JAVA.
2. Я не могу импортировать или использовать какие-либо встроенные структуры данных Java. (т.е. нет Map, HashMap, ArrayList и т. д.)
3. Я могу использовать массивы, примитивные типы Java и строки Java.
4. Trie должен использовать символ $ (доллар) для обозначения конца слова. (см. изображение ниже)

5. Могу предположить, что теперь будет вставляться слово, содержащее символ $.
6. Мне нужно реализовать Trie it в том же стиле, что и в книге.
7. Регистр слов значения не имеет, т.е. все слова будут считаться строчными
8. Trie должен хранить только символ конца слова и символы, применимые к слову, а не весь алфавит (как в некоторых реализациях).

Я не ожидаю, что кто-то сделает за меня реализацию (если только у них не завалялась :P). Мне просто очень нужна помощь.