Рубрики

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

В предыдущем посте о trie мы описали, как вставить и найти узел в trie. Вот алгоритм, как удалить узел из Trie.

Во время операции удаления мы удаляем ключ снизу вверх, используя рекурсию. Ниже приведены возможные условия при удалении ключа из дерева,

  1. Ключ не может быть в три. Операция удаления не должна изменять три.
  2. Ключ представлен как уникальный ключ (ни одна часть ключа не содержит другого ключа (префикса), а сам ключ не является префиксом другого ключа в файле trie). Удалить все узлы.
  3. Ключ — префиксный ключ другого длинного ключа в Trie. Снимите отметку с листового узла.
  4. Ключ присутствует в Trie, имея по крайней мере еще один ключ в качестве префиксного ключа. Удалить узлы от конца ключа до первого конечного узла самого длинного префиксного ключа.

В приведенном ниже коде представлен алгоритм для реализации вышеуказанных условий.

C ++

// 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;

}

Выход:

Yes
No
Yes

Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes