13. Tries (접두사 트리)

Tries

Tries are a data structure that can be used to store strings. The idea is to store the characters of the string in a tree-like structure, where each node of the tree represents a single character. We can use this structure to store strings in a way that allows us to quickly search for strings with a common prefix.

 

트라이는 문자열을 저장하는 데 사용할 수 있는 데이터 구조입니다. 이 아이디어는 문자열의 문자를 트리와 같은 구조에 저장하는 것으로, 트리의 각 노드는 하나의 문자를 나타냅니다. 이 구조를 사용하면 공통 접두사가 있는 문자열을 빠르게 검색할 수 있는 방식으로 문자열을 저장할 수 있습니다.

 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

 

 

 

Tries, 또는 접두사 트리는 문자열을 저장하기 위한 트리 기반의 데이터 구조로, 각 노드가 알파벳의 한 문자를 나타내는 방식으로 구성됩니다. 이 구조는 공통 접두사를 가진 문자열을 빠르게 검색할 수 있게 해주는 특징을 가지고 있습니다.

 

Tries는 알파벳 위에 문자열을 저장하기 위해 사용되는 다방향 트리 데이터 구조입니다. 문자열을 저장하고 검색하는 데 사용됩니다.

Tries는 트리와 같은 데이터 구조로, 노드들이 알파벳의 글자를 저장합니다. 노드를 특정 방식으로 구성함으로써, 단어와 접두사를 효율적으로 저장하고 검색할 수 있습니다.

 

 

 

In Python

class TrieNode:
    def __init__(self):
        self.children = {}  # 자식 노드를 저장하는 딕셔너리
        self.is_end_of_word = False  # 단어의 끝임

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

 

 

 

"apple", "app", "april" 세 단어를 Trie에 삽입하고, 이들 단어 및 다른 문자열들에 대한 검색 및 접두사 검사를 수행.
search 메소드는 정확한 단어가 Trie에 존재하는지 검사하며, starts_with 메소드는 주어진 접두사로 시작하는 단어가 Trie에 있는지 여부를 검사합니다.

 

 

 

 

참고

 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전