자료구조 이진트리(Binary Tree) 그림으로 쉽게 이해하기

자료구조 이진트리(Binary Tree) 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 자료구조 중에서 이진트리(Binary Tree)에 대한 포스팅을 진행하겠습니다.

그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)

 

 

- 이진트리(Binary Tree)란?

이진트리(Binary Tree)는 트리 중에서도 각 노드가 최대 2개의 자식노드를 가질 때 이진트리(Binary Tree)라고 합니다.
최대 2개이기 때문에 자식이 없을 수도 있고, 한개만 있을 수도 있습니다.
이때 자식노드는 각각 왼쪽 자식노드와 오른쪽 자식노드로 표현을 합니다.

그래서 같은 루트에 같은 자식노드 하나를 가지고 있어도

자식노드의 위치가 각각 왼쪽과 오른쪽으로 다르다면 그 두 트리는 서로 다른 트리가 됩니다.

 

 

자식 노드의 위치가 다르다면 서로 다른 트리다

 

 

- 이진트리(Binary Tree)의 종류

1) 정 이진트리(Full Binary Tree)

이진트리(Binary Tree) 중에서도 모든 노드가 2개의 자식을 가지거나 자식이 없는 경우에는

정 이진트리(Full Binary Tree), 혹은 엄격한 이진트리(Strcit Binary Tree)라고 합니다.
다시 말해서, 자식이 한 개인 경우가 없어야 정 이진트리입니다.

 

 

모든 노드가 2개의 자식을 가지거나 자식이 없는 경우 정 이진트리 혹은 엄격한 이진트리라 한다

 

위 그림에서 왼쪽 트리의 경우는 자식을 하나만 가지는 노드가 있기 때문에 정이진트리가 될 수 없고,
오른쪽 트리의 경우는 모든 노드들이 자식을 두개 가지거나, 아예 가지고 있지 않기 때문에 정이진트리가 될 수 있습니다.

 

 

2) 포화 이진트리(Perfect Binary Tree)

그리고 이진트리 중에서도 모든 노드가 2개의 자식을 가지고 leaf노드가 모두 같은 레벨(level)일때는

포화 이진트리(perfect binary tree)라고 합니다.

포화이진트리는 높이가 h인 포화 이진트리에서 노드 갯수는 2의 k+1 제곱 -1의 특징을 갖습니다.

포화이진트리에서는 모든 레벨(level)의 노드가 꽉차있기 때문에 자식노드의 개수가 2의 제곱수만큼 증가하기 때문이죠.
루트부터 해서 각 레벨(level)별로 2의 0제곱 2의 1제곱 2의 2제곱과 같은 순으로 자식노드가 생성되기 때문에

이것을 식으로 일반화하면 2의 k+1제곱에 -1로 표현할 수 있는것입니다.
그리고 포화이진트리에서 leaf노드의 개수는 2의 h제곱 개수가 된다는 특징도 있겠죠.

 

 

포화 이진트리

 

 

3) 완전이진트리(Complete binary tree)

그리고 완전이진트리(Complete binary tree)라는 트리가 있습니다.

 

이 트리는 두가지 조건을 충족해야 합니다.

첫째, 마지막 레벨(level)을 제외하고 모든 노드가 채워져있어야 합니다.

마지막 레벨의 노드는 다 채워져 있을 수도 있고 아닐수도 있습니다.

둘째, 노드는 왼쪽에서 오른쪽 방향으로 채워져야 합니다. 
그래서 어느 노드에 오른쪽 자식이 존재한다면 왼쪽 자식도 가지고 있어야 완전이진트리로 볼 수 있습니다.

 

 

완전이진트리 성립의 예

 

위 왼쪽 그림에서 이 부분은 왼쪽 자식 하나만 있어도 왼쪽에서 오른쪽으로 채워져야 한다는 완전이진트리(Complete binary tree)의 조건을 충족하기 때문에 완전이진트리(Complete binary tree)라고 할 수 있습니다.

바로 앞에서 배웠던 포화이진트리(Perfect binary tree)도 완전이진트리(Complete binary tree)의 조건을 모두 충족하기 때문에 완전이진트리에 속할 수 있습니다.

하지만 완전 이진트리라고 해서 포화이진트리라는 역은 성립하지 않습니다.

 

 

완전 이진트리가 성립되지 않는 예

 

그리고 위 왼쪽 그림의 트리처럼 오른쪽 자식노드는 있지만 왼쪽 자식 노드는 없다면 완전이진트리가 성립하지 않습니다.
그리고 오른쪽 그림의 트리도 왼쪽부터 채우고 있지 않기 때문에 완전 이진트리가 될 수 없습니다.

 

반응형

 

- 이진트리의 특징

1) 1차원 배열로 표현 할 수 있다.

그래서 이런 이진트리는 트리지만 선형자료구조인 1차원 배열로도 표현할 수 있다는 특징을 가집니다.

 

 

이진트리는 선형자료구조인 1차원 배열로도 표현 할 수 있다

 

 

위 그림처럼 루트에서 시작해서 왼쪽노드부터 오른쪽 노드까지 순서를 매기면

완전이진트리(Complete binary tree)같은 경우는 빈숫자가 없게 됩니다.

그래서 완전이진트리(Complete binary tree)는 각 번호를 인덱스로 써서 1차원 배열로 표현이 가능합니다. 
완전 이진트리는 1차원 배열에서 이렇게 빈틈없이 값을 채운 배열이 될 수 있고,
중간에 빈 값이 있는 이진트리는 배열로 표현하면 비어있는 공간의 인덱스에

null값이 들어간 1차원 배열로 표현할 수 있습니다.

중간에 빈 값이 있는 이진트리의 배열 표현

 

그래서 이렇게 1차원 배열로 이진트리를 표현할 때는 0번째 인덱스를 비워두고 첫번째 인덱스부터 루트값이 들어갑니다.
첫번째 인덱스부터 루트값을 넣으면은 인덱스 위치로 찾을 수 있는 몇가지 연산이 있기 때문입니다.

 

1) 이진트리의 연산

그래서 i번재 인덱스에 들어있는 노드의 부모는 i/2연산을 한 인덱스의 위치에 들어가 있게 되고,
노드 i의 왼쪽 자식은 i*2를한 인덱스에 들어있게 됩니다.
노드 i의 오른쪽 자식은 i*2+1을한 위치의 인덱스에서 찾을 수 있습니다.
배열로 표현된 트리에서 6번째 노드의 부모는 나누기2를 한 3번째 인덱스에 위치하게 되고,
노드 2의 왼쪽 자식 노드는 2*2를한 4번째 위치에서 찾을 수 있다는 것을 알 수 있습니다.

 

 

이진트리의 몇가지 연산

 

 

- 이진트리(Binary Tree)의 단점

이렇게 1차원 배열로 이진트리를 표현하게 되면 간단하게 트리를 나타낼 수 있다는 장점이 있지만,
배열의 한계인 공간의 제약이나 데이터의 삽입, 삭제시에 기존 데이터의 이동과 같은 단점은 여전히 극복할 수 없기 때문에 트리는 왠만하면 배열보다는 노드의 연결로만 표현하게 됩니다.

그래서 실제 코드작성시 각 노드의 next point 대신에

왼쪽 자식과 오른쪽 자식을 가리킬 수 있는 left, right point를 두어서 연결 관계를 표현하게 되고,
이때 데이터를 저장할 수 있는 데이터 필드는 이전 노드들과 동일하게 가지고 있습니다.

 

 

실제 코드 작성

 

 

- 정리 및 요약

이런 이진트리(Binary Tree)는 많은 응용 트리의 기초가 된다고 했습니다.
뒤에서 배울 힙(heep)이라는 자료구조도 이 이진트리를 응용한 자료구조의 하나이고
binary search tree, 줄여서 BST라고 하는 이진탐색트리도 이진트리의 응용입니다.

여기서 이진트리와 이진탐색트리는 다른 개념이기 때문이기 때문에 헷갈리시면 안됩니다.

 

그리고 B-Tree도 이진트리의 응용인데 이 트리는 데이터베이스나 파일시스템에서 중요하게 다뤄지는 자료구조입니다.
마지막으로 AVL트리라고 하는 이진탐색트리의 응용트리도 트리 자료구조에 대해서 어느 정도 이해가 되고나면 나중에 꼭 공부해보면 좋을 자료구조입니다.

트리도 자료구조이기 때문에 앞에서 배운 다른 자료구조와 동일하게

기본적으로 트리에 데이터를 삽입하고 삭제하고 검색하는 기본 연산이 있습니다.
그리고 다른 자료구조와 한가지 다름점이 있다면 트리에는 트리탐색이라는 연산이 있다는 것입니다.

앞에서 배운 선형적인 자료구조들은 앞에서부터 모든 데이터들을 쭉 스캔하는게 그렇게 어려운 문제가 아니었는데
연결 관계로 표현된 트리같은 경우는 구조 특성상 모든 데이터 항목들을 탐색하는 방법이 다를 수밖에 없습니다.

다음 포스팅에서는 트리구조에서 데이터 탐색을 어떻게 하는지 알아보도록 하겠습니다. 

 

로스윗의 코딩캠프는

미래의 개발자 여러분을 응원합니다.

모두 화이팅!!

 

 

알고리즘 퀵정렬(Quick sort) 그림으로 쉽게 이해하기

 

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)