문자열에서 검색을 빠르게 도와주는 자료구조
- K진 트리 구조
- 단어 사전을 트라이로 생성 후 찾을 단어를 트라이를 사용하여 검색
- 트라이의 루트 노드는 공백문자열
- 정수형에서 이진탐색트리 시간복잡도:
O(logN)
최대 길이가 M인 문자열에서 이진탐색트리 시간복잡도:O(M*logN)
트라이 시간복잡도:O(M)
트라이 구성
1. 트라이 노드 설계
2. 단어 사전의 입력할 단어를 트라이에 삽입
3. Root 노드부터 시작하여 단어의 첫 글자부터 트라이 탐색
4. 만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식 존재
=>현재 노드를 해당하는 자식 노드로 이동
만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식 존재 X
=>새로운 자식 추가
5. 단어 삽입 후 탐색된 마지막 노드에 현재 입력된 단어의 정보 추가트라이를 이용한 검색
1. Root 노드부터 시작하여 검색할 단어의 첫 글자부터 트라이 탐색
2. 만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식 존재
=>현재 노드를 해당하는 자식 노드로 이동
만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식 존재 X
=>검색할 단어는 단어사전에 존재하지 않음
3. 검색이 완료되엇다면, 탐색된 마지막 노드의 정보 이용
