[박혜웅] digital tree

• digital tree의 특징

  • 문자열을 처리하기 위한 트리
  • 노드안에는 원소가 한개만 들어간다.

 

• 디지털탐색트리의 특징

  • 각 노드가 하나의 원소만을 갖는 이진 트리

  • 접두사 탐색에 효율적이다.

  • 이동할 서브트리가 탐색 키의 비트에 의해서 결정됨

  • 각각의 연산은 O(h) 시간 내에 수행됨

    • h : 디지털 탐색 트리의 높이
    • 각 키가 keySize 비트 가지면, 트리 높이 최대 keySize + 1

  • 키가 아주 긴 경우에 비효율적인 탐색 구조

    • 키의 비교에 많은 비용이 필요

 

 

 

• digital tree의 구조 및 원소삽입

  • a, b, c, d, e, f  순으로 삽입했을 경우