TRIE структуры данных implementaion в

Question

, что это ошибка в функции поискового

search_word(); 

и эта реализация использует временную сложность эффективности для TRIE или не для операций как ввод/поиск. считать строку из 1500 букв, выполняющих операцию вставки/поиска во времени менее 2 секунд, может ли она быть передана?

class Trie 
{ 
private: 
    struct node 
    { 
     bool isWord; 
     node* child[26]; 
     node() 
     { 
      for(int i = 0;i < 26;i++) 
       child[i] = NULL; 
      isWord = false; 
     } 
    }; 

    void insert_word(int index, node* vertex, int i, string s) 
    { 
     if(index == SZ) 
     { 
      vertex -> isWord = true; 
      return; 
     } 
     int c = s[index] - 'a'; 
     if(vertex -> child[c] == NULL) 
      vertex -> child[c] = new node; 

     insert_word(index + 1, vertex -> child[c], c, s); 

    } 
    bool search_word(int index, node* vertex, int i, string s) 
    { 
     if(index == SZ && vertex -> isWord == true) 
      return true; 
     if(index == SZ && vertex -> isWord == false) 
      return false; 

     int c = s[index] - 'a'; 

     if(vertex -> child[c] == NULL) 
      return false; 
     else 
      return search_word(index + 1, vertex -> child[c], c, s); 
    } 
public: 
    int SZ; 
    node* root; 
    Trie() 
    { 
     root = new node; 
    } 
    void insert_word(string s) 
    { 
     SZ = s.size(); 
     insert_word(0, root, s[0] - 'a', s); 
    } 
    bool search_word(string s) 
    { 
     SZ = s.size(); 
     return search_word(0, root, s[0] - 'a', s); 
    } 

}; 

обновление: найдена ошибка, и код должен работать правильно.

Answer 1

хорошо, я нашел ошибку, и она находится в блоке кода

if(index == (SZ - 1)) 
    { 
     vertex -> isWord = true; 
     return; 
    } 

индекс должен быть проверен для == с самого размера не размер-1, почему ..? ex: string ab, если мы сейчас обрабатываем букву b, это == размер - 1 означает последний символ в строке, код будет отмечать его корень как конец слова, а не узел, связанный с символом b, потому что он никогда не был создано путем редактирования его размера он должен исправным также в

search_word() 

размера - 1 должны быть отредактировано

примечания: я буду обновлять сам вопрос, чтобы иметь фиксированный код.