트라이

개요

트라이

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태

• 장단점
  • 시간복잡도는 O(L: 탐색 문자열 길이) 로, 문자 하나하나 비교하는 것에 비해 효율적이다.
  • 각 노드마다 자식의 포인터를 모두 저장하고 있어, 메모리 소비가 크다.

원리

트라이의 구조

1. 루트는 아무런 값이 없다.
2. 삽입할 문자열의 문자를 각각 노드로 만들어, 부모-자식으로 연결짓는다.
3. 문자열의 마지막 문자는 해당 문자열의 종료 지점을 나타내는 플래그를 True로 설정한다. 위의 그림에서 노란색 노드들은 단어의 마지막 문자여서 Flag가 True이다.

구현

트라이의 노드

노드의 구성요소

3가지의 필수 정보가 필요하다.

1. 문자 값
2. 자식 노드 포인터를 저장할 자료구조(주로 딕셔너리)
3. 해당 노드가 단어의 마지막인지 나타내는 Flag

트라이 노드

class TrieNode:
    def __init__(self, character=None):
        self.c = character
        self.children = {} # key: 자식 노드의 문자, value: 자식 노드
        self.is_end = False # 해당 문자를 마지막으로 하는 문자열 존재 유무
 
    def append(self, child_char, child_node):
        self.children[child_char] = child_node
 
    def pop(self, child_char):
        if child_char in self.children:
            del self.children[child_char]

트라이 본체

초기화

트라이 초기화

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

조회

트라이 조회

# 정확한 문자 탐색
    def search(self, string):
        current = self.head
        for c in string:
	        # 다음 문자가 존재하는지 확인
            if c not in current.children:
                return False
            current = current.children[c]
        # Flag 확인
        return current.is_end

삽입

트라이 삽입

    def add(self, string):
        if len(string) == 0:
            return
            
        current = self.head
        for c in string:
	        # 해당 문자의 자식 노드가 없으면 추가
            if c not in current.children:
                current.children[c] = TrieNode(c)
            current = current.children[c]
        # Flag 설정
        current.is_end = True

삭제

삭제 기능이 조금 복잡하다.

원리는 다음과 같다.

1. 마지막 문자까지 순회하면서 (부모 노드, 현재 문자) 스택을 만든다.
   • 노드를 역순으로 지우기 위함
2. 역순으로 자식노드의 Flag와 children 을 확인하며 삭제 처리한다.
   • Flag가 false이고, children이 없는 경우에만 노드를 삭제
3. 반복적으로 부모노드에 대해 2번을 반복한다.

트라이 삭제

def delete(self, string):
        # (부모 노드, 문자) 스택
        stack = []
        current = self.head
 
        # 스택 초기화
        for c in string:
            # 존재하는 문자인지 확인
            if c not in current.children:
                return False
            stack.append((current, c))
            current = current.children[c]
 
        # 존재하는 문자열인지 확인
        if not current.is_end:
            return False
        
        # Flag 설정
        current.is_end = False
 
        # 마지막 문자의 자식 노드가 있으면 종료
        if current.children:
            return True
        
        # 부모노드로 재귀 진행: 자식 노드가 없고 Flag가 False여야 한다.
        for parent, char in reversed(stack):
            del parent.children[char]
            if parent.is_end or parent.children:
                break
 
        return True

전체 코드

트라이 구현

class TrieNode:
    def __init__(self, character=None):
        self.c = character
        self.children = {}
        self.is_end = False
 
    def append(self, child_char, child_node):
        self.children[child_char] = child_node
 
    def pop(self, child_char):
        if child_char in self.children:
            del self.children[child_char]
 
class Trie:
    def __init__(self):
        self.head = TrieNode()
 
    def add(self, string):
        if len(string) == 0:
            return
        current = self.head
        for c in string:
            if c not in current.children:
                current.children[c] = TrieNode(c)
            current = current.children[c]
        current.is_end = True
        
    def delete(self, string):
        # (부모 노드, 문자) 스택
        stack = []
        current = self.head
 
        # 스택 초기화
        for c in string:
            # 존재하는 문자인지 확인
            if c not in current.children:
                return False
            stack.append((current, c))
            current = current.children[c]
 
        # 존재하는 문자열인지 확인
        if not current.is_end:
            return False
        
        # Flag 설정
        current.is_end = False
 
        # 마지막 문자의 자식 노드가 있으면 종료
        if current.children:
            return True
        
        # 부모노드로 재귀 진행: 자식 노드가 없고 Flag가 False여야 한다.
        for parent, char in reversed(stack):
            del parent.children[char]
            if parent.is_end or parent.children:
                break
 
        return True
    
    # 정확한 문자 탐색
    def search(self, string):
        current = self.head
        for c in string:
            if c not in current.children:
                return False
            current = current.children[c]
        return current.is_end