Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- // Определение структуры узла трай-дерева
- struct TrieNode
- {
- // Вектор дочерних узлов (размерность 26 для каждой буквы алфавита)
- vector<TrieNode*> children;
- // Флаг, указывающий, является ли текущий узел концом слова
- bool isEndOfWord;
- // Конструктор узла трай-дерева, инициализирующий вектор дочерних узлов и флаг конца слова
- TrieNode()
- {
- children = vector<TrieNode*>(26, nullptr);
- isEndOfWord = false;
- }
- };
- // Класс трай-дерева
- class Trie
- {
- private:
- // Указатель на корневой узел трай-дерева
- TrieNode* root;
- public:
- // Конструктор трай-дерева, создающий корневой узел
- Trie()
- {
- root = new TrieNode();
- }
- // Метод для добавления слова в трай-дерево
- void insert(const string& word)
- {
- TrieNode* node = root;
- // Проходимся по каждой букве слова
- for (char c : word)
- {
- // Если узел не имеет дочернего узла для текущей буквы, создаем его
- if (node->children[c - 'a'] == nullptr)
- {
- node->children[c - 'a'] = new TrieNode();
- }
- // Переходим к следующему узлу в дочерних узлах
- node = node->children[c - 'a'];
- }
- // Помечаем конечный узел как конец слова
- node->isEndOfWord = true;
- }
- // Метод для поиска слова в трай-дереве
- bool search(const string& word)
- {
- TrieNode* node = root;
- // Проходимся по каждой букве слова
- for (char c : word)
- {
- // Если узел не имеет дочернего узла для текущей буквы, слова нет в трай-дереве
- if (node->children[c - 'a'] == nullptr)
- {
- return false;
- }
- // Переходим к следующему узлу в дочерних узлах
- node = node->children[c - 'a'];
- }
- // Проверяем, является ли последний узел концом слова
- return node != nullptr && node->isEndOfWord;
- }
- // Метод для поиска слова по префиксу
- bool startsWith(const string& prefix)
- {
- TrieNode* node = root;
- // Проходимся по каждой букве префикса
- for (char c : prefix)
- {
- // Если переход к следующему узлу в дочерних узлах невозможен, слова с данным префиксом нет в трай-дереве
- if (node->children[c - 'a'] == nullptr)
- {
- return false;
- }
- // Переходим к следующему узлу в дочерних узлах
- node = node->children[c - 'a'];
- }
- // Если префикс найден, значит слова в трай-дереве есть с таким префиксом
- return node != nullptr;
- }
- // Метод для удаления всех слов с заданным префиксом
- void removePrefix(const string& prefix)
- {
- removePrefixHelper(root, prefix, 0);
- deleteEmptyNodes(root);
- }
- private:
- // Вспомогательный метод для удаления слов с заданным префиксом
- void removePrefixHelper(TrieNode* node, const string& prefix, int index)
- {
- if (node == nullptr)
- {
- return;
- }
- // Если достигли конца префикса, удаляем все слова, начинающиеся с данного префикса
- if (index == prefix.length())
- {
- removeWords(node);
- return;
- }
- // Рекурсивный вызов метода для удаления слов с префиксом
- removePrefixHelper(node->children[prefix[index] - 'a'], prefix, index + 1);
- }
- // Вспомогательный метод для удаления всех слов из узла
- void removeWords(TrieNode* node)
- {
- if (node == nullptr)
- {
- return;
- }
- // Сбрасываем флаг конца слова
- node->isEndOfWord = false;
- // Рекурсивный вызов метода для удаления всех слов из дочерних узлов
- for (int i = 0; i < node->children.size(); i++)
- {
- removeWords(node->children[i]);
- }
- // Удаляем текущий узел
- delete node;
- }
- // Вспомогательный метод для удаления пустых узлов из трай-дерева
- void deleteEmptyNodes(TrieNode* node)
- {
- if (node == nullptr)
- {
- return;
- }
- // Рекурсивный вызов метода для удаления пустых узлов из дочерних узлов
- for (int i = 0; i < node->children.size(); i++)
- {
- if (node->children[i] != nullptr)
- {
- // Если у дочернего узла нет флага конца слова и он пуст, удаляем его
- if (node->children[i]->isEndOfWord == false && isNodeEmpty(node->children[i]))
- {
- delete node->children[i];
- node->children[i] = nullptr;
- }
- else
- {
- deleteEmptyNodes(node->children[i]);
- }
- }
- }
- }
- // Метод для проверки, является ли узел пустым
- bool isNodeEmpty(TrieNode* node)
- {
- // Проходимся по всем дочерним узлам текущего узла
- for (TrieNode* child : node->children)
- {
- // Если дочерний узел не равен nullptr, значит он не пустой
- if (child != nullptr)
- {
- // Так как наша задача - удалить все пустые узлы, то если нашли хотя бы один непустой узел,
- // можно сразу вернуть false - текущий узел не является пустым
- return false;
- }
- }
- // Если цикл прошел по всем дочерним узлам, и ни один из них не был непустым, значит текущий узел пустой
- return true;
- }
- };
- int main()
- {
- Trie trie;
- // Вставляем
- trie.insert("apple");
- trie.insert("banana");
- trie.insert("app");
- trie.insert("apartment");
- trie.insert("baby");
- trie.insert("book");
- // Удаляем с префиксом "ap"
- trie.removePrefix("ap");
- // Проверяем наличие слов в дереве с помощью поиска
- cout << (trie.search("apple") ? "apple found" : "apple not found") << endl;
- cout << (trie.search("banana") ? "banana found" : "banana not found") << endl;
- cout << (trie.search("app") ? "app found" : "app not found") << endl;
- cout << (trie.search("apartment") ? "apartment found" : "apartment not found") << endl;
- cout << (trie.search("baby") ? "baby found" : "baby not found") << endl;
- cout << (trie.search("book") ? "book found" : "book not found") << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement