11. 이진트리 - 트리 루트노드, 리프노드, 부모,형제 노드 / 길이, 깊이, 높이 / 이진트리 / 포화 이진 트리 / 완전 이진 트리 / 높이 균형 트리

이진트리

이진 트리의 필요성과, 이진 트리와 관련한 다양한 용어를 이해한다.

 

트리

 트리(Tree)는 나무의 형태를 뒤집은 것과 같은 형태의 자료구조이다.

트리의 일반적인 형태

루트 노드와 리프 노드

루프 노드와 리프 노드. 가지로 연결되어 있다.

트리에서 가장 위에 존재하는(가지가 뻗어나가기 시작하는) 노드를 루트노드, 가장 아랫단 즉 끝에 있는 노드들을 각각 리프노드라고 부른다.

 

부모 노드, 자식 노드, 형제 노드

트리에서 각각의 노드는 부모-자식 관계를 가지며, 부모가 같은 노드들은 형제노드라고 부른다.

트리의 길이, 깊이, 높이

 

트리에서 길이(Length)란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미한다.

루트 노드에서부터 리프 노드까지의 길이 2

깊이(Depth)란 루트 노드에서 특정 노드까지의 길이를 의미한다.

트리의 높이(Heifht)란 루트 노드에서 가장 깊은 노드까지의 길이를 말한다.

위 트리의 높이는 2이다

이진트리

이진 트리(Binary Tree)는 최대 2개의 자식을 가질 수 있는 트리이다. 구현이 간단하다는 점에서 다방면에서 활용되는 자료 구조 중 하나이다.

 

포화 이진 트리

포화 이진 트리(Full Binary Tree)는 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리이다.

오른쪽은 포화 이진 트리가 아니다

 

완전 이진 트리

완전 이진 트리(Complete Binary Tree)는 모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드이다. 포화 이진트리에 가까운 형태로, 완전 이진 트리 또한 안정적인 트리형태를 갖춘다.

높이 균형 트리

높이 균형 트리(Height Balanced Tree)는 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1이상 차이 나지 않는 트리이다.  높이 균형이 맞지 않는 트리는 편향트리라고 한다.(아래 그림 오른쪽 참고)

편향 이진트리의 경우, 한 쪽으로 몰려있기 때문에 바르지 못한 자료구조이다. 높이 균형을 맞추는 방법까지 공부하는 것이 좋다.

 

1. 요약
2. 이진 트리는 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 활용의 효율성이 높아진다.
3. 트리는 데이터 저장, 탐색 등의 다양한 목적에서 사용할 수 있다.