"Semplice" Implementazione Trie

Question

Devo implementare uno Trie (in Java) per un progetto college. Il Trie dovrebbe essere in grado di aggiungere e rimuovere stringhe (per la fase 1).

Ho trascorso diverse ore ogni giorno (negli ultimi giorni) cercando di capire come fare questo e FAILED miseramente ogni volta.

Ho bisogno di aiuto, gli esempi su internet e il mio libro di testo (Strutture dati e algoritmi in Java di Adam Drozdek) non aiutano.

Informazioni

1. classi nodo con cui sto lavorando:

   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. Ed ecco il codice pseudo per l'inserimento che ho bisogno di seguire: (in guardia è molto vaga)

   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. Ho bisogno di implementare i seguenti metodi.

   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. non posso trovare pseudo codice per la rimozione, ma se inserto non funziona eliminare abitudine che ti aiuti.

5. Ecco un'immagine di come dovrebbe apparire il Trie che ho bisogno di implementare.

6. Sono consapevole del fatto che la Trie sarà ancora inefficiente se attuata in questo modo, ma al momento non ho bisogno di preoccuparsi di questo.

7. il libro fornisce un'implementazione che è simile a quello che devo fare, ma non utilizza la fine del char parola ('$') e memorizza solo le parole senza i loro prefissi nel bambino nodi http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java

Vincoli

1. ho bisogno di attuare il trie in JAVA.
2. Non è possibile importare o utilizzare nessuna delle strutture di dati incorporate di Java. (cioè nessuna mappa, HashMap, ArrayList ecc.)
3. Posso utilizzare matrici, tipi primitivi Java e stringhe Java.
4. Il Trie deve utilizzare un simbolo $ (dollaro) per indicare una fine parola. (Vedi immagine sotto)

5. io possa asume che ora la parola contenente il simbolo $ verrà inserito.
6. Ho bisogno di implementare il Trie nello stesso stile del libro.
7. Il caso delle parole non ha importanza.tutte le parole saranno considerate minuscole
8. Il Trie deve solo memorizzare il carattere di fine parola ei caratteri applicabili a una parola e non l'intero alfabeto (come alcune implementazioni).

Non mi aspetto che qualcuno faccia l'implementazione per me (a meno che non ne abbia uno in giro: P) Ho davvero bisogno di aiuto.

Answer 1

Prima di tutto, non penso che dovresti rendere i nodi foglia e i nodi interni classi separate. Raccomando di creare una classe nodo universale con un metodo isLeaf(). Questo metodo restituirebbe true se un nodo non ha figli.

Ecco uno pseudocodice di livello superiore per le funzioni che è necessario implementare. Per semplicità, presumo l'esistenza di un metodo chiamato getIndex() che restituisce l'indice corrispondente a un carattere.

Insert(String str) 
    Node current = null 
    for each character in str 
     int index = getIndex(character) 
     if current.children[index] has not been initialized 
      initialize current.children[index] to be a new Node 
     current = current.children[index] 

È possibile aumentare facilmente questo pseudocodice in base alle proprie esigenze. Ad esempio, se si vuole restituire false ogni volta che l'inserimento non è successo:

• restituire false se la stringa di input è nullo
• restituire false se la stringa di input contiene caratteri non validi

Ora, ecco alcuni pseudocodice di livello superiore da rimuovere.

Remove(String str) 
    Node current = null 
    for each character in str 
     int index = getIndex(character) 
     current = current.children[index] 

    // At this point, we found the node we want to remove. However, we want to 
    // delete as many ancestor nodes as possible. We can delete an ancestor node 
    // if it is not need it any more. That is, we can delete an ancestor node 
    // if it has exactly one child. 

    Node ancestor = current 
    while ancestor is not null 
     if ancestor has 2 or more children 
      break out of loop 
     else if ancestor has less than 2 children 
      Node grandAncestor = ancestor.parent 
      if grandAncestor is not null 
       reinitialize grandAncestor.children // this has the effect of removing ancestor 

     ancestor = ancestor.parent 

Ad un livello molto alto, seguiamo la stringa di input sul nodo che vogliamo rimuovere. Dopo questo, attraversiamo l'albero seguendo i puntatori genitore e cancelliamo ogni nodo con 1 figlio (poiché non è più necessario). Una volta raggiunto un nodo con 2 bambini, ci fermiamo.

Come Inserire, possiamo facilmente aumentare questo pseudocodice per restituire false ogni volta che la cancellazione non va a buon fine:

• restituire false se la stringa di input è nullo
• restituire false se la stringa di input contiene caratteri non validi
• ritorno false se la stringa di input porta a un nodo che non esiste

E 'più semplice da implementare eliminare se la classe Node ha un campo genitore. Tuttavia, è possibile implementare il metodo senza punti principali, ma è più difficile. Puoi vedere un esempio dell'implementazione più ingannevole here.