Triển khai Trie "Đơn giản"

Question

Tôi cần triển khai Trie (bằng Java) cho một dự án đại học. Các Trie sẽ có thể thêm và loại bỏ Strings (cho giai đoạn 1).

Tôi đã dành vài giờ mỗi ngày (trong vài ngày qua) cố gắng tìm ra cách thực hiện điều này và XỬ LÝ một cách khốn khổ mỗi lần.

Tôi cần trợ giúp, ví dụ trên internet và sách giáo khoa của tôi (Cấu trúc dữ liệu và thuật toán trong Java của Adam Drozdek) không giúp ích gì.

Thông tin

1. lớp Node tôi đang làm việc với:

   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. Và đây là mã giả cho chèn mà tôi cần phải làm theo: (cảnh báo nó là rất mơ hồ)

   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. Tôi cần triển khai các phương pháp sau.

   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. tôi không thể tìm thấy mã giả cho loại bỏ, nhưng nếu chèn không hoạt động xóa sẽ không giúp tôi.

5. Đây là hình ảnh về cách Trie mà tôi cần triển khai như thế nào.

6. Tôi biết rằng các Trie vẫn sẽ không hiệu quả nếu được thực hiện như thế này, nhưng tại thời điểm này tôi không cần phải lo lắng về việc này.

7. Cuốn sách này cung cấp một thực hiện tương tự như những gì tôi cần phải làm nhưng không sử dụng hết từ char ('$') và chỉ lưu trữ những lời mà không tiền tố của họ trong con các nút http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java

chế

1. tôi cần phải thực hiện các Trie trong JAVA.
2. Tôi không thể nhập hoặc sử dụng bất kỳ cấu trúc dữ liệu tích hợp nào của Java. (ví dụ: không có Bản đồ, HashMap, ArrayList, vv)
3. Tôi có thể sử dụng Mảng, Kiểu nguyên thủy Java và Chuỗi Java.
4. Trie phải sử dụng ký hiệu $ (đô la) để biểu thị phần cuối của từ. (Xem hình dưới đây)

5. tôi có thể asume mà bây giờ từ có chứa biểu tượng $ sẽ được chèn vào.
6. Tôi cần triển khai Trie theo phong cách tương tự như sách.
7. Trường hợp từ không quan trọng, ví dụ:tất cả các từ sẽ được coi là chữ thường
8. Trie chỉ được lưu trữ ký tự kết thúc và các ký tự áp dụng cho một từ chứ không phải toàn bộ bảng chữ cái (như một số cách triển khai).

Tôi không mong đợi bất kỳ ai thực hiện việc triển khai cho tôi (trừ khi họ có ai nói dối: P) Tôi thực sự cần trợ giúp.

Answer 1

Trước hết, tôi không nghĩ bạn nên tạo các nút lá và các nút nội bộ riêng biệt. Tôi khuyên bạn nên tạo một lớp nút chung với một phương thức isLeaf(). Phương thức này sẽ trả về true nếu một nút không có con.

Dưới đây là một số mã giả mức cao hơn cho các hàm bạn cần triển khai. Để đơn giản, tôi giả sử sự tồn tại của một phương thức được gọi là getIndex() trả về chỉ mục tương ứng với một ký tự.

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] 

Bạn có thể dễ dàng tăng thêm mã giả này để phù hợp với nhu cầu của bạn. Ví dụ, nếu bạn muốn quay trở lại bất cứ khi nào sai chèn không thành công:

• Return false nếu chuỗi đầu vào là null
• Return false nếu chuỗi đầu vào chứa các ký tự không hợp lệ

Bây giờ, đây là một số mã giả cao cấp để loại bỏ.

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 

Ở mức rất cao, chúng tôi làm theo chuỗi đầu vào cho nút mà chúng tôi muốn xóa. Sau này, chúng ta đi qua cây theo con trỏ cha và xóa tất cả các nút với 1 con (vì nó không còn cần thiết nữa). Khi chúng tôi đạt đến một nút với 2 trẻ em, chúng tôi dừng lại.

Giống như Insert, chúng ta có thể dễ dàng tăng thêm giả này để trả lại sai bất cứ khi nào xóa không thành công:

• Return false nếu chuỗi đầu vào là null
• Return false nếu chuỗi đầu vào chứa các ký tự không hợp lệ
• Return false nếu chuỗi đầu vào dẫn đến một Node mà không tồn tại

Nó là dễ dàng nhất để thực hiện xóa nếu lớp Node của bạn có một lĩnh vực mẹ. Tuy nhiên, có thể thực hiện phương thức mà không có điểm cha, nhưng nó khó hơn. Bạn có thể xem ví dụ về việc triển khai thủ công hơn here.