-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrie.java
More file actions
145 lines (116 loc) · 3.64 KB
/
Trie.java
File metadata and controls
145 lines (116 loc) · 3.64 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
package org.study;
import java.util.*;
public class Trie {
private TrieNode root;
// -- 생성자 , 루트노드 생성
public Trie() {
root = new TrieNode(' ');
}
// -- 삽입
public void insert(String word) {
// 삽입하려는 문자가 모두 존재할때
if(search(word) == true) return;
TrieNode current = root;
for (char ch : word.toCharArray()) {
TrieNode child = current.subNode(ch);
if(child != null) {
current = child;
}
else {
// ch 문자가 있으면 그 노드 리턴
current.childList.add(new TrieNode(ch));
current = current.subNode(ch);
}
current.count++;
}
current.terminal = true;
}
// -- 검색
public boolean search(String word) {
TrieNode current = root;
// 문자열을 문자배열로 쪼개서 비교
for(char ch : word.toCharArray()) {
// 해당 문자의 노드가 없으면 false
if(current.subNode(ch) == null)
return false;
// 해당 문자가 존재하면, 현재 노드에 서브 노드 저장해서 단계별로 내려감
else
current = current.subNode(ch);
}
// a,p,p,l,e 가 있을때,
// word = apple 이면 true / word = appleb 이면 false
if(current.terminal == true) return true;
return false;
}
// -- Trie에 저장된 단어 목록 Iterator타입으로 반환
public Iterator<String> iterator(){
Set<String> elementsInTrie = new TreeSet<>();
// 저장됨 데이터를 elementsIntrie에 저장
recursiveCallPrint(root, "", elementsInTrie);
Iterator<String> elementsInTrieSet = elementsInTrie.iterator();
return elementsInTrieSet;
}
private void recursiveCallPrint(TrieNode currNode,
String key, Set<String> elementsInTrie) {
if(currNode.terminal) {
elementsInTrie.add(key);
}
LinkedList<TrieNode> children = currNode.childList;
Iterator<TrieNode> childIter = children.iterator();
String sKey = key;
while (childIter.hasNext()) {
TrieNode nextNode = childIter.next();
// 문자열 합치기 (키+문자)
String s = sKey + nextNode.nodeChar;
// 재귀 호출 (다음 노드, 키값, 저장셋)
recursiveCallPrint(nextNode, s, elementsInTrie);
}
}
public void printWord() {
System.out.println("▶Elements in the TRIE are :");
Iterator<String> itr = iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
System.out.println("===================");
}
}
/*
* 트라이 노드 정의
* */
class TrieNode implements Comparable<TrieNode>{
char nodeChar; // 문자저장
boolean terminal; // 리프 노드 여부
int count; // 해당 노드 사용수, 내 노드에 몇개의 가지가 있는지
LinkedList<TrieNode> childList; // 자식 노드 리스트
// constructor
public TrieNode(char c) {
childList = new LinkedList<>();
terminal = false;
nodeChar = c;
count = 0;
}
boolean getTerminal() {
return terminal;
}
// 해당 노드가 가지고 있는 자식 노드들중에서 입력받은 문자가 있으면 그 노드 리턴
public TrieNode subNode(char nextChar) {
// 자식 노드들이 있다면
if(childList != null) {
for(TrieNode eachChild:childList) {
if(eachChild.nodeChar == nextChar) {
return eachChild;
}
}
}
return null;
}
@Override
public int compareTo(TrieNode other) {
return Character.compare(this.nodeChar, other.nodeChar);
}
@Override
public String toString() {
return this.nodeChar+"("+this.terminal+") ";
}
}