본문 바로가기

자료구조 & 알고리즘/트라이(Trie)

[박혜웅] compact trie

  • compact trie 의 특징

    • 잎 노드위의 단일자식노드를 제거한 trie

      • 단일자식노드: 자식노드가 1개 분인 노드
    • trie보다 저장공간, 탐색시간 절약
    • 탐색후, 질의어와 일치하는지 확인하는 과정 필요

      • 예: 질의어 black 일 경우 아래 그림에서 탐색은 성공하지만, 실제 색인어는 bluebird 이므로 결과에 표시하면 안됨

 

  • compact trie 의 구조

    • 데이타: bluebird, bunting, cardinal, chicadee, godwit, goshawk, thrasher, thrush, wren

 

  • trie를 compact trie로 변환

    • trie

      •  


    • 잎 노드위의 단일자식노드를 제거

      •  
    • compact trie

      •