• 트리의 특징

    • connected, undirected, acyclic graph (비방향, 비순환 그래프)
    • 탐색회수: 트리의 높이(깊이)

 

  • 트리에서 사용하는 용어

    • degree(차수): 자식 노드의 개수
    • level(레벨): 루트 노드로 부터의 거리

    • traversing(순회): 트리의 노드들을 순서적(체계적)으로 방문하는것

 

  • 트리의 분류
    • 구조상
      • binary tree: degree <= 2
      • multiway tree: degree >= 0
    • 기능상
      • digital tree
      • search tree


  • 이진트리(binary tree)의 특징

    • 배열,연결리스트에 비해 검색 속도가 빠르다.
    • 왼쪽 최하위 노드부터 순회하면 정렬된 순서로 데이타를 접근할 수 있다.

       

  • 탐색트리(search tree)의 특징

    • 전체적으로 트리의 균형이 잡혀있다. (balanced tree)

      • 트리의 높이가 작기때문에 탐색 속도가 빠르다.

 

  • 기억장치별 탐색트리

    • 주기억장치(메모리)용 : 이진트리

      • 트리의 깊이가 깊어도(탐색회수가
        많아도
        많아도) 큰 문제가 없으므로.
    • 보조기억장치(디스크)용 : B-트리

 

  • 검색용 트리의 분류

 

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

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