트리 - swkim0128/PARA GitHub Wiki

트리의 개념

비선형 구조

원소들 간에 1:n 관계를 가지는 자료구조

원소들 간에 계층관계를 가지는 계층형 자료구조

상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다.

1. 노드 중 최상위 도느를 루트(root)라 한다.
2. 나머지 노드들은 n(≥ 0)개의 분리 집합 T1, ..., TN으로 분리될 수 있다.

이들 T1, ..., TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 한다.

노드(node) - 트리의 원소

간선(edge) - 노드와 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결

루트 노드(root node) - 트리의 시작 노드인 최상위 노드

형제 노드(sibling node) - 같은 부모 노드의 자식 노드들

조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

자손 노드 - 서브 트리에 있는 하위 레벨의 노드들

차수(degree)

노드의 차수 : 노드에 연결된 자식 노드의 수

트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값

단말 노드(리프 노드) : 차수가 0인 노드 즉, 자식 노드가 없는 노드

높이

노드의 높이 : 루트에서 노드에 이르는 갓너의 수

트리의 높이 트리에 있는 노드의 높이 중에서 가장 큰 값

차수가 2인 트리

각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리

왼쪽 자식 노드 (left child node)

오른쪽 자식 노드 (right child node)

모든 노드들이 최대 2개의 서브 트리를 갖는 특별한 형태의 트리

높이 i(레벨 i)에서의 노드의 최대 개수는 2의 i제곱개

높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h + 1)개가 되며, 최대 개수는 $2^h + ^1 - 1$ 개가 된다.

포화 이진 트리(Full Binary Tree)

모든 레벨에 노드가 포화 상태로 차 있는 이진 트리

높이가 h일 때, 최대의 노드 개수인 ( $2^h + ^1 - 1$ )의 노드를 가진 이진 트리

• 높이가 3일 때 15개의 노드

루트를 1번으로 하여 $2^h + ^1 - 1$ 까지 정해진 위치에 대한 노드 번호를 가짐

완전 이진 트리(Complete Binary Tree)

높이가 h이고 노드 수가 n개일 때 (단, h + 1 ≤ 2 < $2^h + ^1 - 1$ ), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

편향 이진 트리(Skewed Binary Tree)

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리

• 왼쪽 편향 이진 트리
• 오른쪽 편향 이진 트리

배열을 이용한 이진 트리의 표현

이진 트리에 각 노드 번호를 다음과 같이 부여

루트의 번호를 1로 함

레벨 n에 잇는 노드에 대하여 왼쪽부터 오른쪽으로 $2^n$부터 $2^n + ^1 - 1$ 까지 번호를 차례로 부여

노드 번호의 성질

노드 번호가 i인 노드의 부모 노드 번호 ? i / 2

노드 번호가 i인 노드의 왼쪽 자식 노드 번호? 2 * i

노드 번호가 i인 노드의 오른쪽 자식 노드 번호? 2 * i + 1

레벨 n의 노드 번호 시작 번호는? $2^n$

배열을 이용한 이진 트리의 표현의 단점

편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생

트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기 변경

비선형구조인 트리, 그래프의 각 도느(정점)를 중복되지 않게 전부 방문(visit) 하는 것을 말하는데 비선형구조는 선형 구조에서와 같이 선후 연결 관계를 알 수 없다. 따라서, 특별한 방법이 필요하다.

• 너비 우선 탐색(Breadth First Search, BFS)
• 깊이 우선 탐색(Depth First Search, DFS)

너비 우선 탐색

너비 우선 탐색은 루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식

인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료 구조인 큐를 활용함.

BFS()
	큐 생성
	루트 v를 큐에 삽입
	
	while (큐가 비어 있지 않은 경우) {
		t <- 큐에 첫 번째 원소 반환
		t 방문
		
		for (t와 연결된 모든 간선에 대해) {
			u <- t의 자식노드
			u를 큐에 삽입
		}
	}
end BFS()

깊이 우선 탐색

루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 모든 노드를 방문하는 순회방법

가장 마지막에 만낫던 갈림길의 노드로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택을 사용해서 구현

DFS(v)
	v 방문;
	
	for (v의 모든 자식 노드 w) {
		DFS(w);
	}
end DFS()

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

3가지의 기본적인 순회방법

• 전위순회(preorder traversal) : VLR

  • 부모노드 방문 후, 자식노드를 좌, 우 순서로 방문한다.

• 중위순회(inorder traversal) : LVR

  • 왼쪽 자식노드, 부모노드, 오른쪽 자식노드 순으로 방문한다.

• 후위순회(postorder traversal) : LRV

  • 자식노드를 좌우 순서로 방문한 후, 부모노드로 방문한다.

전위 순회(preorder traversal)

수행 방법

1. 현재 노드 T를 방문하여 처리한다. → V
2. 현재 노드 T의 왼쪽 서브트리로 이동한다. → L
3. 현재 노드 T의 오른쪽 서브트리로 이동한다. → R

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

중위 순회(inorder traversal)

수행 방법

1. 현재 노드 T의 왼쪽 서브트리로 이동한다. → L
2. 현재 노드 T를 방문하여 처리한다. → V
3. 현재 노드 T의 오른쪽 서브트리로 이동한다. → R

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

후위 순회(postorder traversal)

수행 방법

1. 현재 노드 T의 왼쪽 서브트리로 이동한다. → L
2. 현재 노드 T의 오른쪽 서브트리로 이동한다. → R
3. 현재 노드 T를 방문하여 처리한다. → V

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

수식트리

수식을 표현하는 이진 트리

수식 이진 트리(Expression Binary Tree)라고 부르기도 함.

연산자는 루트 노드이거나 가지 노드

피연산자는 모두 잎 노드

• 중위 순회 : A / B * C * D + E (식의 중위 표기법)
• 후위 순회 : A B / C * D * E + (식의 후위 표기법)
• 전위 순회 : + * * / A B C D E (식의 전위 표긱법)