자료구조&알고리즘_트라이

트라이 (Trie)

• 트리를 이용한 자료구조
• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
  ex) 검색에서 사용하는 자동완성 기능을 만들 때 사용하는 알고리즘

트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 사용한다.
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
• 각 정점이 자식에 대한 링크를 전부 갖고 있기 때문에 저장 공간을 더 많이 사용한다.

트라이 구조

• 루트는 비어있다.
• 각 간선(링크)는 추가될 문자를 키로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

class Node {
	constructor(value = "") {
		this.value = value;
		this.children = new Map();
	}
}

class Trie {
	constructor() {
		this.root = new Node();
	}

	insert(string) {
		let currentNode = this.root;

		for (const char of string) {
			if (!currentNode.children.has(char)) {
				currentNode.children.set(char, new Node(currentNode.value + char));
			}
			currentNode = currentNode.children.get(char);
		}
	}

	has(string) {
		let currentNode = this.root;

		for (const char of string) {
			if (!currentNode.children.has(char)) {
				return false;
			}
			currentNode = currentNode.children.get(char);
		}

		return true;
	}
}

const trie = new Trie();
trie.insert("cat");
trie.insert("can");
console.log(trie.has("cat")); // true
console.log(trie.has("caq")); // false
console.log(trie.has("can")); // true
console.log(trie.has("cab")); // false

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스