728x90
반응형
자료구조
-
[JS] 트라이자료구조와 알고리즘 2022. 8. 31. 11:16
검색의 자동완성 기능을 구현할 때 적합한 자료구조 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 특징 - 찾는 문자열의 길이만큼만 시간 복잡도가 걸린다. - 저장공간을 좀 더 많이 사용한다. 구조 루트는 비어있다. 각 간선은 추가될 문자를 키로 가진다. 각 정점은 이전 간선의 키를 값으로 가진다. 해시 테이블과 연결 리스트를 사용한다. 트리 생성하기 function makeTrie(words) { const root = {}; // 먼저 루트 노드를 설정할 변수를 만든다. for (const word of words) { // Trie를 구성하기 위한 루프를 돌린다. let current = root; // 루프부터 시작 for (const letter of word) { // 단어의 ..