자료구조 & 알고리즘 (트라이)
2023. 7. 19. 14:28ㆍ자바스크립트 정리
728x90
트라이
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
트라이의 특징
▶ 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
▶ 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
▶ L이 문자열의 길이일 때 탐색, 삽입은 0(L)만큼 걸린다
▶ 대신 각 정점이 지식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.
Trie 생성하기
트라이 구조
▶ 루트는 비어있다.
▶ 각 간선(링크)은 추가될 문자를 키로 가진다.
▶ 각정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
▶ 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.
JavaScript에서 사용법
트라이 구성
'자바스크립트 정리' 카테고리의 다른 글
| 자료구조 & 알고리즘 (이진 탐색) (0) | 2023.07.19 |
|---|---|
| 자료구조 & 알고리즘 (정렬) (0) | 2023.07.19 |
| 자료구조 & 알고리즘 (힙 - Heap) (0) | 2023.07.19 |
| 자료구조 & 알고리즘 (트리) (0) | 2023.07.19 |
| 자료구조 & 알고리즘 (그래프) (0) | 2023.07.19 |