트라이 (Trie) 시각화
문자열 집합을 트리로 저장하여 빠른 검색과 자동완성을 지원하는 자료구조
문자열★★☆
속도
1 / 1노드 수: 0
연산
CARCARDCARECATDODOGDONE
현재 노드방문 완료단어 끝루트
각 단계를 클릭하면 해당 시점으로 이동합니다.
연산을 선택하고 실행 버튼을 누르세요.
트라이란?
트라이(Trie, prefix tree)는 문자열 집합을 문자 단위로 트리에 저장하는 자료구조입니다. 공통 접두사를 공유하므로 메모리를 절약하고, 삽입·탐색·자동완성 모두 O(m) (m=문자열 길이)에 수행됩니다. 단어 끝 노드는 이중 원으로 표시됩니다.
사용 방법
- 1초기 트라이에는 CAR, CARD, CARE, CAT, DO, DOG, DONE이 삽입되어 있습니다
- 2연산(삽입/탐색/자동완성)을 선택하고 단어를 입력합니다
- 3삽입: 새 노드가 생성되고 단어 끝이 표시됩니다
- 4탐색: 경로를 따라가며 존재 여부를 확인합니다
- 5자동완성: 접두사까지 이동 후 하위 모든 단어를 수집합니다
동작 원리
- 1삽입: 루트에서 시작하여 문자마다 자식 노드를 탐색/생성하고, 마지막 노드를 단어 끝으로 표시합니다
- 2탐색: 루트에서 문자를 하나씩 따라가며 자식이 없으면 '없음', 끝까지 도달하면 isEnd 확인
- 3자동완성: 접두사 끝 노드까지 이동 후 DFS로 하위 모든 단어를 수집합니다
- 4시간 복잡도: 모든 연산 O(m), m=문자열/접두사 길이. 자동완성은 O(m + 결과 수 * 평균 단어 길이)
실무 활용
- •검색 엔진 자동완성 (Google, Naver)
- •스마트폰 키보드 단어 예측
- •IP 라우팅 테이블 (최장 접두사 매칭)
- •사전/맞춤법 검사기
학습 팁
- •'CA'로 자동완성을 실행하면 CAR, CARD, CARE, CAT이 나옵니다 — 접두사 공유를 확인하세요
- •DARE를 삽입하면 DO 분기와 별도로 D-A-R-E 경로가 생깁니다
- •이중 원이 단어 끝 표시임을 기억하세요 — C-A-R 경로에서 R이 이중 원이면 'CAR'이 존재합니다
자주 묻는 질문
Q. 트라이 vs 해시테이블의 차이는?
A. 해시테이블은 정확한 키 조회에 O(1)이지만 접두사 검색/자동완성이 불가능합니다. 트라이는 접두사 기반 연산에 강하지만 메모리 사용이 큽니다. 자동완성이 필요하면 트라이, 정확한 조회만 필요하면 해시테이블을 선택합니다.
Q. 메모리를 줄이려면?
A. 압축 트라이(Patricia tree/radix tree)는 단일 자식 노드를 합쳐서 공간을 절약합니다. 또는 해시맵 대신 배열(26칸)로 자식을 저장하면 포인터 오버헤드를 줄일 수 있습니다.