Рубрики
Без рубрики

Структура данных Trie – Операция вставки

Введение Trie – это специальная структура данных, в которой мы храним буквы строки…. С пометкой java, алгоритмы, учебник, интервью.

Trie – это специальная структура данных, в которой мы храним буквы строки. Это очень полезно для поиска самого длинного префикса, самой длинной длины префикса, поиска определенной строки, поиска самого длинного слова в словаре, а также для системы автозаполнения.

Мы можем структурировать нашу пробу в зависимости от наших потребностей. Обычно у нас может быть символ ch , обозначающий символ, Конец слова , который обозначает при вставке слова, достигли ли мы конца или нет, Триенод [] Триенод[26] , который действует как указатель, указывающий на индекс буквы, которую мы вставили.

class TrieNode {
    char ch;
    TrieNode [] array = new TrieNode[26];
    int wordEnd = 0;
}

Таким образом, у каждого узла trie есть символ, конец слова и массив для указания на вставленные буквы.

Мы можем выполнять операции вставки, поиска и многое другое с помощью trie.

В операции вставки мы начинаем с создания корневого узла, в котором есть слово и значение 0, в нем нет определенного символа и массива TrieNode.

Итак, предположим, что мы вставляем строку, скажем s . Мы выполняем следующие действия:

  • Начиная с корня, мы проверяем индекс a , который можно найти с помощью 'a' - . Сначала мы проверяем, является ли массив[0] нулевым или нет. Здесь массив[0] равен нулю, поэтому из 0-го индекса в корне мы создаем новый тринод с новым символом, содержащим a , так как строка, которую мы должны вставить, не закончена, и массив указателей. Теперь мы переходим к узлу а.

  • Далее мы должны вставить b и на этот раз мы начинаем со следующего узла, то есть с узла a . Так же, как и выше, мы находим правильный индекс для b используя 'b' - . Здесь мы проверяем, равен ли массив[1] нулю или нет, если он равен нулю, то создается новый узел для b создается, как указано выше, с соответствующим полем, в противном случае это означает, что мы уже вставили b и мы переходим к следующему узлу. В нашем примере азбука , новый узел для b будет создан. Теперь мы переходим к узлу b. Примечание : Конец слова по-прежнему будет равен 0, так как мы еще не закончили с нашим сильным.

  • Далее мы вставляем c путем нахождения индекса 'c' - . Мы проверяем, является ли массив[2] нулевым или нет, здесь он будет нулевым, поэтому для c узла будет сгенерирован новый узел. Здесь мы закончили со строкой, поэтому конечное значение слова будет обновлено до wordEnd + 1 .

Давайте продолжим вставлять другую строку s

  • Здесь мы снова начинаем с корня и находим индекс для первого символа, то есть здесь, который ' a' - . Итак, здесь массив[0] не равен нулю, так как мы уже вставляли его ранее, поэтому мы переходим к узлу a без создания нового узла.

  • Далее мы должны вставить b . Нахождение индекса для b , который равен 'b' - . Здесь также, когда мы проверяем массив [1] нулевой или нет из узла a, мы видим, что он уже вставлен, поэтому, не создавая новый узел, мы переходим к узлу b.

  • Следующий символ – d и мы находим индекс для d , который равен 'd' - . Если мы проверим массив[3], мы увидим, что он равен нулю, и поэтому для d создается новый узел . Поскольку d является последним символом строки, мы увеличиваем конец слова до Конец слова + 1 , чтобы указать, что мы закончили со строкой abd .

Давайте вставим еще одну строку s .

То же, что и в описанной выше процедуре, давайте сделаем это еще раз.

  • Начните с корня, найдите индекс первого символа b который 'b' - и его значение в массиве[1] равно нулю, поэтому создается новый узел для b, и мы переходим к узлу b.

  • Следующий символ – c и его индекс = 'c' - . Из узла b, если мы ищем значение массива[2], мы получаем, что оно равно нулю, и мы создаем новый узел для c и продолжаем с этим узлом.

  • Следующий символ – d и его индекс = 'd' - . Из узла c, если мы ищем значение массива[3], мы получаем, что оно равно нулю, и создается новый узел. Поскольку d является последним символом строки, мы увеличиваем слово И на Конец слова + 1 .

Окончательная структура trie после этих вставок будет:

O(количество слов * максимальная Длина Слова)

O(количество слов * максимальная Длина Слова)

class TrieNode {
    char ch;
    TrieNode [] array = new TrieNode[26];
    int wordEnd = 0;
}

public class Trie {
    TrieNode root = null;
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.array[index] == null) {
                node.array[index] = new TrieNode();
                node.array[index].ch = ch;
                node.array[index].wordEnd = 0;  
            }
            node = node.array[index];
        }
        node.wordEnd += 1;
    }
        public static void main(String [] args) {
            Trie trie = new Trie();
            String a = "abc";
            String b = "abd";
            String c = "bcd";
            trie.insert(a);
            trie.insert(b);
            trie.insert(c);
        }
}

Rohith v 07/LeetCode Топ-интервьювопросы

Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode. Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode.

Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode. Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode.

Также ответ на вопрос от CodeSignal.com: https://app.codesignal.com/

Rohithv07/Код доступа

Проблемы с кодом, которые решены.

Проблемы с кодом, которые решены.

Это видео – отличный повод узнать о три.

Оригинал: “https://dev.to/rohithv07/trie-data-structure-insert-operation-253g”

Читайте ещё по теме: