문자열 자료구조 Trie 알고리즘 기본개념 이해하고 삽입, 추가 직접 구현해보기

1. 문자열 단어 저장

 

'hello', 'hi', 'hey' 등을 저장하고자 할때, 생각할 수 있는 방법중 하나는 dictionary에 저장하는 것이다

 

d = {'hello':1, 'hi':1, 'hey':1}

 

단어를 key값으로 저장해두면, 특정 단어를 찾고자 할때, d['hello']같이 key로 접근해서 1인지 확인해보면 되니까 O(1)로 바로 찾을 수 있는 장점이 있다

 

하지만 공간복잡도 측면에서 단어가 100만개가 있다면 100만개의 공간이나 필요할 것이다

 

 

2. Trie 자료구조

 

Trie 자료구조는 효율적인 공간복잡도를 가지면서도, 시간복잡도도 충분히 효율적으로 만드는 문자열 저장 자료구조라고 할 수 있다.

 

dictionary보다 조금 느리지만, 단어를 찾는데 단어를 구성하는 알파벳(문자)개수만큼 시간이 걸린다

 

문자열의 집합을 다음과 같이 저장하는 자료구조가 트라이이다.

 

루트에서부터 시작해서 초록색 원이 있는 곳 까지 읽어나가면 하나의 단어에 대응시킬 수 있다.

 

 

 

3. 예시 - 저장

 

hello라는 단어를 저장할때... 아래와 같은 트리 형태로 저장

 

단어의 모든 문자를 저장했을때 마지막에 단어가 끝났다는 표시를 하는 flag가 존재한다

 

 

 

만약 hey를 저장하고 싶다면 어떻게 해야할까?

 

똑같이 다음과 같이 한다면...

 

 

오히려 공간이 낭비다

 

hello를 저장한 트리에 이어서 h와 e가 동일하므로 이를 이용한다면 공간을 효율적으로 사용할 수 있게 된다

 

 

 

마찬가지로 hi를 저장한다면...

 

 

 

4. 예시 - 단어 찾기

 

위와 같이 저장된 자료구조에서 hello를 찾고자 한다면?

 

h, e, l, l, o 순으로 찾다가 마지막 flag *을 찾는다면, 자료구조에 hello가 있다는 뜻이다

 

 

 

만약 he라는 단어를 찾고자 한다면 어떻게 될까

 

h, e를 찾았는데... 문자열의 끝을 알리는 flag *이 그 뒤에 존재하지 않는다

 

그러므로 실제 자료구조에 he라는 단어가 저장되어 있는 것은 아니다

 

 

 

5. 구현 예시 - add함수

 

add함수의 경우 word를 받아 word를 trie에 추가하는 함수

 

예를 들어 'hello'를 저장한다고 생각해봐

 

현재 노드를 self.head = {} 빈 dictionary로 설정

 

단어 hello의 문자 h,e,l,l,o를 순차적으로 확인

 

h는 {}에 존재하지 않으므로... {'h':{}}으로 저장시켜준다

 

그리고 현재 노드를 'h':{}으로 바꿔주는거지

 

그림으로 나타내보면...

 

 

현재 이런 상태인거임... 다음 문자 e는 이제 존재하지 않으므로.. h의 자식 노드로서 'h':{'e':{}}형태로 저장된다는 소리지

 

 

이게 반복되면.. hello는 다음과 같이 저장될 것이다

 

 

그리고 마지막에 단어가 끝났다는 표시 flag도 저장시켜줘야한다

 

    #단어 추가
    def add(self, word):
        
        #현재 노드
        current_node = self.head

        #현재 들어온 단어 word를 문자 char별로 순차적으로 확인

        for char in word:
            
            #현재 노드에 문자가 존재하지 않는다면...
            if char not in current_node:
                
                #현재 노드에 문자 char을 넣어준다
                current_node[char] = {}
            
            #현재 노드를 방금 넣어준 문자 노드로 교체
            #다음에 볼 문자를 현재 문자 노드의 자식 노드에 넣어줄 수 있도록
            current_node = current_node[char]
        
        #모든 문자를 넣었다면 마지막이라는 flag표시
        current_node['*'] = True

 

 

만약에 이 상태에서.. hey를 저장한다고 생각해보자

 

hey의 문자를 순차적으로 볼건데

 

현재 self.head에는 {'h':{'e':{'l':{'l':{'o':{'*':True}}}}}} 이런 느낌으로 되어 있을거야

 

h가 존재하니까... 다음은 'h'의 value인 {'e':{'l':{'l':{'o':{'*':True}}}}}을 볼거고..

 

e가 존재하니까.. 'e'의 value인 {'l':{'l':{'o':{'*':True}}}}를 볼거고...

 

'e'의 value에는 y는 존재하지 않으니까..

 

{'l':{'l':{'o':{'*':True}}}, 'y': {}} 으로 새로운 key-value쌍이 들어간다

 

그리고 마지막이라는 flag표시가 추가될 것이다

 

{'l':{'l':{'o':{'*':True}}}, 'y': {'*':True}}  이런 느낌으로?

 

 

6. 구현 예시 -search함수

 

그럼 단어를 검색하는 함수 search는 어떻게 만들까

 

역시 단어 word를 받으면.. 문자 하나씩 순차적으로 확인할것이다.

 

만약에 현재 노드에 현재 확인하는 문자가 존재하지 않는다면 False를 바로 return하면 될 것이다

 

그러면 문자가 존재한다면? 다음 자식으로 넘어가면 된다

 

여기서 자식은 current_node[char]로 할 수 있을 것

 

모든 문자를 순회하고나서도 False를 return하지 못했다면, 마지막 flag '*'이 존재하는지 확인해본다

 

'*'이 존재한다면... 현재 확인하고자 하는 문자가 있다는 뜻으로 True를 return하고..

 

존재하지 않는다면 hello에서 he만 확인했듯이.. 부분문자열로서만 존재하고 있다는 뜻으로 False를 return 

 

    #단어 찾기

    def search(self,word):
        
        current_node = self.head

        #찾고자 하는 단어의 문자를 순차적으로 확인

        for char in word:
            
            #현재 노드에 문자가 존재하지 않는다면..
            if char not in current_node:
                
                return False #그 단어는 자료구조에 저장되어 있지 않다
            
            #존재한다면..
            #현재 노드를 그 문자의 노드로 변경해서
            #그 문자의 자식 노드를 확인할 수 있도록
            current_node = current_node[char]
        
        #모든 문자를 순회했더니
        #마지막 flag가 존재한다면..
        if '*' in current_node:
            
            return True
        
        #마지막 flag가 존재하지 않는다면..
        #hello에서 he만 본것처럼.. 단순히 부분문자열로만 존재하고 있다
        else:
            
            return False

 

 

7. 구현 예시 - Trie 자료구조

 

Trie 자료구조 기본 형태 코드 종합

 

self.head는 trie의 현재 노드를 나타내는 dictionary

 

단어를 추가하는 add함수와 단어를 검색하는 search 함수로 구성

 

시간복잡도는 추가, 검색 모두 O(문자열 길이)라고 함

 

class Trie:
    
    def __init__(self):
    
        self.head = {} #문자가 저장되는 Trie
        
    #단어 추가
    def add(self, word):
        
        #현재 노드
        current_node = self.head

        #현재 들어온 단어 word를 문자 char별로 순차적으로 확인

        for char in word:
            
            #현재 노드에 문자가 존재하지 않는다면...
            if char not in current_node:
                
                #현재 노드에 문자 char을 넣어준다
                current_node[char] = {}
            
            #현재 노드를 방금 넣어준 문자 노드로 교체
            #다음에 볼 문자를 현재 문자 노드의 자식 노드에 넣어줄 수 있도록
            current_node = current_node[char]
        
        #모든 문자를 넣었다면 마지막이라는 flag표시
        current_node['*'] = True
    

    #단어 찾기

    def search(self,word):
        
        current_node = self.head

        #찾고자 하는 단어의 문자를 순차적으로 확인

        for char in word:
            
            #현재 노드에 문자가 존재하지 않는다면..
            if char not in current_node:
                
                return False #그 단어는 자료구조에 저장되어 있지 않다
            
            #존재한다면..
            #현재 노드를 그 문자의 노드로 변경해서
            #그 문자의 자식 노드를 확인할 수 있도록
            current_node = current_node[char]
        
        #모든 문자를 순회했더니
        #마지막 flag가 존재한다면..
        if '*' in current_node:
            
            return True
        
        #마지막 flag가 존재하지 않는다면..
        #hello에서 he만 본것처럼.. 단순히 부분문자열로만 존재하고 있다
        else:
            
            return False

 

 

 

 

참조

 

[코딩인터뷰] 트라이 (trie) - YouTube

 

 

 

 

https://blog.encrypted.gg/1059

[실전 알고리즘] 0x1F강 - 트라이