본문 바로가기

자료구조 & 알고리즘/트리(Tree)

[박혜웅] digital tree

  • digital tree의 특징

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

 

  • 디지털탐색트리의 특징

    • 각 노드가 하나의 원소만을 갖는 이진 트리
    • 접두사 탐색에 효율적이다.

    • 이동할 서브트리가 탐색 키의 비트에 의해서 결정됨
    • 각각의 연산은 O(h) 시간 내에 수행됨

      • h : 디지털 탐색 트리의 높이
      • 각 키가 keySize 비트 가지면, 트리 높이 최대 keySize + 1
    • 키가 아주 긴 경우에 비효율적인 탐색 구조

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

 

 

 
  • digital tree의 구조 및 원소삽입

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

       

'자료구조 & 알고리즘 > 트리(Tree)' 카테고리의 다른 글

[강한구] Binary Heap  (0) 2010.03.31
[박혜웅] 트리 (tree)  (0) 2010.03.28
[박혜웅] B Tree (balanced tree)  (0) 2010.03.27
[강한구] 이진트리  (0) 2009.07.13
[강한구] 트리 기초개념  (0) 2009.04.01