소개

접두사 트리라고도 알려진 Trie는 효율적인 정보 검색에 사용되는 특수한 트리 기반 데이터 구조입니다.

문자열 내에서 검색 및 접두사 일치와 관련된 사용 사례에 특히 유용합니다.

1. Trie 알고리즘에 대해 말씀드리면 여러분은 이 알고리즘에 관심이 있을 수도 있고 없을 수도 있습니다.

2. 하지만 이것을 사용하여 자동 완성 알고리즘을 만들 수 있다고 말씀드리고 싶습니다. 당신은 이것을 배우게 되어 더욱 기쁠 것입니다.

이 알고리즘의 사용 사례

1. 자동 완성:

에이. 시도는 자동 완성 기능을 구현하기 위해 검색 엔진이나 텍스트 편집기에서 자주 사용됩니다.
비. 입력을 시작하면 애플리케이션은 입력한 접두어를 기반으로 가능한 완성을 제안합니다.

2. 맞춤법 검사기:

에이. 맞춤법 검사기를 구현하는 데 시도를 사용할 수 있습니다. 단어가 트라이에 없으면 철자가 틀렸을 가능성이 높습니다.
비. 트리는 유사한 단어를 찾아 수정 사항을 제안할 수도 있습니다.

3. IP 라우팅:

에이. 트라이는 라우터에서 라우팅 테이블을 저장하는 데 사용됩니다.
비. 라우터는 가장 긴 접두사와 일치하는 트리를 사용하여 패킷의 다음 홉을 결정합니다.

4. 문자열을 효율적으로 저장하고 검색하려면:

에이. 공유 접두사가 많은 문자열 데이터세트가 있는 경우 트리는 개별적으로 저장하는 것보다 적은 공간을 사용하여 이러한 문자열을 저장할 수 있습니다.
비. 검색 작업은 검색 중인 문자열의 길이에 비례하여 시간 복잡도가 높아지므로 효율적입니다.

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
*/

우려사항이나 문의사항이 있으면 언제든지 문의해 주세요.