• 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조

핵심 이론

• 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행
• 특징
  • N진 트리: 문자 종류의 개수에 따라 N이 결정. 예를 들어 알파벳은 26개의 문자로 이뤄져 있어 26진트리로 구성
  • 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지

• 노드는 기본적으로 N개의 공백 노드를 자식으로 가짐
• 다음 단어를 삽입할 때는 루트 노드에서부터 검색
• 검색 노드가 공백 상태일 경우 신규 노드를 생성하고, 공백 상태가 아니면 이동
• 문자열의 마지막에 도달하면 리프 노드라고 표현

[069] 문자열 찾기

• https://www.acmicpc.net/problem/14425

(root)
├─ b
│  └─ a
│     └─ e
│        └─ k
│           └─ j
│              └─ o
│                 └─ o
│                    └─ n
│                       └─ o
│                          └─ n
│                             └─ l
│                                └─ i
│                                   └─ n
│                                      └─ e
│                                         └─ j
│                                            └─ u
│                                               └─ d
│                                                  └─ g
│                                                     └─ e (●)
├─ c
│  └─ o
│     └─ d
│        ├─ e
│        │  └─ p
│        │     └─ l
│        │        └─ u
│        │           └─ s (●)
│        └─ i
│           └─ n
│              └─ g
│                 └─ s
│                    └─ h (●)
└─ s
   ├─ t
   │  └─ a
   │     └─ r
   │        └─ t
   │           └─ l
   │              └─ i
   │                 └─ n
   │                    └─ k (●)
   └─ u
      └─ n
         └─ d
            └─ a
               └─ y
                  └─ c
                     └─ o
                        └─ d
                           └─ i
                              └─ n
                                 └─ g (●)