Introdução

A Trie, também conhecida como árvore de prefixo, é uma estrutura de dados especializada baseada em árvore usada para recuperação eficiente de informações.

É particularmente útil para casos de uso que envolvem pesquisa e correspondência de prefixos em strings.

1. Se eu falar sobre o Algoritmo Trie, você pode ou não estar interessado neste algoritmo

2. Mas se eu dissesse que você pode criar um algoritmo de preenchimento automático usando isso. você ficará mais animado em aprender isso.

Caso de uso deste algoritmo

1. Preenchimento automático:

um. As tentativas são frequentemente usadas em mecanismos de pesquisa ou editores de texto para implementar o recurso de preenchimento automático.
b. À medida que você começa a digitar, o aplicativo sugere possíveis conclusões com base no prefixo inserido.

2. Corretores ortográficos:

um. Tentativas podem ser usadas para implementar corretores ortográficos. Se uma palavra não estiver presente na tentativa, provavelmente ela está escrita incorretamente.
b. O try também pode sugerir correções encontrando palavras semelhantes.

3. Roteamento IP:

um. As tentativas são usadas em roteadores para armazenar tabelas de roteamento.
b. O roteador usa uma tentativa para corresponder ao prefixo mais longo, que determina o próximo salto de um pacote.

4. Armazenamento e pesquisa eficiente de strings:

um. Se você tiver um conjunto de dados de strings onde há muitos prefixos compartilhados, um teste pode armazenar essas strings usando menos espaço do que armazená-las individualmente.
b. A operação de pesquisa também é eficiente, com complexidade de tempo proporcional ao comprimento da string que você está procurando.

class Node {
    constructor() {
        this.end = false;
        this.children = {}
    }
}

class Trie {
    constructor() {
        this.root = new Node ();
    }

    insert(word) {
        let head = this.root;

        for (let i = 0; i ', current.children);

        console.log('Possible Auto Complete Values are --->');
        for (let key in current.children) {
            console.log('---> ', word key);
        }
    }
}

const test = new Trie();
test.insert('ant');
test.insert('any');
console.log(test.search('ant'));
console.log(test.search('any'));
console.log(test.search('anj'));
test.autoComplete('an')
/*
true
true
false
children =--->  {
  t: Node { end: true, children: {} },
  y: Node { end: true, children: {} }
}
Possible Auto Complete Values are --->
--->  ant
--->  any
*/

Sinta-se à vontade para entrar em contato comigo se tiver alguma dúvida/dúvida.