본문 바로가기
IT 이것저것

트리(Tree) 개념, 용어, 종류(완전 이진트리, 전 이진트리, 포화 이진트리)

by 관성맨 2023. 1. 24.
반응형

오늘은 트리(Tree)의 개념에 대해서 알아보겠습니다.

 

 

 

 

 

 

 

 

 

트리의 개념 / 용어

 

트리는 노드로 이루어진 계층적 관계를 표현하는 비선형 자료구조입니다.

 

나뭇가지 형태의 이미지를 나타내며 트리 관련 용어를 먼저 살펴보도록 합시다.

 

 

위 트리를 보고 용어 설명 먼저드리도록 하겠습니다.

 

노드(Node) : 위 트리그림의 a,b,c,d,e,f 들을 노드라 합니다.

간선(Edge) : 노드와 노드를 연결하는 선을 간선이라고 합니다.

 

부모노드(Parent node) : 자식노드가 있는 노드 ( 예시 : b, c )

자식노드(Child node) : 부모노드로 부터 나온 노드 ( 예시 : d, e, f )

(예시 : 부모가 a이면 자식은 b,c / 부모가 b이면 자식은 d,e )

 

루트노드 (Root node) : 부모(Parent)가 없는 노드로 모든 트리는 단 하나의 루트 노드를 가집니다. (예시 : a ) 

단말노드 (Leaf node) : 자식이 없는 노드로 터미널(terminal)노드라고도 한다. (예시 : d, e, f)

 

노드의 깊이(depth) : 루트 노드에서 특정 노드에 도달하기까지 거쳐야 하는 간선의 수 (예시 : d의 깊이 : 2 / b의 깊이 : 1)

노드의 차수(degree) : 자식 노드의 개수 (예시 : b의 차수 : 2 / c의 차수 : 1)

트리의 차수 : 트리의 최대 차수로 보통 2

 

 

 

 

 

 

 

 

 

 

 

트리의 특징

 

- 트리의 루트노드는 하나이다.

- 루트노드는 0개 이상의 자식 노드를 갖는다.

- 트리에는 사이클 및 루프가 존재할 수 없다. (시작 노드에서 출발해 다시 돌아올 수 있으면 사이클이 존재한다고 함)

 

 

 

 

 

 

 

 

 

 

 

 

트리의 종류

 

트리의 종류에는 이진트리, 편향 이진트리, 완전 이진트리, 전 이진트리, 포화 이진트리가 있다.

 

 

 

이진트리 (Binary Tree)

이진트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 의미한다.

각 노드는 자식이 0개, 1개, 2개가 있을 수 있다.

 

 

 

 

완전 이진트리 (Complete Binary Tree)

 

마지막 레벨 제외 그 이전 레벨까지는 모든 레벨이 채워져 있어야 하며, 노드는 왼쪽에서 오른쪽으로 채워져야 한다.

 

 

 

전 이진트리 (Full Binary Tree)

전 이진트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리로 1개의 노드를 갖는 트리는 없어야 한다.

 

 

 

포화 이진트리 (Perfect Binary Tree)

포화 이진트리는 모든 레벨이 (마지막 레벨까지도) 노드로 꽉 차 있는 트리이다.

모든 말단 노드가 동일한 깊이를 가지는 트리이다.

 

 

 

트리의 종류가 많아 외우기에 좀 헷갈릴 수 있는 부분이 있다.

 

포화 이진트리는 의미 그대로 꽉 차있는 트리이기 때문에 모든 노드가 다 채워져있다고 보면 된다.

완전 이진트리와 전 이진트리가 헷갈릴 수 있는 부분인데 이렇게 외우고 다니면 좀 덜 헷갈리는 것 같습니다.

 

완전 이진트리는 전 이진트리보다 한글자가 더 있기 때문에 한 노드가 더 있어도 된다고 생각하면 헷갈리지 않을 수 있다고 봅니다.

감사합니다.

반응형