Вставка
Урок 5 из 14 курса Префиксные деревья (Trie) — Серия «Структуры данных» №8 на Coddy.
Чтобы вставить слово в префиксное дерево (trie), спускайтесь от корня по одному символу за раз. Для каждого символа слова: если у текущего узла нет дочернего узла для этого символа, создайте новый TrieNode и присоедините его. В любом случае, перейдите в этот дочерний узел и продолжайте со следующим символом.
Когда вы достигнете конца слова, отметьте узел, на котором вы остановились, с помощью isEndOfWord = true. Этот флаг — то, что позже отличает реально сохраненное слово от пути, который просто существует, потому что является префиксом чего-то другого.
Вставка "cat", а затем "car" использует общий путь c -> a и разветвляется только на третьем символе. Такое совместное использование — это то, что делает префиксные деревья настолько эффективными по объему памяти для словарей.
Задание
ЛегкоДобавьте метод insert в класс Trie.
Он принимает строку word и сохраняет её в префиксном дереве (trie):
- Начните с
root. Для каждого символаcвword, если у текущего узла нет дочернего узла дляc, добавьте туда новыйTrieNode. - Перейдите в этот дочерний узел и продолжайте.
- После последнего символа установите значение
isEndOfWordпоследнего узла вtrue.
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
}
return 0;
}