[java] 트라이(Trie) 자료구조
업데이트:
트라이 자료구조 개념 및 코드
개념
Trie is an efficient information reTrieval data structure.
트라이(Trie)는 Prefix Tree, digital search tree, retrieval tree라고도 부른다.
M : 문자열의 최대 길이
N : 트리 내에서 키의 갯수
균형을 맞춘 BST(Binary Search Tree)는 M * log N 의 시간이 필요로 한다.
Trie를 사용하는 경우 O(M)에 키를 찾을 수 있다
여러 가지(branch)를 구성하는 각각의 노드로 구성되어 있으며, <Key, Value> 맵을 가지고 있다.
- Key : 하나의 알파벳
- Value : Key에 해당하는 자식노드
(브랜치를 따라 geeks, geekt, geer, geez)
특징
1) Trie는 자식노드를 Map<Key, Value> 형태로 가지고 있다
2) 루트 노드를 제외한 노드의 자손들은 해당 노드와 공통 접두어를 가진다
3) 정렬된 트리구조이다 (데이터에 따라 이진트리일 때도 있다)
코드
기본 구조
node(TrieNode)
자식노드로 위의 설명에서 g, e, k 같이 각 글자를 의미하는 자식노드
private HashMap<Character, TrieNode> children;
private boolean endOfWord;
// 코드가 길어지므로 메소드 틀만 기입했음
public TrieNode();
public HashMap<Character,TrieNode> getChildren();
public void setChildren(HashMap<Character,TrieNode> children);
public boolean isEndOfWord(); // getter
public void setEndOfWord(boolean endOfWord);
- children : 글자와 자기자신을 key, value로 가지는 children을 가짐
- endOfWord : 현재 글자가 어떤 단어의 끝인지 아닌지 표현을 위함
이하 getter, setter 그리고 생성자
root(TrieTree)
기준이되는 루트 노드
private TrieNode root;
// 코드가 길어지므로 메소드 틀만 기입했음
public void insert(String word);
public boolean find(String word);
public void delete(String word);
private boolean delete(TrieNode current, String word, int idx);
// 트라이트리 출력용 메소드
public void printRoot();
private void print(TrieNode current, Stack<Character> stack);
- root : 기준이 되는 루트노드로서, 내부에 children을 이용해 이어가는 형식
insert
public void insert(String word) {
TrieNode current = root;
for (char l : word.toCharArray()) {
current = current.getChildren().computeIfAbsent(l, c -> new TrieNode());
}
current.setEndOfWord(true);
}
- 루트노드를 current에 담는다.
- 추가할 단어를 글자로 쪼개 1글자씩 반복
- current의 children(map구조)에서 반복중인 글자가 없는 경우, current의 children에 추가한다.
- 그리고 추가해서 만들어진 TrieNode를 current에 담는다
- 3부터 반복(글자 반복이 끝날때까지)
- 반복이 끝나면 current(마지막 글자가 추가된 trieNode객체)의 EndOfWord를 true로 할당한다.
- computeIfAbset(key, c -> new TrieNode());? ? ?
key가 map에 포함되어 있지 않은 경우, 새로운 객체를 생성하여 추가한다
예)map.computeIfAbsent(key, k -> new HashSet()).add(v);</code>
find
public boolean find(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.getChildren().get(ch);
if (node == null) {
return false;
}
current = node;
}
return current.isEndOfWord();
}
insert와 마찬가지로 current를 타고 들어가며 글자를 찾음
- 루트노드를 current에 담는다
- 단어를 1글자씩 돌면서 current의 children에 값이 있는지 확인한다
- 없는 경우, 저장되어있지 않으므로 false리턴
- 있는 경우, current를 해당 글자의 TrieNode를 담아 2부터 반복
- 찾으려는 단어의 모든 글자가 포함되어있다면 return하지 않았을 것이다
현재 current가 마지막글자인지(isEndOfWord) 확인 후 결과 리턴
만일 마지막 글자가 아니라면, (geeks가 저장되어있는데 find(geek)하는 경우)
geeks가 저징되어있는 것이고 ,geek은 저장되어있지않은 일부기때문에 isEndOfWord는 false
delete
public void delete(String word) {
delete(root, word, 0);
}
private boolean delete(TrieNode current, String word, int idx) {
if (idx == word.length()) {
if (!current.isEndOfWord()) {
return false;
}
current.setEndOfWord(false);
return current.getChildren().isEmpty();
}
char ch = word.charAt(idx);
TrieNode node = current.getChildren().get(ch);
if (node == null) {
return false;
}
boolean shouldDeleteCurrentNode = delete(node, word, idx + 1) && !node.isEndOfWord();
if (shouldDeleteCurrentNode) {
current.getChildren().remove(ch);
return current.getChildren().isEmpty();
}
return false;
}
find때와 비슷하게 찾아들어가며 삭제하는데, 이때는 재귀형태로 진행
(ㅠㅠ 재귀다보니 풀어쓰는게 너무 어렵다)
- 처음시작은 current에 루트노드를 넣어준다
- word의 idx번째 글자가 current에 있는지 확인한다. 없는경우 -> 존재하지않는 단어이므로 종료
- 다음 idx로 삭제 진행 && 현재 노드의 마지막 글자여부가 아닌지 체크한다
만일 idx진행이 삭제하려는 단어 길이와 같다면(모든 글자를 진행했다면)
마지막 글자인지 확인한다 . 마지막글자가 아니라면 지울수없음/ 마지막글자라면 다른 브랜치 여부 확인 - 3의 결과가 true라면 idx에 해당하는 글자를 current의 children에서 제거 & 다른 브랜치 여부 리턴
public void printRoot() {
System.out.println();
System.out.println("---------- tree");
Stack<Character> stack = new Stack<>();
print(root, stack);
System.out.println("---------------");
System.out.println();
}
private void print(TrieNode current, Stack<Character> stack) {
for (char ch : current.getChildren().keySet()) {
stack.add(ch);
if (current.getChildren().get(ch).isEndOfWord()) {
for (char c : stack) {
System.out.print(c);
}
System.out.println();
}
print(current.getChildren().get(ch), stack);
stack.pop();
}
}
printRoot와 print로 나눠서 진행했다.
printRoot에서는 스택생성하고 print를 호출, print는 재귀형태로 호출된다
children의 보유 글자를 반복하면서 마지막 글자라면 stack내부 출력하고,
다른 글자가 있다면 current를 변경하면서 반복함
전체 코드(github)
풀 수 있는 문제
관련해서 풀만한 문제 몇개 총총
프로그래머스 - 전화번호 목록
백준 - 휴대폰 자판
백준 - Boggle
참고
Trie | (Insert and Search)
[Java] 트라이(Trie) 자료구조 개념
트라이(Trie) 자료구조
Trie - wikipedia
The Trie Data Structure in Java
댓글남기기