자료구조 09 트라이 | JS
트라이 | Trie
- 문자열에서 검색을 빠르게 도와주는 자료구조
- 정수형에서 이진탐색트리를 이용하면 시간복잡도 O(logN)
하지만 문자열에서 적용했을 때, 문자열 최대 길이가 M이면 O(M*logN)이 된다.
트라이를 활용하면? → O(M)으로 문자열 검색이 가능함!
트라이 노드 구현
import HashTable from '../hash-table/HashTable';
export default class TrieNode {
constructor(character, isCompleteWord = false) {
this.character = character;
this.isCompleteWord = isCompleteWord;
this.children = new HashTable();
}
getChild(character) {
return this.children.get(character);
}
addChild(character, isCompleteWord = false) {
if (!this.children.has(character)) {
this.children.set(character, new TrieNode(character, isCompleteWord));
}
const childNode = this.children.get(character);
// ex) "carpet" 뒤에 "car"를 추가하는 경우 "r" 문자를 완성으로 표시해야 함
childNode.isCompleteWord = childNode.isCompleteWord || isCompleteWord;
return childNode;
}
removeChild(character) {
const childNode = this.getChild(character);
// childNode에 children이 없고
// && childNode가 CompleteWord가 아닐 경우에만 삭제
if (
childNode
&& !childNode.isCompleteWord
&& !childNode.hasChildren()
) {
this.children.delete(character);
}
return this;
}
hasChild(character) {
return this.children.has(character);
}
hasChildren() {
return this.children.getKeys().length !== 0;
}
suggestChildren() {
return [...this.children.getKeys()];
}
toString() {
let childrenAsString = this.suggestChildren().toString();
childrenAsString = childrenAsString ? `:${childrenAsString}` : '';
const isCompleteString = this.isCompleteWord ? '*' : '';
return `${this.character}${isCompleteString}${childrenAsString}`;
}
}
트라이 로직 구현
import TrieNode from './TrieNode';
// 트라이 트리의 루트에 사용할 문자
const HEAD_CHARACTER = '*';
export default class Trie {
constructor() {
this.head = new TrieNode(HEAD_CHARACTER);
}
addWord(word) {
const characters = Array.from(word);
let currentNode = this.head;
for (let charIndex = 0; charIndex < characters.length; charIndex += 1) {
const isComplete = charIndex === characters.length - 1;
currentNode = currentNode.addChild(characters[charIndex], isComplete);
}
return this;
}
deleteWord(word) {
const depthFirstDelete = (currentNode, charIndex = 0) => {
if (charIndex >= word.length) {
return; // 단어의 범위를 벗어난 문자를 삭제하려는 경우 반환
}
const character = word[charIndex];
const nextNode = currentNode.getChild(character);
if (nextNode == null) {
return; // 트리에 추가되지 않은 단어를 삭제하려는 경우 반환
}
// Go deeper.
depthFirstDelete(nextNode, charIndex + 1);
// 마지막 character의 isCompleteWord flag는 false로 설정
if (charIndex === (word.length - 1)) {
nextNode.isCompleteWord = false;
}
// childNode에 children이 없고
// && childNode가 CompleteWord가 아닐 경우에만 삭제
currentNode.removeChild(character);
};
// Start depth-first deletion from the head node.
depthFirstDelete(this.head);
return this;
}
suggestNextCharacters(word) {
const lastCharacter = this.getLastCharacterNode(word);
if (!lastCharacter) {
return null;
}
return lastCharacter.suggestChildren();
}
// Check if complete word exists in Trie.
doesWordExist(word) {
const lastCharacter = this.getLastCharacterNode(word);
return !!lastCharacter && lastCharacter.isCompleteWord;
}
getLastCharacterNode(word) {
const characters = Array.from(word);
let currentNode = this.head;
for (let charIndex = 0; charIndex < characters.length; charIndex += 1) {
if (!currentNode.hasChild(characters[charIndex])) {
return null;
}
currentNode = currentNode.getChild(characters[charIndex]);
}
return currentNode;
}
}
📚 참고
Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
Photo by Alain Pham on Unsplash
Author And Source
이 문제에 관하여(자료구조 09 트라이 | JS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@protect-me/자료구조-07-트라이-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)