Trie(접두사 트리) 소개

Trie는 특히 자동 완성, 맞춤법 검사, IP 라우팅과 같은 애플리케이션에서 문자열을 효율적으로 저장하고 검색하는 데 사용되는 트리형 데이터 구조입니다.

---

Trie의 주요 속성:

1. 노드: 각 노드는 문자를 나타냅니다.
2. 루트: 루트 노드는 비어 있으며 시작점 역할을 합니다.
3. 하위: 각 노드에는 문자 집합에 따라 최대 26개(영문 소문자의 경우) 이상의 하위가 있습니다.
4. 단어 끝 표시: 일부 노드는 단어 끝을 표시하기 위해 표시됩니다.

---

기본 트라이 작업:

1. 삽입

단어를 삽입하려면 트라이를 순회하고 존재하지 않는 문자에 대한 새 노드를 생성해야 합니다.

2. 검색

검색은 해당 노드를 순회하여 트리에 단어가 존재하는지 확인합니다.

3. 접두사 검색

트리에 있는 단어가 주어진 접두사로 시작하는지 확인합니다.

---

JavaScript에서 기본 Trie 구현:

class TrieNode {
    constructor() {
        this.children = {}; // Stores child nodes
        this.isEndOfWord = false; // Marks the end of a word
    }
}

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

    // Insert a word
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

---

고급 트라이 작업:

1. 단어 삭제:

단어 삭제에는 더 이상 필요하지 않은 노드를 제거하는 재귀적 접근 방식이 포함됩니다.

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth + 1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

2. 접두사가 있는 단어 개수:

주어진 접두어로 시작하는 단어 수를 세어보세요.

countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isEndOfWord ? 1 : 0;
    for (let char in node.children) {
        count += this._countWords(node.children[char]);
    }
    return count;
}

3. 자동 완성 제안:

접두사가 주어지면 해당 접두사로 시작하는 모든 단어를 반환합니다.

getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix + char));
    }

    return results;
}

---

시간 복잡도:

1. 삽입: O(L) (L = 단어 길이)
2. 검색: O(L)
3. 접두사 검색: O(L)
4. 삭제: O(L)

---

트라이의 응용:

1. 자동완성 시스템(예: 검색창, 텍스트 편집기)
2. 맞춤법 검사기.
3. IP 라우팅(가장 긴 접두사 일치).
4. 단어 게임(예: Boggle).
5. DNA 서열 매칭.

위 내용은 Trie(접두사 트리) 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!