Бор

Бор (Trie) — это структура данных для хранения и поиска строк, которая позволяет эффективно выполнять операции вставки, удаления и поиска строк. Бор представляет собой дерево, где каждый узел соответствует символу строки. Структура Бора особенно полезна при работе с большим количеством строк, таких как словари или базы данных слов.

Основные понятия

Узел (Node): Каждый узел в Боре представляет символ строки.
Ребро (Edge): Ребро соединяет два узла и помечено символом алфавита.
Корень (Root): Начальный узел, который не содержит символа.
Лист (Leaf): Узел, который обозначает конец строки.

Пример

Рассмотрим пример Бора для набора строк: ["cat", "car", "dog"].

        (root)
       /       \
      c         d
     / \        |
    a   a       o
   /     \      |
  t       r     g

Операции над Бором

Вставка (Insertion):
- Начинаем с корня.
- Для каждого символа строки проверяем, существует ли соответствующий узел.
- Если узел существует, переходим к нему; если нет — создаем новый узел.
- Продолжаем до конца строки.
Поиск (Search):
- Начинаем с корня.
- Для каждого символа строки проверяем, существует ли соответствующий узел.
- Если узел существует, переходим к нему; если нет — строка не найдена.
- Если достигли конца строки и все узлы существуют, строка найдена.
Удаление (Deletion):
- Поиск строки в Боре.
- Если строка существует, удаляем узлы, которые не принадлежат другим строкам.

Реализация на C++

Структура узла

#include <iostream>
#include <unordered_map>
#include <vector>
 
struct TrieNode {
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
 
    TrieNode() : isEndOfWord(false) {}
};

Вставка строки

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
 
    void insert(const std::string &word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }
 
private:
    TrieNode* root;
};

Поиск строки

class Trie {
public:
    // ... (остальной код)
 
    bool search(const std::string &word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            node = node->children[ch];
        }
        return node->isEndOfWord;
    }
 
private:
    TrieNode* root;
};

Удаление строки

class Trie {
public:
    // ... (остальной код)
 
    bool remove(const std::string &word) {
        return removeHelper(root, word, 0);
    }
 
private:
    TrieNode* root;
 
    bool removeHelper(TrieNode* node, const std::string &word, int depth) {
        if (!node) return false;
 
        if (depth == word.size()) {
            if (!node->isEndOfWord) return false;
            node->isEndOfWord = false;
            return node->children.empty();
        }
 
        char ch = word[depth];
        if (removeHelper(node->children[ch], word, depth + 1)) {
            delete node->children[ch];
            node->children.erase(ch);
            return node->children.empty() && !node->isEndOfWord;
        }
 
        return false;
    }
};

Пример использования

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("dog");
 
    std::cout << std::boolalpha;
    std::cout << "Search for 'cat': " << trie.search("cat") << std::endl; // true
    std::cout << "Search for 'car': " << trie.search("car") << std::endl; // true
    std::cout << "Search for 'cap': " << trie.search("cap") << std::endl; // false
 
    trie.remove("car");
    std::cout << "Search for 'car' after deletion: " << trie.search("car") << std::endl; // false
 
    return 0;
}

Преимущества и недостатки

Преимущества:

Быстрое выполнение операций вставки и поиска: Время выполнения операции зависит от длины строки, а не от количества строк в Боре.
Эффективное использование памяти: Узлы, которые разделяются несколькими строками, хранятся в одном экземпляре.

Недостатки:

Высокое потребление памяти: В худшем случае, Бор может потреблять много памяти, особенно если строки имеют мало общих префиксов.
Сложность реализации: Реализация алгоритма может быть сложнее по сравнению с другими структурами данных.

Заключение

Бор является мощным инструментом для хранения и поиска строк. Он особенно полезен в приложениях, где необходимо работать с большим количеством строк, таких как автозаполнение, поиск по префиксу и анализ текстов. Эффективность и быстрота выполнения операций делают его незаменимым в задачах обработки текстовой информации.

m4lvx

Explorer

Бор