[알고리즘] 트라이 개념 및 구현하기
트라이(Trie)란?
문자열을 저장하고 탐색하기 위한 트리모양 자료구조
특징
- 자동완성, 사전찾기에 응용됩니다
문자열
탐색에 최적화된 자료구조 입니다
- 문자마다 노드를 만들어야하기 때문에 저장공간이 많이 필요합니다
- 탐색 시간복잡도는 문자열의 길이 L에 대해
O(L)
만큼만 걸립니다
규칙
문자열을 저장하고 탐색하기 위한 트리모양 자료구조
문자열
탐색에 최적화된 자료구조 입니다O(L)
만큼만 걸립니다트라이를 구현할 때 몇가지 규칙이 있습니다.
root
노드는 항상 비어있습니다- 간선은 추가될 문자입니다
- 각 노드는 이전 정점의 값 + 간선에 추가될 문자를 값으로 가집니다
- 해시테이블을 사용해 구현할 수 있습니다
구현
자바스크립트로 다음과 같이 구현할 수 있습니다. 먼저 각 문자를 표현할 Node 클래스가 필요합니다.
class TrieNode {
constructor(str = "") {
this.word = false; // 입력한 단어 그 자체인지
this.str = str;
this.children = {};
}
}
- 단어인지 구분하는
word
가 있습니다.
Tree라는 단어를 넣으면, 마지막 노드에만 word=True
가 됩니다
children
으로 트라이 자식노드들을 관리합니다
다음은 자바스크립트로 구현한 트라이 자료구조입니다
class Trie {
constructor() {
this.root = new TrieNode(); // 루트는 항상 비어있습니다
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!(char in node.children)) {
node.children[char] = new TrieNode(node.str + char);
}
node = node.children[char];
}
node.word = true;
}
find(word) {
let node = this.root;
for (const char of word) {
if (char in node.children) {
node = node.children[char];
} else {
return false;
}
}
return node.word;
}
}
다음은 파이썬으로 구현한 트라이 입니다
class TrieNode:
def __init__(self,str=""):
self.word = False
self.str = str
self.children = {}
class Trie:
def __init__(self) -> None:
self.root = TrieNode()
def insert(self,word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode(node.str+char)
node = node.children[char]
node.word = True
def find(self,word):
node=self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
return False
return node.word
-
insert 메서드는 해당 단어의 글자를 하나하나씩 node를 만들어 집어넣는 메서드입니다.
-
find
메서드는 해당 단어가 트라이에 존재하는지 확인하는 메서드입니다. -
만약 찾고자 하는 단어 중에 하나의 글자라도
node.children
에 존재 하지 않는다면false
를 반환합니다 -
node.children
에 존재해서 끝까지 탐색하였더라도 해당 노드가word=false
라면 존재하지 않는 단어입니다. 다음 예시를 들 수 있습니다
const trie = new Trie();
trie.insert("가");
trie.insert("나");
trie.insert("다");
trie.insert("가나다");
trie.find("가나") // false
가나
단어는 모두 트라이에 존재하는 단어이지만, 해당가나
노드가 입력된 단어가 아니기 때문에word=false
입니다
정리
-
트라이는 문자열을 저장, 탐색하는데 안성맞춤인 알고리즘입니다. 특히 탐색 시간복잡도는 문자열의 길이 O(L)
만큼만 듭니다.
-
insert() find()메서드는 단어의 문자를 하나씩 확인하면서 해당 node의 childrend 유무를 따져 구현합니다
Author And Source
이 문제에 관하여([알고리즘] 트라이 개념 및 구현하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@sa02045/알고리즘-트라이-개념-및-구현하기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
트라이는 문자열을 저장, 탐색하는데 안성맞춤인 알고리즘입니다. 특히 탐색 시간복잡도는 문자열의 길이 O(L)
만큼만 듭니다.
insert() find()메서드는 단어의 문자를 하나씩 확인하면서 해당 node의 childrend 유무를 따져 구현합니다
Author And Source
이 문제에 관하여([알고리즘] 트라이 개념 및 구현하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sa02045/알고리즘-트라이-개념-및-구현하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)