이론공부/자료구조

트리(Tree)

멍토 2020. 4. 19.

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

트리의 개념

비선형 구조

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

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

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

정의

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

노드 중 최상위 노드를 루트(root)라 한다

나머지 노드들은 n(>=0)개의 분리 집합 T1, ... TN으로 분리될 수 있다.

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

Tree의 구성 요소, 용어

Node : 트리의 원소 (그림에서의 동그라미 부분)

Edge(간선) : 노드를 연결하는 선, 부모노드와 자식노드를 연결한다.

Root Node : 제일 최상위 노드( 그림에서 숫자2를 가진 노드)

Sibling Node(형제노드) : 같은 부모 노드의 자식 노드들 (7, 5의 값을 가진 노드들은 형제노드이다.)

Ancestor Node(조상노드) : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

(11을 기준으로 잡으면 6, 7, 2가 조상 노드이다.)

Sub Tree : 간선을 끊으면 따로 생기는 트리들

Descendent Node(자손노드) : 서브트리에 있는 하위 레벨의 노드들(7의 자손노드는 2, 6, 5, 11이다.)

Degree(차수) : 노드에 연결된 자식 노드의 수(7의 차수는 2이다)

트리의 차수 : 트리에 있는 차수중에서 가장 큰 값(2진트리이므로 최대 차수는 2이다)

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

높이 : 루트의 노드를 높이를 기준으로 잡고 아래로 내려갈수록 높이가 1개씩 늘어난다.

트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값(아래 그림은 높이가 3이다)

댓글