이 영역을 누르면 첫 페이지로 이동
Arc 블로그의 첫 페이지로 이동

Arc

페이지 맨 위로 올라가기

[Data Structure] 트라이 트리(Trie Tree)

Arc

[Data Structure] 트라이 트리(Trie Tree)

  • 2023.03.19 13:14
  • Algorithm/Data Structure
글 작성자: SeoArc

트라이 트리(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)이다.

이 글은 본 저작자 표시 규칙 하에 배포할 수 있습니다. 자세한 내용은 Creative Commons 라이선스를 확인하세요.
Creative Commons
본 저작자 표시

'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

댓글

댓글을 사용할 수 없습니다.

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [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
다른 글 더 둘러보기

정보

Arc 블로그의 첫 페이지로 이동

Arc

  • Arc의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 방명록

카테고리

  • 분류 전체보기 (106)
    • Language (28)
      • C++ (0)
      • C# (0)
      • Java (28)
    • Algorithm (47)
      • Algorithm (15)
      • Data Structure (6)
      • PS (26)
    • Computer Science (22)
      • Design Pattern (1)
      • Network (14)
      • OS (7)
    • Game (0)
      • Unity (0)
    • Backend (3)
      • Spring (1)
      • JPA (2)
    • DB (0)
      • SQL (0)
    • DevOps (2)
      • AWS (0)
      • Docker (2)
      • Jenkins (0)
      • Nginx (0)
    • Software Engineering (4)
      • OOP (4)
    • AI (0)
      • Machine Learning (0)
    • Others (0)

인기 글

공지사항

태그

  • 그래프
  • java
  • 알고리즘
  • algorithm
  • graph
  • 네트워크
  • network
  • 자바

정보

SeoArc의 Arc

Arc

SeoArc

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. © SeoArc. Designed by Fraccino.

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.