"Basit" Trie Uygulaması

Question

Bir üniversite projesi için bir Trie (Java'da) uygulamanız gerekiyor. Trie, Dizeleri ekleyebilmeli ve çıkarabilmelidir (faz 1 için).

Her gün birkaç saat harcadım (son birkaç gündür) bunun nasıl yapılacağını anlamaya çalışıyorum ve her seferinde başarısızlıkla sonuçlandı.

Bazı yardıma ihtiyacım var, internetteki örnekler ve ders kitabım (Java'da Veri Yapıları ve Algoritmaları Adam Drozdek tarafından) yardımcı olmuyor. Ben ile çalışıyorum

Bilgi

1. Düğüm sınıfları: Burada

   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. Ve izlemeniz gereken eki için sözde kodu:

   (çok muğlak uyarısı) Aşağıdaki yöntemleri uygulamam gerek.

   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. Ben çıkarma işleminde sözde kodunu bulmak, ancak ekleme silme işe yaramazsa alışkanlık bana yardımcı olamaz.

5. İşte uygulamak zorunda olduğum Trie'nin nasıl göründüğüne dair bir görüntü.

6. Böyle uygulanması durumunda Trie hala verimsiz olacağından farkındayım, ancak şu anda bu konuda endişelenmenize gerek yok.

7. kitap yapmam gerekenler benzer ancak kelime char ('$') ucunu kullanın ve yalnızca çocukta önekleriyle olmadan kelimeleri saklar vermez http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java

düğümlerin bir uygulamasını sağlar

Kısıtlamalar

Ben JAVA tray uygulamak gerekir.

Java'nın yerleşik veri yapılarını içe aktarmaya veya kullanmayabilirim. (örn. Map, HashMap, ArrayList vb.)

Array'ları, Java ilkel Türlerini ve Java Dizelerini kullanabilirim.

Trie, bir sözcük sonu belirtmek için $ (dolar) sembolü kullanmalıdır.

(aşağıdaki resme bakın)

1. Ben $ sembolü içeren şimdi kelimeyi eklenecektir asume olabilir.
2. Trie'i, kitapla aynı stille uygulamanız gerekiyor.
3. Kelimelerin önemi önemli değil örn.Tüm kelimeleri
4. Trie sadece sonu kelime karakterini ve bir kelime için geçerli karakterler değil (bazı uygulamalarda gibi) tüm alfabe saklamalısınız küçük olduğu kabul edilecektir.

Uygulamanın benim için birisini yapmasını beklemiyorum (etrafta bir tane bulunmadıkça: P) Gerçekten yardıma ihtiyacım var. Her şeyden

Answer 1

Öncelikle, sana yaprak düğümleri ve iç düğümleri ayrı sınıflar yapmalıdır sanmıyorum. IsLeaf() yöntemiyle evrensel bir düğüm sınıfı oluşturmanızı öneririm. Bir düğümün çocuğu yoksa, bu yöntem doğru olur. İşte

uygulamanız gerektiğiyle işlevler için bazı üst düzey pseudocode olduğunu. Basitlik için, bir karaktere karşılık gelen indeksi döndüren getIndex() adında bir yöntemin varlığını varsayardım.

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] 

kolayca ihtiyaçlarına uygun bu pseudocode uzatabilirsiniz. Ekleme başarısız olduğunda Örneğin, return false istiyorsanız:

• İade sahte girdi dizesi Şimdi
• İade sahte girdi dizesi içeriyorsa geçersiz karakterler

boşsa, İşte, kaldırmak için bazı üst düzey sözde koddur.

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 

Çok yüksek bir seviyede, kaldırmak istediğimiz düğüm için giriş dizesini izleriz. Bundan sonra, ana işaretçilerden sonra ağacı kesiştiririz ve her düğümü 1 çocukla sileriz (artık gerekli olmadığından). 2 çocuklu bir düğüme ulaştıktan sonra dururuz.

gibi takın silme başarısız olduğunda, kolayca yanlış dönmek için bu pseudocode çoğaltmak olabilir:

• İade sahte girdi dizesi null ise
İade girdi dizesi geçersiz karakterler içeriyor yanlış ise
• giriş dizesi Bu sizin Düğüm sınıfı bir üst alanı varsa silmek uygulanması kolaydır

varolmayan bir Düğüm yol açarsa

İade yanlış. Bununla birlikte, metodu ebeveyn noktaları olmaksızın uygulamak mümkündür, ancak daha zordur. Trickier uygulamasının here bir örneğini görebilirsiniz.