[자료구조 공부] 자바스크립트 트라이(Trie) #10💜 코딩테스트/자료구조 & 알고리즘2023. 11. 3. 15:58
Table of Contents
☘️ 트라이(Trie)
트라이 정의
트라이는 트리 형태로 되어 있는 자료구조이다.
트라이
문자열 저장
문자열을 효율적으로 탐색하기 위한 자료구조
이전 정점으로부터 더해진 문자열 정보 가짐
트라이 특징
검색어 자동완성, 사전 찾기
트라이는 검색어 자동완성, 사전 찾기 등에서 활용된다.
효율적인 문자열 탐색
단순하게 문자열을 비교하여 탐색하는 것보다 효율적이게 찾을 수 있다.
탐색 시간
문자열을 탐색, 삽입하는 시간 복잡도는 문자열의 길이만큼 소요된다.
- 문자열 길이: L
- 시간 복잡도: O(L)
저장공간
각 정점이 자식에 대한 링크를 전부 가지고 있어 저장공간이 많이 차지한다는 단점이 있다.
트라이 구조 특징
빈 루트
트라이의 Root는 문자열이 없는 비어있는 상태이다.
간선(링크) 키 값
각 간선(링크)는 키 값으로 다음에 추가될 문자를 가진다.
정점 키 값
각 정점의 값은 이전 정점 값 + 간선의 키 값 이다.
☘️ 트라이(Trie) 구현
자바스크립트에서 트라이를 구현하는 방법은 아래 코드와 같다.
해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)
코딩테스트 광탈 방지 A to Z : JavaScript
코딩테스트 광탈 방지 A to Z : JavaScript 자료구조와 알고리즘 기본기를 다지고 문제 풀이 꿀팁까지 한 번에 가져가요! 자료구조와 알고리즘 기초부터 코딩 테스트 대표 유형 문제 풀이까지 “A to Z
'💜 코딩테스트 > 자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘 공부] 자바스크립트 정렬(sort) #2 (1) | 2023.12.07 |
|---|---|
| [알고리즘 공부] 자바스크립트 이진 탐색(binary search) #1 (0) | 2023.12.05 |
| [자료구조 공부] 자바스크립트 힙(heap) #9 (0) | 2023.11.03 |
| [자료구조 공부] 자바스크립트 그래프 #7 (0) | 2023.11.02 |
| [자료구조 공부] 자바스크립트 해시 테이블 #6 (0) | 2023.11.02 |
@짱잼 :: 짱잼이의 FE 개발 공부 저장소
FE 개발자가 되고 싶은 짱잼이
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!
