Рубрики

Трие | (Вставить и найти)

Trie — это эффективная информационная база данных Trie val. Используя Trie, сложности поиска могут быть доведены до оптимального предела (длина ключа). Если мы храним ключи в бинарном дереве поиска, хорошо сбалансированному BST потребуется время, пропорциональное M * log N , где M — максимальная длина строки, а N — количество ключей в дереве. Используя Trie, мы можем искать ключ за O (M) время. Однако штраф наложен на требования к хранилищу Trie ( для более подробной информации, пожалуйста, обратитесь к Applications of Trie )

Каждый узел Trie состоит из нескольких ветвей. Каждая ветвь представляет собой возможный символ ключей. Нам нужно пометить последний узел каждого ключа как конец слова. Поле узла Trie isEndOfWord используется для различения узла как конца слова. Простая структура для представления узлов английского алфавита может быть следующей,

// Trie node
struct TrieNode
{
struct TrieNode *children[ALPHABET_SIZE];

// isEndOfWord равно true, если узел
// представляет конец слова
bool isEndOfWord;
};

Вставка ключа в Trie — это простой подход. Каждый символ клавиши ввода вставляется как отдельный узел Trie. Обратите внимание, что потомки — это массив указателей (или ссылок) на триуровневые узлы следующего уровня. Ключевой символ действует как индекс в массиве потомков . Если входной ключ является новым или является расширением существующего ключа, нам нужно создать несуществующие узлы ключа и отметить конец слова для последнего узла. Если клавиша ввода является префиксом существующей клавиши в Trie, мы просто помечаем последний узел клавиши как конец слова. Длина ключа определяет глубину Trie.

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

Следующая картинка объясняет конструкцию дерева с использованием ключей, приведенных в примере ниже,

                       root
                    /   \    \
                    t   a     b
                    |   |     |
                    h   n     y
                    |   |  \  |
                    e   s  y  e
                 /  |   |
                 i  r   w
                 |  |   |
                 r  e   e
                        |
                        r

На рисунке каждый символ имеет тип trie_node_t . Например, корень имеет тип trie_node_t, и его дочерние элементы a , b и t заполнены, все остальные узлы root будут равны NULL. Аналогично, «a» на следующем уровне имеет только одного ребенка («n»), все остальные дети имеют значение NULL. Узлы листа синие .

Стоимость вставки и поиска O (key_length) , однако требования к памяти Trie — O (ALPHABET_SIZE * key_length * N), где N — количество ключей в Trie. Существует эффективное представление узлов дерева (например, сжатого дерева , троичного дерева поиска и т. Д.), Чтобы минимизировать требования памяти к дереву.

C ++

// C ++ реализация поиска и вставки
// операции на Трие
#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);

}

  
// Водитель

int main()

{

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

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

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

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

                     "bye", "their" };

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

    return 0;

}

С

// C реализация операций поиска и вставки
// на Трие
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

  
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

  
// Размер алфавита (количество символов)
#define ALPHABET_SIZE (26)

  
// Преобразует текущий символ ключа в индекс
// использовать только буквы от 'a' до 'z' и строчные буквы
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

  
// Три узла

struct TrieNode

{

    struct TrieNode *children[ALPHABET_SIZE];

  

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

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

    bool isEndOfWord;

};

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

struct TrieNode *getNode(void)

{

    struct TrieNode *pNode = NULL;

  

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

  

    if (pNode)

    {

        int i;

  

        pNode->isEndOfWord = false;

  

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

            pNode->children[i] = NULL;

    }

  

    return pNode;

}

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

void insert(struct TrieNode *root, const char *key)

{

    int level;

    int length = strlen(key);

    int index;

  

    struct TrieNode *pCrawl = root;

  

    for (level = 0; level < length; level++)

    {

        index = CHAR_TO_INDEX(key[level]);

        if (!pCrawl->children[index])

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

  

        pCrawl = pCrawl->children[index];

    }

  

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

    pCrawl->isEndOfWord = true;

}

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

bool search(struct TrieNode *root, const char *key)

{

    int level;

    int length = strlen(key);

    int index;

    struct TrieNode *pCrawl = root;

  

    for (level = 0; level < length; level++)

    {

        index = CHAR_TO_INDEX(key[level]);

  

        if (!pCrawl->children[index])

            return false;

  

        pCrawl = pCrawl->children[index];

    }

  

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

}

  
// Водитель

int main()

{

    // Клавиши ввода (используйте только буквы от «а» до «z» и строчные буквы)

    char keys[][8] = {"the", "a", "there", "answer", "any",

                     "by", "bye", "their"};

  

    char output[][32] = {"Not present in trie", "Present in trie"};

  

  

    struct TrieNode *root = getNode();

  

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

    int i;

    for (i = 0; i < ARRAY_SIZE(keys); i++)

        insert(root, keys[i]);

  

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

    printf("%s --- %s\n", "the", output[search(root, "the")] );

    printf("%s --- %s\n", "these", output[search(root, "these")] );

    printf("%s --- %s\n", "their", output[search(root, "their")] );

    printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );

  

    return 0;

}

Джава

// Java реализация операций поиска и вставки
// на Трие

public class Trie {

      

    // Размер алфавита (количество символов)

    static final int ALPHABET_SIZE = 26;

      

    // Три узла

    static class TrieNode

    {

        TrieNode[] children = new TrieNode[ALPHABET_SIZE];

       

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

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

        boolean isEndOfWord;

          

        TrieNode(){

            isEndOfWord = false;

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

                children[i] = null;

        }

    };

       

    static TrieNode root; 

      

    // Если нет, вставляет ключ в три

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

    // просто отмечаем листовой узел

    static void insert(String key)

    {

        int level;

        int length = key.length();

        int index;

       

        TrieNode pCrawl = root;

       

        for (level = 0; level < length; level++)

        {

            index = key.charAt(level) - 'a';

            if (pCrawl.children[index] == null)

                pCrawl.children[index] = new TrieNode();

       

            pCrawl = pCrawl.children[index];

        }

       

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

        pCrawl.isEndOfWord = true;

    }

       

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

    static boolean search(String key)

    {

        int level;

        int length = key.length();

        int index;

        TrieNode pCrawl = root;

       

        for (level = 0; level < length; level++)

        {

            index = key.charAt(level) - 'a';

       

            if (pCrawl.children[index] == null)

                return false;

       

            pCrawl = pCrawl.children[index];

        }

       

        return (pCrawl != null && pCrawl.isEndOfWord);

    }

       

    // Водитель

    public static void main(String args[])

    {

        // Клавиши ввода (используйте только буквы от «а» до «z» и строчные буквы)

        String keys[] = {"the", "a", "there", "answer", "any",

                         "by", "bye", "their"};

       

        String output[] = {"Not present in trie", "Present in trie"};

       

       

        root = new TrieNode();

       

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

        int i;

        for (i = 0; i < keys.length ; i++)

            insert(keys[i]);

       

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

        if(search("the") == true)

            System.out.println("the --- " + output[1]);

        else System.out.println("the --- " + output[0]);

          

        if(search("these") == true)

            System.out.println("these --- " + output[1]);

        else System.out.println("these --- " + output[0]);

          

        if(search("their") == true)

            System.out.println("their --- " + output[1]);

        else System.out.println("their --- " + output[0]);

          

        if(search("thaw") == true)

            System.out.println("thaw --- " + output[1]);

        else System.out.println("thaw --- " + output[0]);

         

    }

}
// Этот код предоставлен Sumit Ghosh

питон

# Python программа для вставки и поиска
# операция в трие

  

class TrieNode:

      

    # Три узла класса

    def __init__(self):

        self.children = [None]*26

  

        # isEndOfWord - True, если узел представляет конец слова

        self.isEndOfWord = False

  

class Trie:

      

    # Три класса структуры данных

    def __init__(self):

        self.root = self.getNode()

  

    def getNode(self):

      

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

        return TrieNode()

  

    def _charToIndex(self,ch):

          

        # приватная вспомогательная функция

        # Преобразует ключевой текущий символ в индекс

        # используйте только 'a' до 'z' и строчные буквы

          

        return ord(ch)-ord('a')

  

  

    def insert(self,key):

          

        # Если нет, вставляет ключ в три

        # Если ключ является префиксом узла Trie,

        # просто отмечает листовой узел

        pCrawl = self.root

        length = len(key)

        for level in range(length):

            index = self._charToIndex(key[level])

  

            # если текущий символ отсутствует

            if not pCrawl.children[index]:

                pCrawl.children[index] = self.getNode()

            pCrawl = pCrawl.children[index]

  

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

        pCrawl.isEndOfWord = True

  

    def search(self, key):

          

        # Поиск ключа в трие

        # Возвращает true, если присутствует ключ

        # в три, иначе ложь

        pCrawl = self.root

        length = len(key)

        for level in range(length):

            index = self._charToIndex(key[level])

            if not pCrawl.children[index]:

                return False

            pCrawl = pCrawl.children[index]

  

        return pCrawl != None and pCrawl.isEndOfWord

  
# функция драйвера

def main():

  

    # Клавиши ввода (используйте только буквы от «а» до «z» и строчные буквы)

    keys = ["the","a","there","anaswe","any",

            "by","their"]

    output = ["Not present in trie",

              "Present in trie"]

  

    # Три объекта

    t = Trie()

  

    # Построить три

    for key in keys:

        t.insert(key)

  

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

    print("{} ---- {}".format("the",output[t.search("the")]))

    print("{} ---- {}".format("these",output[t.search("these")]))

    print("{} ---- {}".format("their",output[t.search("their")]))

    print("{} ---- {}".format("thaw",output[t.search("thaw")]))

  

if __name__ == '__main__':

    main()

  
# Этот код предоставлен Атулом Кумаром (www.facebook.com/atul.kr.007)

C #

// C # реализация поиска и
// вставляем операции в Trie

using System;

      

public class Trie 

{

      

    // Размер алфавита (количество символов)

    static readonly int ALPHABET_SIZE = 26;

      

    // Три узла

    class TrieNode

    {

        public TrieNode[] children = new TrieNode[ALPHABET_SIZE];

      

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

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

        public bool isEndOfWord;

          

        public TrieNode()

        {

            isEndOfWord = false;

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

                children[i] = null;

        }

    };

      

    static TrieNode root; 

      

    // Если нет, вставляет ключ в три

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

    // просто отмечаем листовой узел

    static void insert(String key)

    {

        int level;

        int length = key.Length;

        int index;

      

        TrieNode pCrawl = root;

      

        for (level = 0; level < length; level++)

        {

            index = key[level] - 'a';

            if (pCrawl.children[index] == null)

                pCrawl.children[index] = new TrieNode();

      

            pCrawl = pCrawl.children[index];

        }

      

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

        pCrawl.isEndOfWord = true;

    }

      

    // Возвращает true если ключ

    // представляет в три, иначе ложь

    static bool search(String key)

    {

        int level;

        int length = key.Length;

        int index;

        TrieNode pCrawl = root;

      

        for (level = 0; level < length; level++)

        {

            index = key[level] - 'a';

      

            if (pCrawl.children[index] == null)

                return false;

      

            pCrawl = pCrawl.children[index];

        }

      

        return (pCrawl != null && pCrawl.isEndOfWord);

    }

      

    // Водитель

    public static void Main()

    {

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

        // через 'z' и нижний регистр)

        String []keys = {"the", "a", "there", "answer"

                        "any", "by", "bye", "their"};

      

        String []output = {"Not present in trie", "Present in trie"};

      

      

        root = new TrieNode();

      

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

        int i;

        for (i = 0; i < keys.Length ; i++)

            insert(keys[i]);

      

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

        if(search("the") == true)

            Console.WriteLine("the --- " + output[1]);

        else Console.WriteLine("the --- " + output[0]);

          

        if(search("these") == true)

            Console.WriteLine("these --- " + output[1]);

        else Console.WriteLine("these --- " + output[0]);

          

        if(search("their") == true)

            Console.WriteLine("their --- " + output[1]);

        else Console.WriteLine("their --- " + output[0]);

          

        if(search("thaw") == true)

            Console.WriteLine("thaw --- " + output[1]);

        else Console.WriteLine("thaw --- " + output[0]);

          

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход :

the --- Present in trie
these --- Not present in trie
their --- Present in trie
thaw --- Not present in trie


ПРИМЕЧАНИЕ. В видео isEndOfWord называется isLeaf .

Статьи по Теме:

Проблемы практики:

  1. Три поиска и вставки
  2. Три Удалить
  3. Уникальные строки в двоичной матрице
  4. Количество различных подстрок
  5. Слово Боггл

Последние статьи о Три

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

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

Трие | (Вставить и найти)

0.00 (0%) 0 votes