[Python] Trie(트라이)

■

 

트라이는 검색 트리의 일종으로 문자열 탐색을 위한 자료구조로 널리 쓰인다.

초창기에는 '트리'로 발음했으나, 기존의 트리와 구분하기 위해 '트라이'라 부른다. 그리고 이진 트리가 아닌 다진 트리의 형태를 띤다.

 

위 그림과 같이 트라이가 있을 때 "appear"이라는 단어를 찾는다고 하면 a → p → p → e → a → r 순서로 문자열의 길이만큼만 탐색하면 원하는 결과를 얻을 수 있다.

 

트라이는 문자열을 위한 트리의 형태이기 때문에 사실상 문자 개수만큼 자식이 있어 상당히 많은 자식 노드를 갖고 있는 트리임을 확인할 수 있다. 위 그림을 봐도 그렇다고 느낄 것이다....

 

■■

 

트라이에서의 Leaf(리프) 노드 즉, 문자의 끝을 True, 나머지 상위 노드(문자)들은 False인 상태를 나타내며 구성된다.

이게 무슨 말이냐면...

위 그림처럼 된다는 뜻이다. 간단히 말해서 문자의 끝을 True로 구분하면서 문자의 완성을 알려준다.

 

자, 이제 구현을 해보자...

 

#TrieNode를 구성할 class를 먼저 정의한다
from collections import defaultdict
class TrieNode:
	def __init__(self):
    	self.word = False #기본적으로 문자의 끝이 아닌이상 False를 default값으로 넣어준다
        self.children = defaultdict(TrieNode) 
        #defaultdict를 사용하지 않으면 삽입할때마다 자식이 있는지 없는지 확인해야한다.
        #class로 정의한 TrieNode는 하나의 Type이므로 삽입시 TrieNode Type으로 삽입될 것이다.

class를 정의해보았으니 Insert(삽입)을 먼저 구현해보자

class Trie:
	def __init__(self):
    	self.root = TrieNode() #root는 항상 있는 것이니 TrueNode로 미리 정의해두겠다
    
    def insert(self, word):
    	node = self.root #가장 첫 번째 글자를 root로 정의한다
        for char in word:
        	#한 글자 한 글자씩 root의 자식에 처넣는다
            #여기서 class를 정의할때 node.chileren을 defaultdict를 사용하여 만들었기 때문에 그냥 넣을 수 있는 것이다.
        	node = node.children[char]
        node.word = True #위 에서 한 글자씩 다 넣었으니 마지막 글자는 끝이므로 True로 만들어준다.

마지막으로 문자가 존재하는지 확인하는 것을 구현할 것인데 두 가지로 나누어서 구현할 것이다.

첫 번째는 문자가 존재하는지 찾을 것이고 두 번째는 문자로 시작하는 문자가 존재하는지 찾을 것이다.

#첫 번째로 문자가 존재 여부를 알아내보자
def search(self, word):
	node = self.root #이것도 삽입할때처럼 첫 번째 문자를 root로 지정한다
    for char in word:
    	if char not in node.children:
        	#찾는 문자인 word를 for문으로 돌렸을때 중간에 노드가 끊겼다면 문자가 존재하지 않는 것이므로 False를 return
            return False
        node = node.children[char] #다음 글자를 시작으로 그 다음 글자가 있는 탐색
   return node.word #for문이 다 돌면 word를 찾았다는 의미이므로 문자의 끝(true)을 return한다.     

#두 번째로 문자로 시작하는 문자가 있는지 알아내보자
def startword(self, start):
	node = self.root #앞에서 했던거랑 똑같으다...
    for char in start:
    	if char not in node.children:
        	#여기까지는 위에서처럼 중간에 자식 노드가 없으면 start로 시작하는 문자가 없다는 것이다
            return False
        node = node.children[char] #다음 글자 탐색
    return True #위의 for문을 다 돌았으면 start로 시작하는 문자가 있다는 것이므로 True를 return

작성하면서도 느끼는 거지만 둘 다 거기서 거기네.....