자료구조 - 이진 트리(Binary Tree)

이진 트리(Binary Tree)

---

이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 뜻한다.

트리 영역에서 가장 많이 사용되는 형태로 트리를 1차원 배열로 표현해준다.

 

이진 트리의 종류

왼쪽부터 편향 이진 트리, 포화 이진 트리, 완전 이진 트리 순서

1. 편향 이진 트리: 노드들이 한 쪽으로 편향돼 생성된 이진 트리

2. 포화 이진 트리: 프리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리

3. 완전 이진 트리: 마지막 레벨(차수)을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽 부터 채워진 트리

※ 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되므로 데이터를 담을 때 완전 이진 트리의 형태로 담는 것이 좋다.

 

이진 트리의 순차 표현

이진 트리의 순차 표현

가장 직관적이면서 편리한 트리 자료구조 형태는 바로 배열이다.

배열의 인덱스 간의 상관관계를 확인하여 식을 구하면 아래와 같다.

배열의 인덱스 연산

위의 이진 트리의 순차 표현 사진을 예시로 인덱스 연산을 해보면

D의 부모를 찾기 위해 D의 인덱스인 4를 2로 나누기 연산을 하면 값은 2가 나오고 2의 인덱스를 가진 B가 부모 노드라는 것을 알 수 있다.

C의 오른쪽 자식 노드를 구해보면 C의 인덱스인 3을 2로 곱하고 1을 더해주면 7이 나오고 7번 인덱스를 가진 G가 오른쪽 자식 노드라는 것을 확인할 수 있다.

이처럼 이진 트리는 1차원 배열 형태로 표현해주기 때문에 세그먼트 트리나 최소 공통 조상과 같은 알고리즘을 사용하기 위해서는 꼭 알아야할 개념이다.