[자료구조] Tree란?

트리(Tree)의 개념

트리는 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성
트리는 하나의 루트 노드를 갖고, 루트노드는 0개 이상의 자식 노드를 갖고 있다.
트리에는 사이클(cycle)이 존재할 수 없는 단방향이다.
노드들은 특정 순서로 나열될 수 있다.

 

 

트리 관련 용어

 

루트 노드(root node): 부모가 없는 최상단 노드.

내부(internal) 노드: 부모, 자식이 있는 노드.
단말 노드(leaf node): 자식이 없는 노드.

형제노드(sibling): 같은 부모를 가지는 노드.
간선(edge): 노드를 연결하는 선 (branch 라고도 부름).
노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(level): 트리의 같은 깊이를 가지는 노드의 집합.
노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(degree of tree): 트리의 최대 차수
트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

트리(Tree)의 특징

트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
loop나 circuit이 없고, self-loop도 없다.
노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
루트에서 어떤 노드로 가는 경로는 유일하다.
임의의 두 노드 간의 경로도 유일하다. 즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

 

 

이진트리

이진트리는 효율적인 검색,정렬을 위하여 이진 탐색 트리, AVL 트리, red-black 트리, 이진 힙등에서 사용된다.

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다

 

이진트리의 순회

1. 중위 순회(in-order traversal): 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지

void inOrderTraversal(TreeNode node) {
  if(node != null) {
   inOrderTraversal(node.left);
   visit(node);
   inOrderTraversal(node.right);
  }
}

2. 전위 순회(pre-order traversal): 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지

void preOrderTraversal(TreeNode node) {
  if(node != null) {
   visit(node);
   preOrderTraversal(node.left);
   preOrderTraversal(node.right);
  }
}

 

3. 후위 순회(post-order traversal): 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드

void postOrderTraversal(TreeNode node) {
  if(node != null) {
   postOrderTraversal(node.left);
   postOrderTraversal(node.right);
   visit(node);
  }
}

 

Full Binary Tree

Full Binary Tree

• 모든 노드가 0개 혹은 2개의 children 을 가지고 있을 때 “Binary Tree 는 full” 이라고 한다.
• 같은 의미 다른 말로, “Full Binary Tree 는 leaf 노드들을 제외한 모든 노드들이 2개의 children 을 가지는 Binary Tree” 라고도 할 수 있다.

 

Perfect Binary Tree

Perfect Binary Tree

• 모든 internal node 가 두개의 children 을 가지고 있고, 모든 leaf 노드가 같은 level 에 있으면 Perfect Binary Tree 라고 한다.
• Height 가 h 인 Perfect Binary Tree 는 2h - 1 개의 노드를 가진다.
• 위 그림의 경우 height 는 4 이고, 노드의 개수는 24 - 1 = 15 개의 노드를 가지고 있다.

 

Complete Binary Tree

Complete Binary Tree

• 마지막 level 을 제외한 나머지 level 에 node 들이 가득 차있고, 마지막 level 에서 node 는 가장 왼쪽 부터 채워지는 형태가 Complete Binary Tree 이다.
• Complete Binary Tree 구조를 그대로 사용하여 Binary Heap 이라는 데이터 구조를 만들 수 있는데, 이놈이 Heap 이다.
• Complete Binary Tree (15개의 데이터가 저장된다면 index 0 ~ index 14 까지 채워진다) 구현에는 Array 를 사용하는 것이 일반적이다.

 

이진 힙

최소힙(Min Heap)
트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 완전 이진 트리이며, 각 노드의 원소가 자식들의 원소보다 작다.
즉, key(부모 노드) >= key(자식 노드)인 완전 이진 트리
가장 큰 값은 루트 노드이다.
N개가 힙에 들어가 있으면 높이는 log(N)이다.

최대힙(Max Heap)
원소가 내림차순으로 정렬되어 있다는 점에서만 최소힙과 다르다.
각 노드의 원소가 자식들의 원소보다 크다.

힙은 일차원 배열로 표현가능 A[1...n]

A[i]의 부모 = A[1/2]

A[i]의 왼쪽자식 = A[2i]

A[i]의 오른쪽자식 = A[2i+1]