자료구조와 알고리즘 - Trie (Prefix Tree)

 

---

 

1.  Trie 개념

 Trie(트라이)는 트리 자료 구조의 일종으로, 문자열 검색과 관련된 작업에 사용됩니다. Trie는 각 노드가 하나의 문자를 나타내며, 루트 노드에서부터 각 문자의 연속으로 경로를 형성합니다. 이로써 단어 검색, 접두어 검색, 삽입 등의 작업을 빠르게 수행할 수 있습니다. 이를 응용하여 자동완성, 스펠링 체크 등에 쓰입니다.

 

- Trie의 주요 특징:

1. 계층적인 구조: 각 노드가 문자를 나타내며, 노드 간의 관계가 문자열의 구조를 반영한다.
2. 공통 접두어 공유: 비슷한 문자열은 동일한 접두어를 공유한다.
3. 빠른 검색: 문자열 검색이 효율적이다. 시간 복잡도는 O(L)이며, L은 찾고자 하는 문자열의 길이이다.

 

 

 

2. Trie 구현 방법

Trie는 문자열을 각 노드에 저장합니다. 예를 들어 ["apple", "app","banana","basic"]을 Trie에 저장하면 다음과 같은 트리로 이루어집니다.

 

 

- Trie의 기본 동작(N: 문자열의 길이)

• 삽입(Insertion): 문자열을 Trie에 추가한다.(O(N))
• 검색(Search): 특정 문자열이 Trie에 있는지 확인한다.(O(N))
• 삭제(Deletion): Trie에서 특정 문자열을 삭제한다.(O(N))

 

 

 

- 코드

class Node:
    def __init__(self):
        self.end = False # 마지막 문자열 여부, True면 마지막 문자열이다.
        self.link = dict() #자식노드여부, 빈칸이면 자식노드가 없기 때문에 마지막 문자열이다.

class Trie:

    def __init__(self):
        self.root = Node()   #root 노드를 만든다.
                
    def insert(self, word: str) -> None:
        
        cur = self.root #루트노드에서 시작한다.
        for w in word:

            if w not in cur.link:  #해당 문자열이 노드에 없다면
                cur.link[w] = Node() #새로운 노드를 연결하고
            
            cur = cur.link[w] #새로 만든 노드로 이동한다.
        
        cur.end = True  #마지막노드는 마지막 문자열이기 때문에 True로 바꾼다.
            

    def search(self, word: str) -> bool:

        cur = self.root #루트노드부터 시작해서
        for w in word:

            if w in cur.link:  # 해당 문자열이 존재하면
                cur = cur.link[w] #그 문자열 노드로 이동한다.
            else:
                return False

        return True
        

    def delete(self, word: str) -> None:
        self._delete_recursive(self.root, word, 0)

    def _delete_recursive(self, node, word, index):
        if index == len(word):
            # 단어의 끝에 도달했을 때 해당 노드의 end 플래그를 False로 설정
            if node.end:
                node.end = False
            return

        char = word[index]

        if char in node.link:
            # 다음 문자가 현재 노드에 존재하는 경우 재귀 호출
            self._delete_recursive(node.link[char], word, index + 1)

            # 삭제된 노드가 단말 노드이고 자식이 없으면 해당 노드 삭제
            # 만약 ["app","apple"]이란 단어를 저장하고 "apple"을 삭제한다면 "app"은 삭제하면 안된고 "le"만 삭제해야 한다.=> node.linke[char].end == True인 경우
            # 만약 ["banana",basic]이란 단어를 저장하고 basic을 삭제한다면 ba에서 -> [nana, sic] 으로 분기하기때문에 "banana"를 살리기 위해서 "sic"만 삭제되어야 한다.
            #=> 이경우는 node.link[char].link != None인 경우
            if not node.link[char].link and not node.link[char].end:
                del node.link[char]
        else:
            # Trie에 해당 문자열이 존재하지 않으면 삭제할 수 없음
            return

 

 

 

 

- 관련 문제

 

https://leetcode.com/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=leetcode-75

LeetCode - The World's Leading Online Programming Learning Platform

 

 

 

- 관련 문제2

 

 

 

 

 

 

 

---