자료구조 (5)

트리 Tree

1대1 관계를 갖는 선형 linear 구조와 달리 1대 多 관계를 갖는 비선형 자료구조(Nonlinear data structure)이다. 이뿐만 아니라 원소들 간의 계층관계를 가지는 계층형 자료구조(Hierarchical data structure)이다.

 

트리의 용어설명

• 노드Node : 원소이다. 트리는 이들이 모인 결과의 집합이다.
• 차수degree : 연결된 자식노드의 수이다.
  • 트리의 차수 : 트리 내의 노드의 차수 중에 가장 큰 값이다. 아래 그림에서는 노드 A D의 차수가 3과 같다. 
• 간선Edge : 부모와 자식노드의 연결선.
• 높이Height or level : 높이에 따른 계층구분.
  • 트리의 높이는 그 트리의 높이 중에서 가장 큰값이 된다. 아래 그림을 예시로 들면 레벨 3이다.
• 루트root 노드 : 근본인 시작노드.
• 단말Termina노드l or 잎Leaf노드 : 차수 0인, 자식이 없는 노드.
• 서브 트리Sub tree :  부모노드와 간선을 끊었을 때 생기는 트리. 자식이 있다면 그 갯수만큼 서브 트리를 가진다.
• 형제Sibling노드 : 같은 부모를 공유하는 노드. 아래 E와 F가 형제 노드다.
• 포레스트Forest : 아래 A노드를 없애면 B,C,D의 트리가 생겨난다. 이 트리들의 집합이 포레스트다.

이진트리 Binary tree

자식노드를 갖는다면 왼쪽 혹은 오른쪽 노드만을 가지게 함으로써 차수가 2 이하로 유지되도록 하는 제한 트리.

자식노드를 갖는다면 위의 형태로만.

이렇게 정의를 함에 따라 구현과 연산을 단순하게 할 수 있다.

이진트리의 특성은 다음과 같다.

• 노드 수가 n이라면 간선 수는 n-1이 된다.
• 높이가 h라면 이 트리의 노드 수는 (h+1) ~ {2^(h+1)-1}이 된다.

 

이진 트리의 종류

• 포화 이진 트리 Full binary tree : 높이가 정해졌을 때 해당 높이에서 가질 수 있는 노드를 전부 채운 트리. {2^(h+1)-1}개의 노드수를 가진 트리이다.

• 완전 이진 트리 Complete binary tree : 트리의 높이가 h일 때, 레벨 0부터 레벨 h-1까지는 포화 상태이고, 마지막 레벨 h는 왼쪽부터 차례로 노드가 채워진 이진 트리. 다음은 노드 수가 12인 완전 이진 트리이다.

• 편향 이진 트리 Skewed binary tree : h+1개의 노드 수를 가지면서 한쪽 방향의 자식노드만을 가진 트리.

 

이진트리의 구현

순차 자료구조방식의 구현 : 1차원 배열로, 인덱스 위치로 부모와 자식 노드를 표시한다.

완전 이진 트리

좌편향 이진트리

1차배열에서 원하는 노드의 위치를 찾는 식은 다음과 같다.

 

이러한 1차원 배열의 이진트리는 메모리낭비가 심하고, 트리의 높이를 상황에 따라 동적으로 변경하기 어렵다. 그러나 부모/자식 노드의 표현을 위한 별도의 메모리공간은 필요로 하지 않고, 이 노드들의 위치, 인덱스를 통해 간단히 찾아낼 수 있다. 또한 높이가 고정된 이진트리를 표현하는 경우에는 1차원배열 사용이 더 나을 수 있다.

 

연결 자료구조방식으로 구현 : 부모노드가 왼쪽/오른쪽 자식 노드에 대한 링크를 지님.

이진 트리에서는 하나의 노드가 최대 2개 이하의 차수만을 가질 수 있으므로 '이중연결리스트' 구현한다. 자바로는 다음과 같이 표현할 수 있다.

class Node{
	char data;
	Node leftChild;
	Node rightChild;
}

 

연결 자료구조의 완전 이진 트리 표현

 

 

이진 트리의 순회 Traversal

이진 트리의 모든 노드를 한 번씩 방문하여 데이터를 처리하는 연산이다.

현재 노드를 방문하여 데이터를 처리하는 작업 D, 현재 노드에서 왼쪽 서브트리를 순회하는 것은 L, 오른쪽 서브트리로 순회하는것을 R이라 표현하자.

그럼 시작 위치에 따라 순회의 종류도 나뉜다.

전위 순회 : DLR

중위 순회 : LDR

후위 순회 : LRD

 

전위 순회 Preorder traversal

중위 순회 Inorder traversal

후위 순회 Postorder traversal