-
compressed trie
-
-
compact trie 에서 내부노드중 단일자식노드를 1개의 노드로 압축
- 단일자식노드: 자식노드가 1개 분인 노드
- trie, compact trie 보다 저장공간, 탐색시간 절약
-
압축으로 인해 삭제되는 간선(edge)의 정보를 보존해야 함
- B,I를 나타내는 간선이 압축될 경우, 압축된 간선은 BI 의 정보를 가지고 있어야 함.
-
탐색후, 질의어와 일치하는지 확인하는 과정 필요
-
-
compact trie를 compressed trie로 압축하는 과정
-
compact trie
-
내부노드중 단일자식노드를 1개의 노드로 압축
-
compressed trie
-
-
'자료구조 & 알고리즘 > 트라이(Trie)' 카테고리의 다른 글
| [박혜웅] 패트리샤 트리 (patricia tree) (0) | 2010.03.29 |
|---|---|
| [박혜웅] PAT tree (0) | 2010.03.29 |
| [박혜웅] compact trie (0) | 2010.03.29 |
| [박혜웅] 이진 트라이 (binary trie) (0) | 2010.03.29 |
| [박혜웅] 트라이 (trie) (0) | 2010.03.29 |
