Tree.md

Tree

트리

• 비선형 구조
• 1:n 관계를 가지는 자료구조
• 계충 관계를 가지는 계층형 자료구조

정의

• 노드(node) : 트리의 원소
• 한 개 의상의 노드로 이루어진 유한 집합
  • 최상위 노드를 루트 노드라 한다.
    • 상위 노드가 없는 노드
  • 나머지 노드들은 n개의 분리집합으로 분리될 수 있다
    • 이들은 각각 하나의 트리가 되며 루트의 subTree가 된다.

용어 정리

• 단말노드
  • 자식 노드가 없는 마지막 노드
• 간선
  • 노드와 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결
• 형제 노드
  • 같은 부모 노드의 자식 노드들
• 조상 노드
  • 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 차수(degree)
  • 노드의 차수
    • 노드에 연결된 자식 노드의 수, 즉 간선의 수
  • 트리의 차수
    • 트리에 있는 노드의 차수 중에서 가장 큰 값
  • 단말 노드는 차수가 0
• 높이
  • 노드의 높이
    • 루트에서 노드에 이르는 간선의 수, 노드의 레벨
  • 트리의 높이
    • 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨

이진 트리

• 차수가 2인 트리
• 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리
  • 왼쪽 자식 노드
  • 오른쪽 자식 노드
• 모든 노드들이 최대 2개의 서브트리를 갖는 특별한 형태의 트리

특성

• 높이 i에서 노드의 최대 개수는 2개
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1) -1)개

종류

• 포화 이진 트리(Perfect Binary Tree)
  • 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
  • 높이가 h일 때, 최대의 노드 개수를 가진 이진 트리
  • 루트를 1번으로 하여 2^(h+1) - 1 까지 정해진 위치에 대한 노드 번호를 가짐
• 완전 이진 트리(Complete Binary Tree)
  • 마지막 레벨을 제외한 위 레벨의 모든 노드가 채워진 이진 트리
  • 모든 포화 이진트리는 완전 이진 트리이다
• 편향 이진 트리
  • 한쪽 방향의 자식 노드 만을 가지는 이진 트리

표현

• 배열을 이요한 이진 트리의 표현
  • 노드 번호의 성질
    • 노드 번호가 i 인 노드의 부모 노드 번호 i/2
    • 노드 번호가 i 인 왼쪽 자식 노드 번호 2 * i
    • 노드 번호가 i 인 오른쪽 자식 노드 번호 2*i+1
    • 레벨 n의 노드 시작 번호 2^n
  • 노드 번호를 배열의 인덱스로 사용
  • 높이가 h인 이진 트리를 위한 배열의 크기
    • 2^(h+1), 0인덱스는 사용 x
    • 루트 노드의 인덱스 1
    • 편향 이진 트리의 경우에는 비효율적인 메모리 소모
      • 이런 경우에는 연결리스트가 효율적임

이진트리 순회

• 순회 : 트리의 노드를 체계적으로 방문하는 것

순회 방법

• 전위 순회(preorder traversal) : VLR
  • 부모노드 방문 후, 자식노드를 좌, 우 순서로 방문
• 중위 순회(inorder traversal) : LVR
  • 왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문
• 후위 순회(postorder traversal) : LRV
  • 자식 노드를 좌우 순서로 방문한 후, 부모노드 방문

구현 방법

1. preorder

preorder_traverse(T)
  if (T is not null){
    visit(T);
    preorder_traverse(T.left)
    preorder_traverse(T.right)
  }
End preorder_traverse

2. inorder

inorder_traverse(T)
  if (T is not null){
    inorder_traverse(T.left)
    visit(T)
    inorder_traverse(T.right)
  }
End inorder_traverse

3. postorder

postorder_traverse(T)
  if (T is not null){
    postorder_traverse(T.left)
    postorder_traverse(T.right)
    visit(T)
  }
End postorder_traverse