[Data Structure] 트라이 트리(Trie Tree)
트라이 트리(Trie Tree)?
트라이 트리는 문자열 검색을 빠르게 해주는 트리 형태의 자료구조이다.
radix tree, prefix tree, retireval tree 라고도 한다. 여기서 트라이(Trie)는 retireval에서 따온 단어이다.
구현

위 그래프 처럼 car, cb, do, dog라는 단어를 저장한다고 가정한다.
먼저 노드를 하나 만들어 주어야 한다.
import java.util.HashMap; import java.util.Map; public class Node { private final Map<Character, Node> children; private boolean endOfWord; public Node() { children = new HashMap<>(); } public Map<Character, Node> getChildren() { return children; } public boolean isEndOfWord() { return endOfWord; } public void endOfWordToTrue() { this.endOfWord = true; } }
노드에는 그 다음 문자를 가진 노드를 저장하는 Map타입인 children과, 단어의 끝인지 확인하는 endOfWord의 인스턴스 변수를 가지고 있다.
그 다음은 Node를 사용하여 insert와 search 메서드를 가지고 있는 Trie Class를 구현해보자.
public class Trie { private final Node root; public Trie() { this.root = new Node(); } public void insert(String str) { Node curNode = this.root; char[] chars = str.toCharArray(); for (char c : chars) { curNode = curNode.getChildren().computeIfAbsent(c, key -> new Node()); } curNode.endOfWordToTrue(); } public boolean search(String str) { Node curNode = this.root; char[] chars = str.toCharArray(); for (char c : chars) { curNode = curNode.getChildren().get(c); if (curNode == null) { return false; } } return curNode.isEndOfWord(); } }
먼저 insert 메서드부터 살펴보자.
insert 메서드는 항상 root 노드부터 시작하여 자식 노드들을 탐색한다.
예를 들어, car이라는 글자를 넣는다고 가정하면 ['c', 'a', 'r'] 배열을 순차적으로 돌면서 'c' 부터 자식노드에 해당 문자를 가진 노드가 있는지 찾는 것이다.
만약 'c'를 가진 자식 노드가 있다면 해당 노드로 들어가고, 없다면 새 노드를 만들고 거기로 들어간다.
자식 노드로 들어가면 그 다음 문자인 'a'에서 다시 위 과정을 반복한다.
처음 들었던 예시를 기준으로 삽입을 진행한다고 하면, 최종적으로 다음과 같은 형태가 될 것이다.

그 다음 search 메서드를 살펴보자.
형태는 insert 메서드와 매우 유사하다.
문자열을 순차적으로 탐색하며 자식 노드를 계속 탐색해나가는 형태이다. 자식이 만약 없거나 단어의 마지막임에도 endOfWord가 false 라면 false가 반환된다.
그럼 위 코드를 한 번 실행시켜보자
public class App { public static void main(String[] args) { Trie trie = new Trie(); trie.insert("car"); trie.insert("cb"); trie.insert("do"); trie.insert("dog"); System.out.println(trie.search("car")); System.out.println(trie.search("ca")); System.out.println(trie.search("cb")); System.out.println(trie.search("do")); System.out.println(trie.search("dog")); } }
true false true true true
ca라는 단어는 저장하지 않았으므로 자식 노드가 있어도 endOfWord가 false기 때문에 false가 출력된다.
시간 복잡도
문자열 최대 길이가 M이라고 하면, 문자열 검색 시 시간복잡도는 O(M log n)이다.
'Algorithm > Data Structure' 카테고리의 다른 글
[Algorithm] 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) (0) | 2023.04.07 |
---|---|
[Data Structure] 최소 신장 트리(MST, Minimum Spanning Tree) (0) | 2023.02.14 |
[Data Structure] 세그먼트 트리(Segment Tree) (0) | 2022.09.08 |
[Data Structure] 이진 탐색 트리(Binary Search Tree) (0) | 2022.08.17 |
[Data Structure] 우선순위 큐(Priority Queue) & 힙(Heap) (0) | 2022.08.17 |
댓글
이 글 공유하기
다른 글
-
[Algorithm] 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)
[Algorithm] 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)
2023.04.07 -
[Data Structure] 최소 신장 트리(MST, Minimum Spanning Tree)
[Data Structure] 최소 신장 트리(MST, Minimum Spanning Tree)
2023.02.14 -
[Data Structure] 세그먼트 트리(Segment Tree)
[Data Structure] 세그먼트 트리(Segment Tree)
2022.09.08 -
[Data Structure] 이진 탐색 트리(Binary Search Tree)
[Data Structure] 이진 탐색 트리(Binary Search Tree)
2022.08.17
댓글을 사용할 수 없습니다.