트리 - 이진 트리, 완전 이진 트리

트리라는 자료구조를 이용하면 계층 구조의 데이터를 쉽게 표현 할 수 있습니다.

 

👀 트리란?

👉 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료구조입니다.

(계층형 자료구조란 데이터가 트리 형태의 구조로 조직된 것)

 

앞에서 살펴 보았던 큐(Queue), 스택(Stack)은 자료구조에서 선형 구조라고 합니다.

 

👉 형태적 차이점
선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미합니다.

비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다.

 

👉 용도적 차이점

선형 구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,

비선형 구조는 표현에 초점이 맞춰져 있습니다.

(하나의 데이터의 밑에 밑에 어떤 데이터가 있는 지가 더 중요하다면 트리구조가 적합합니다.)

 

아래의 폴더 구조가 대표적인 트리의 형태입니다.

트리는 이름에서부터 느껴지듯이 계층형 구조입니다. 위, 아래가 구분 되어 있습니다.

 

👀 트리에 나오는 용어들

 

👉 Node: 트리에서 데이터를 저장하는 기본 요소(노드+포인터 -> Node)

👉 Root Node: 트리 맨 위에 있는 노드

👉 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄

👉 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드

👉 Child Node: 어떤 노드의 하위 레벨에 연결된 노드

👉 Leaf Node(Terminal Node): Child Node가 하나도 없는 노드

👉 Sibling: 동일한 Parent Node를 가진 노드(형제 자매)

👉 Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

👀 트리의 종류

👉 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등 되게 다양한 트리가 있지만 일단 이진 트리와 완전 이진 트리만 알아보겠습니다.

 

👉 이진 트리(Binary Tree)의 특징은 각  노드가 최대 두 개의 자식을 가진다는 것입니다.

하위의 노드가 4~5개 일 수 없고, 무조건 0, 1, 2개만 있어야 합니다.

 

👉 완전 이진 트리(Complete Binary Tree)의 특징은 노드를 삽입 할 때 최하단 왼쪽 노드부터 차례대로 삽입 해야 한다는 것입니다.

 

👀 완전 이진 트리를 표현하는 방법

: 트리 구조를 표현하는 방법에는 2가지가 있다.

👉 직접 클래스를 구현해서 사용하는 방법

👉 배열로 표현하는 방법

 

❓ 그렇다면 트리 구조를 어떻게 배열에 저장 할 수 있을까요?

바로 완전 이진 트리를 쓰는 경우에 사용 할 수 있습니다.

👉 완전 이진 트리는 왼쪽부터 데이터가 쌓이게 되는데, 이를 순서대로 배열에 쌓으면서 표현할 수 있습니다.

 

예를 들어 아래와 같은 완전 이진 트리를 배열에 표현한다면, 다음과 같습니다!

이때 배열에 첫번째 인덱스(0)에 None을 넣는 이유는 자식 인덱스나 부모 인덱스를 구할 때 현재 인덱스에 곱하기 연산하여 구하게 되는 데 그럴 때 0을 곱하게 되면 결과가 0만 나오기 때문에 첫번째 인덱스(0)에는 None을 넣는 것이다.

 

❓ 완전 이진 트리의 높이는 어떻게 구할 수 있을까요?

👉 트리의 높이(height)는, 루트 노드부터 가장 아래 리프 노드까지의 길이를 말합니다.

예를 들어 다음과 같은 트리의 높이는 2라고 할 수 있습니다.

 

그렇다면 각 레벨에 노드가 꽉 차있을 경우 몇 개의 노드가 있는 지 생각 해봅시다!

 

아래 예시를 보면, 레벨을 k라고 한다면 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k 개수 임을 알 수 있습니다.

만약 높이가 h 인데 모든 노드가 꽉 차 있는 완전 이진 트리라면 모든 노드의 개수는 몇개일까요?

즉, 높이가 h 일 때 최대 노드의 개수는 2^(h+1) -1개 입니다.

 

❓ 그러면 이 때 최대 노드의 개수가 N이라면, h 는 뭘까요?

 

2^(h+1) -1 = N → h = log_2(N+1)-1 라고 할 수 있습니다!

 

즉! 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log_2(N+1) - 1 이므로

(상수를 제외하고 생각 해보면)

이진 트리의 높이는 최대로 해봤자 O(log(N))인 것을 알 수 있습니다.