Трие | (Удалять)

// C ++ реализация delete
// операции на Трие
#include <bits/stdc++.h>

using namespace std;

const int ALPHABET_SIZE = 26;

  
// Три узла

struct TrieNode {

    struct TrieNode* children[ALPHABET_SIZE];

    // isEndOfWord равно true, если узел представляет

    // конец слова

    bool isEndOfWord;

};

  
// Возвращает новый три-узел (инициализируется NULL)

struct TrieNode* getNode(void)

{

    struct TrieNode* pNode = new TrieNode;

    pNode->isEndOfWord = false;

    for (int i = 0; i < ALPHABET_SIZE; i++)

        pNode->children[i] = NULL;

    return pNode;

}

  
// Если нет, вставляет ключ в три
// Если ключ является префиксом узла trie, просто
// отмечает листовой узел

void insert(struct TrieNode* root, string key)

{

    struct TrieNode* pCrawl = root;

    for (int i = 0; i < key.length(); i++) {

        int index = key[i] - 'a';

        if (!pCrawl->children[index])

            pCrawl->children[index] = getNode();

        pCrawl = pCrawl->children[index];

    }

    // пометить последний узел как лист

    pCrawl->isEndOfWord = true;

}

  
// Возвращает true, если ключ присутствует в trie, иначе
// ложный

bool search(struct TrieNode* root, string key)

{

    struct TrieNode* pCrawl = root;

    for (int i = 0; i < key.length(); i++) {

        int index = key[i] - 'a';

        if (!pCrawl->children[index])

            return false;

        pCrawl = pCrawl->children[index];

    }

    return (pCrawl != NULL && pCrawl->isEndOfWord);

}

  
// Возвращает true, если у root нет потомков, иначе false

bool isEmpty(TrieNode* root)

{

    for (int i = 0; i < ALPHABET_SIZE; i++)

        if (root->children[i])

            return false;

    return true;

}

  
// Рекурсивная функция для удаления ключа из заданного Trie

TrieNode* remove(TrieNode* root, string key, int depth = 0)

{

    // Если дерево пусто

    if (!root)

        return NULL;

    // Если обрабатывается последний символ ключа

    if (depth == key.size()) {

        // Этот узел больше не является концом слова после

        // удаление данного ключа

        if (root->isEndOfWord)

            root->isEndOfWord = false;

        // Если дан не префикс другого слова

        if (isEmpty(root)) {

            delete (root);

            root = NULL;

        }

        return root;

    }

    // Если не последний символ, повторить для ребенка

    // получено с использованием значения ASCII

    int index = key[depth] - 'a';

    root->children[index] = 

          remove(root->children[index], key, depth + 1);

    // Если у root нет дочернего элемента (его единственный дочерний элемент получен

    // удалено), и это не конец другого слова.

    if (isEmpty(root) && root->isEndOfWord == false) {

        delete (root);

        root = NULL;

    }

    return root;

}

  
// Водитель

int main()

{

    // Клавиши ввода (используйте только 'a' до 'z'

    // и нижний регистр)

    string keys[] = { "the", "a", "there",

                      "answer", "any", "by",

                      "bye", "their", "hero", "heroplane" };

    int n = sizeof(keys) / sizeof(keys[0]);

    struct TrieNode* root = getNode();

    // Построить три

    for (int i = 0; i < n; i++)

        insert(root, keys[i]);

    // Поиск разных ключей

    search(root, "the") ? cout << "Yes\n" : cout << "No\n";

    search(root, "these") ? cout << "Yes\n" : cout << "No\n";

    remove(root, "heroplane");

    search(root, "hero") ? cout << "Yes\n" : cout << "No\n";

    return 0;

}