자료구조 - 트라이 (Trie)

1. 트라이란?

  트라이(Trie)란 Prefix Tree, Digital Tree, Retrieval Tree라고도 부르며 문자열을 빠르게 검색할 수 있는 자료 구조이다. K진 트리 구조 이고 단어 사전을 트라이로 생성 후 찾을 단어를 트라이를 사용하여 검색한다. 트라이의 Root 노드는 항상 공백문자열(빈 문자열) 상태를 의미한다.

 

2. 트라이 구축하기

① 트라이 노드 설계

class Node
	Ojbect data
    Node child[]

② 단어 사전의 입력할 단어를 트라이에 삽입

③ 루트 노드부터 시작하여 단어의 첫 글자부터 트라이를 탐색

④ 만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동

⑤ 만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식이 없다면, 새로운 자식을 추가

⑥ 단어를 삽입 후, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가

 

3. 트라이를 이용하여 검색하기

① 루트 노드부터 시작하여 검색할 단어의 첫 글자부터 트라이를 탐색

② 만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동

③ 만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식이 없다면, 검색할 단어는 단어사전에 존재하지 않는 단어로 처리

④ 탐색이 완료되었다면, 탐색된 마지막 노드의 정보를 이용