[박혜웅] 트리 (tree)

• 트리의 특징

  • 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-트리

 

• 검색용 트리의 분류