알고리즘 개념[실전] - 이진 트리

이진 트리(Binary Tree)는 각 노드의 자식 노의 갯수가 2 이하로 구성되어 있는 트리를 말합니다.

이진 트리의 핵심 이론

이진트리의 종류

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

• 포화 이진 트리 : 트리의 높이가 모두 일정하며, 리프 노드가 꽉 차있는 이진 트리.

• 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 형태의 트리.

데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되는 단점이 있습니다.

일반적으로 코딩 테스트에서 데이터를 트리에 담고 싶으면 완전 이진 트리를 떠올리면 됩니다.

이진 트리의 순차 표현

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

위처럼 1차원 배열의 형태로 표현 가능합니다. 그리고 1차원 배열의 형태로 표현 시 트리의 노드와 배열의 인덱스 간의 상관관계는 다음과 같습니다.

트리의 노드와 배열의 인덱스 사이 상관관계

루트 노드 - index = 1
부모 노드 - index = index / 2(현재 노드가 루트 노드가 아닌 경우)
왼쪽 자식 노드 - index = index 2(노드 갯수가 인덱스의 2배 이상인 경우)
오른쪽 자식 노드 - index = index 2 + 1(노드 갯수가 인덱스의 2배 +1 이상인 경우)