트리(tree)

트리(tree)

비선형 구조

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

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

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

노드(node) - 트리의 원소

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

• 노드 중 최상위 노드를 루트(root)라고 한다.(상위 노드가 없는 유일한 노드)
• 나머지 노드들은 n(>=0)개의 분리 집합 T1, T2, ... ,TN 으로 분리될 수 있다.
• 단말노드(leaf node) : 더 이상 하위 노드를 가질 수 없는 노드

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

용어 정리

노드(node) - 트리의 원소

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

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

형제 노드(sibling node) - 같은 부모 노드의 자식 노드들, 형제 노드끼리는 간선 연결이 없다. 트리는 사이클이 없는 그래프

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

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

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

차수(degree)

• 노드의 차수 : 노드에 연결된 자식 노드의 수
• 트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값
• 단말 노드(리프노드) : 차수가 0인 노드, 즉 자식 노드가 없는 노드

높이

• 노드의 높이 : 로트에서 노드에 이르는 간선의 수, 노드의 레벨
• 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨

이진 트리

차수가 2인 트리

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

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

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

특성

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

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

종류

포화 이진 트리(perfect binary tree)

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

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

모든 단말노드에서의 높이가 동일하다.

루트를 1번으로 $2^{h+1} - 1$까지 정해진 위치에 대한 노드 번호를 가진다.

완전 이진 트리(complete binary tree)

높이가 h이고 노드 수가 n개 일 때 (단, h+1 <= n < 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

1차원 배열의 인덱스로 관리 가능

높이가 h인 이진 트리를 위한 배열의 크기

레벨 i의 최대 노드 수는? 2^i

따라서 모든 노드의 수는 2^(h+1) - 1

배열의 크기는 2^(h+1) - 1 (0 인덱스는 사용하지 않는다.)

단점

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

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

비선형 자료구조 완전탐색

비선형 구조인 트리, 그래프의 각 노드(정점)을 중복되지 않게 방문(visit)

비선형 구조는 선형 구조에서와 같이 선후 연결 관계를 알 수 없다.

두 가지 방법

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