[알고리즘] 트라이 - JavaScript

2022. 8. 15. 15:18·알고리즘/풀이 힌트
반응형

트라이? 

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

트라이의 특징

  • 검색어 자동완성, 사전 찾기 등에 사용할 수 있다. 
  • 문자열을 탐색할 때 단순 비교보다 효율적으로 찾을 수 있다. 
  • L이 문자열의 길이일 때 탐색, 삽입은 O(L) 만큼의 시간 복잡도를 가진다. 
  • 자식에 대한 링크를 전부 가져야 하기 때문에 저장 공간을 많이 차지한다. 

JavaScript에서 사용하기

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
    }
}

 

 

 

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 풀이 힌트' 카테고리의 다른 글

[알고리즘] 소수 구하기 - JavaScript  (0) 2022.08.23
[알고리즘] 이진 탐색 - JavaScript  (0) 2022.08.17
[알고리즘] 힙 - JavaScript  (1) 2022.08.13
[알고리즘] 그래프 - JavaScript  (0) 2022.08.12
[알고리즘] 해시 테이블 - JavaScript  (1) 2022.08.09
'알고리즘/풀이 힌트' 카테고리의 다른 글
  • [알고리즘] 소수 구하기 - JavaScript
  • [알고리즘] 이진 탐색 - JavaScript
  • [알고리즘] 힙 - JavaScript
  • [알고리즘] 그래프 - JavaScript
잉여개발자
잉여개발자
풀스택 개발자를 목표로 잉여롭게 개발 공부도 하면서 다양한 취미 생활도 즐기고 있는 잉여 개발자입니다.
  • 잉여개발자
    잉여로운 개발일지
    잉여개발자
    • 분류 전체보기 (789)
      • 개발정보 (36)
      • 개발환경 (7)
      • 개발생활 (19)
      • React (141)
        • 이론 (23)
        • 기능 (12)
        • 실험실 (88)
        • 버그 (6)
        • 패스트캠퍼스 (9)
        • Npm (3)
      • React Native (28)
        • 공통 (6)
        • TypeScript (3)
        • JavaScript (18)
        • 버그 (1)
      • Next.js (30)
        • 이론 (13)
        • 실험실 (13)
        • 버그 (3)
      • Web (35)
      • 알고리즘 (202)
        • 풀이 힌트 (39)
      • JavaScript (47)
      • TypeScript (29)
        • 기초 (27)
        • 실험실 (2)
      • Node.js (13)
        • 이론 (0)
        • 기능 (3)
        • 실험실 (9)
        • 버그 (1)
      • 도커 (4)
      • CCNA (22)
        • 이론 (4)
        • 문제 (18)
      • 취미생활 (167)
        • 잉여로운 칵테일 (2)
        • 잉여의 식물키우기 (130)
        • 잉여로운 여행기 (11)
        • 잉여의 제2외국어 (21)
        • 잉여로운 책장 (2)
      • Java (1)
        • Java의 정석 (1)
      • 꿀팁 공유 (3)
  • 태그

    타일러영어
    Docker
    바질
    바질 키우기
    typescript
    네트워크
    webpack
    redux
    식물
    Node.js
    프로그래머스
    react
    리얼학습일기
    CSS
    javascript
    ReactNative
    알고리즘
    리액트
    자바스크립트
    리얼클래스
    ChatGPT
    CCNA
    Babel
    영어회화
    다이소
    타입스크립트
    네이버 부스트캠프
    next.js
    영어독학
    덤프
  • hELLO· Designed By정상우.v4.10.1
잉여개발자
[알고리즘] 트라이 - JavaScript
상단으로

티스토리툴바