Введение в Trie — учебные пособия по структуре данных и алгоритмам

Опубликовано: 12 Декабря, 2022

Trie data structure is defined as a Tree based data structure that is used for storing some collection of strings and performing efficient search operations on them. The word Trie is derived from reTRIEval, which means finding something or obtaining it. 

Trie follows some property that If two strings have a common prefix then they will have the same ancestor in the trie. A trie can be used to sort a collection of strings alphabetically as well as search whether a string with a given prefix is present in the trie or not.

Нужна структура данных Trie?

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

Преимущества структуры данных Trie по сравнению с хеш-таблицей:

Структура данных trie имеет следующие преимущества перед хэш-таблицей:

  • Мы можем эффективно выполнять префиксный поиск (или автозаполнение) с помощью Trie.
  • Мы можем легко вывести все слова в алфавитном порядке, что нелегко сделать с помощью хеширования.
  • В структуре данных Trie нет накладных расходов на хэш-функции.
  • Поиск строки даже в большом наборе строк в структуре данных Trie может быть выполнен с временной сложностью O (L) , где L — количество слов в строке запроса. Это время поиска может быть даже меньше O(L), если строка запроса не существует в дереве.

Свойства структуры данных Trie

Теперь мы уже знаем, что Trie имеет древовидную структуру. Поэтому очень важно знать его свойства.
Ниже приведены некоторые важные свойства структуры данных Trie:

  • В каждом Trie есть один корневой узел.
  • Каждый узел Trie представляет собой строку, а каждое ребро представляет собой символ.
  • Каждый узел состоит из хэш-карт или массив указателей , где каждый индекс представляет символ и флаг, указывающий, заканчивается ли какая-либо строка в текущем узле.
  • Структура данных Trie может содержать любое количество символов, включая алфавиты , числа и специальные символы . Но в этой статье мы обсудим строки с символами az. Следовательно, для каждого узла требуется только 26 указателей, где 0-й индекс представляет символы «a» , а 25-й индекс представляет символы «z» .
  • Каждый путь от корня к любому узлу представляет собой слово или строку.

Ниже приведен простой пример структуры данных Trie.

Как работает структура данных Trie?

Мы уже знаем, что структура данных Trie может содержать любое количество символов, включая алфавиты , числа и специальные символы . Но в этой статье мы обсудим строки с символами az . Следовательно, для каждого узла требуется только 26 указателей, где 0-й индекс представляет символы «a» , а 25-й индекс представляет «z» .

Любое строчное английское слово может начинаться с az , затем следующая буква слова может быть az , третья буква слова снова может быть az и так далее. Итак, для хранения слова нам нужно взять массив (контейнер) размером 26 и изначально все символы пустые, так как слов нет, и это будет выглядеть так, как показано ниже.

Давайте посмотрим, как слово « и » и « муравей » хранится в структуре данных Trie:

  1. Сохраните « и » в структуре данных Trie:
    • Слово « и » начинается с « а », поэтому мы будем отмечать позицию « а » как заполненную в узле Trie, который представляет использование «а».
    • После размещения первого символа для второго символа снова есть 26 возможностей . Итак, из « а » снова есть массив размером 26 для хранения 2-го символа.
    • Второй символ — « n », поэтому от « a » мы перейдем к « n » и отметим « n » во втором массиве как использованный.
    • После « n » третьим символом является « d », поэтому отметьте позицию « d » как используемую в соответствующем массиве.
  2. Сохраните « ant » в структуре данных Trie:
    • Слово « муравей » начинается с « а », а позиция « а » в корневом узле уже занята. Таким образом, не нужно заполнять его снова, просто перейдите к узлу ' a ' в Trie.
    • Для второго символа « n » мы можем заметить, что позиция «n» в узле «a» уже заполнена. Таким образом, нет необходимости заполнять его снова, просто перейдите к узлу 'n' в Trie.
    • Для последнего символа ' t ' слова позиция для ' t ' в узле ' n ' не заполняется. Итак, заполнили позицию ' t ' в узле ' n ' и перешли к узлу ' t '.

После запоминания слов «и» и «муравей» Trie будет выглядеть так:

Представление узла Trie:

Каждый узел Trie состоит из массива указателей символов или хэш-карты и флага, показывающего, заканчивается ли слово на этом узле или нет. Но если слова содержат только буквы нижнего регистра (например, az), то мы можем определить Trie Node с помощью массива вместо хэш-карты.

C++




struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
 
    // This will keep track of number of strings that are
    // stored in the Trie from root node to any Trie node.
    int wordCount = 0;
};

Java



public class TrieNode {
    public TrieNode[] children;
    public int wordCount;
 
    public TrieNode()
    {
        children = new TrieNode[26];
        // This will keep track of number of strings that
        // are stored in the Trie from root node to any Trie
        // node.
        wordCount = 0;
    }
}
Python



# Python code
class TrieNode:
 
    # Trie node class
    def _init_(self):
        self.children = [None for _ in range(26)]
 
        # This will keep track of number of strings that are
        # stored in the Trie from root node to any Trie node.
        self.wordCount = 0
         
        # This code is contributed by ishankhandelwals.
C#



// Include namespace system
using System;
 
 
public class TrieNode
{
    public TrieNode[] children;
    public int wordCount;
    public TrieNode()
    {
        this.children = new TrieNode[26];
        // This will keep track of number of strings that
        // are stored in the Trie from root node to any Trie
        // node.
        this.wordCount = 0;
    }
}
Javascript



// JS code
class TrieNode {
 
    constructor()
    {
        this.children = new Array(26);
        // This will keep track of number of strings that are
        // stored in the Trie from root node to any Trie node.
        this.wordCount = 0;
    }
}
 
// This code is contributed by ishankhandelwals.
Основные операции со структурой данных Trie:
  1. Вставка
  2.  Поиск
  3.  Удаление
1. Вставка в структуру данных Trie:
Эта операция используется для вставки новых строк в структуру данных Trie. Давайте посмотрим, как это работает:
Давайте попробуем вставить «и» и «муравей» в этот Trie:
Из приведенного выше представления вставки мы можем видеть, что слова « и » и « муравей » имеют общий узел (то есть «an»), это происходит из-за свойства структуры данных Trie: если две строки имеют общий префикс тогда у них будет один и тот же предок в дереве.
Теперь давайте попробуем вставить «папа» и «до»:
Реализация вставки в структуру данных Trie:
Алгоритм:
  1. Определите функцию вставки (TrieNode *root, string &word) , которая будет принимать два параметра: один для корня, а другой для строки, которую мы хотим вставить в структуру данных Trie.
  2.  Теперь возьмите другой указатель currentNode и инициализируйте его корневым узлом.
  3.  Перебрать длину заданной строки и проверить, является ли значение NULL или нет в массиве указателей на текущий символ строки.
    •  Если это NULL , создайте новый узел и укажите текущий символ на этот вновь созданный узел.
    •  Переместите курсор на только что созданный узел.
  4.  Наконец, увеличьте wordCount последнего currentNode, это означает, что есть строка, заканчивающаяся currentNode.
Ниже приведена реализация вышеуказанного алгоритма:
C++



void insert_key(TrieNode* root, string& key)
{
    // Initialize the currentNode pointer
    // with the root node
    TrieNode* currentNode = root;
 
    // Iterate across the length of the string
    for (auto c : key) {
 
        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode->childNode == NULL) {
 
            // If node for current character does not exist
            // then make a new node
            TrieNode* newNode = new TrieNode();
 
            // Keep the reference for the newly created
            // node.
            currentNode->childNode = newNode;
        }
 
        // Now, move the current node pointer to the newly
        // created node.
        currentNode = currentNode->childNode;
    }
 
    // Increment the wordEndCount for the last currentNode
    // pointer this implies that there is a string ending at
    // currentNode.
    currentNode->wordCount++;
}
Java



static void insert(TrieNode root, String key)
{
    // Initialize the currentNode pointer with the root node
    TrieNode currentNode = root;
 
    for (int i = 0; i < key.length(); i++) {
        int index = key.charAt(i) - "a";
 
        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode.childNode[index] == null) {
 
            // Keep the reference for the newly created
            // node.
            currentNode.childNode[index] = new TrieNode();
        }
 
        // Now, move the current node pointer to the newly
        // created node.
        currentNode = currentNode.childNode[index];
    }
 
    // Increment the wordEndCount for the last currentNode
    // pointer this implies that there is a string ending at
    // currentNode.
    currentNode.wordCount++;
}
Javascript



// JS code for above approach
function insert_key(root, key)
{
    // Initialize the currentNode pointer
    // with the root node
    let currentNode = root;
    // Iterate across the length of the string
    for (let i=0;i<key.length;i++) {
        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode.childNode[key[i]- "a"] == NULL) {
            // If node for current character does not exist
            // then make a new node
            let newNode = new TrieNode();
            // Keep the reference for the newly created
            // node.
            currentNode.childNode[key[i] - "a"] = newNode;
        }
        // Now, move the current node pointer to the newly
        // created node.
        currentNode = currentNode.childNode[key[i] - "a"];
    }
    // Increment the wordEndCount for the last currentNode
    // pointer this implies that there is a string ending at
    // currentNode.
    currentNode.wordCount++;
}
C#



static void insert(TrieNode root, string key)
{
    // Initialize the currentNode pointer with the root node
    TrieNode currentNode = root;
 
    for (int i = 0; i < key.Length; i++) {
        int index = key[i] - "a";
 
        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode.childNode[index] == null) {
 
            // Keep the reference for the newly created
            // node.
            currentNode.childNode[index] = new TrieNode();
        }
 
        // Now, move the current node pointer to the newly
        // created node.
        currentNode = currentNode.childNode[index];
    }
 
    // Increment the wordEndCount for the last currentNode
    // pointer this implies that there is a string ending at
    // currentNode.
    currentNode.wordCount++;
}
2. Поиск в структуре данных Trie:
Операция поиска в Trie выполняется аналогично операции вставки, но с той лишь разницей, что всякий раз, когда мы обнаруживаем, что массив указателей в узле curr не указывает на текущий символ слова , мы возвращаем false вместо создания нового узла. для этого текущего символа слова.
Эта операция используется для поиска того, присутствует ли строка в структуре данных Trie или нет. В структуре данных Trie есть два подхода к поиску.
  1. Найдите, существует ли данное слово в Trie.
  2.  Найдите, существует ли в Trie какое-либо слово, начинающееся с данного префикса.
В обоих подходах используется одинаковая схема поиска. Первым шагом в поиске заданного слова в Trie является преобразование слова в символы, а затем сравнение каждого символа с узлом trie из корневого узла. Если текущий символ присутствует в узле, перейти к его дочерним элементам. Повторяйте этот процесс, пока не будут найдены все символы.
2.1 Поиск префикса в структуре данных Trie:
Найдите префикс « an » в структуре данных Trie.
Реализация поиска префиксов в структуре данных Trie:
C++



bool isPrefixExist(TrieNode* root, string& key)
{
    // Initialize the currentNode pointer
    // with the root node
    TrieNode* currentNode = root;
 
    // Iterate across the length of the string
    for (auto c : key) {
 
        // Check if the node exist for the current
        // character in the Trie.
        if (currentNode->childNode == NULL) {
           
            // Given word as a prefix does not exist in Trie
       &
            

                            

                    
                                            Структуры данных
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ

                

                                            

                            
Различия между структурой данных массива и словаря

                            
21 Января, 2023

                        

                                            

                            
TCS SDE Sheet: Вопросы и ответы для интервью

                            
12 Января, 2023

                        

                                            

                            
Множественные сравнения в очереди приоритетов С++?

                            
6 Января, 2023

                        

                                            

                            
Когда использовать Queue over ArrayList в Java?

                            
6 Января, 2023

                        

                                            

                            
Лист SDE HCL: вопросы и ответы на собеседовании

                            
12 Декабря, 2022

                        

                                            

                            
Лист SDE Netflix: вопросы и ответы для интервью

                            
12 Декабря, 2022

                        

                                            

                            
Apple SDE Sheet: вопросы и ответы на собеседовании

                            
12 Декабря, 2022

                        

                                            

                            
Лист Wipro SDE: вопросы и ответы на собеседовании

                            
12 Декабря, 2022