[자료구조] 이진트리와 이진탐색트리

출처 : 트리(그래프) - 나무위키 (namu.wiki)

 

이번 글에서는 이진트리와 이진탐색트리를 살펴보겠습니다.

 

이진트리

노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 합니다.

 

이때 각 노드의 자식은 2명 이하만 유지해야 합니다.

 

이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점입니다.

 

예를 들어 위의 그림에서 노드 A의 왼쪽 자식은 B, 오른쪽 자식은 C입니다.

 

이때 왼쪽 자식을 다시 루트로 하는 서브 트리를 왼쪽 서브 트리(left subtree), 오른쪽 자식을 다시 루트로 하는 서브 트리를 오른쪽 서브 트리(right subtree)라고 합니다.

 

 

완전이진트리

루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리(complete binary tree)라고 합니다.

 

위의 그림을 보면서 '채우다'라는 말의 의미와 함께 좀 더 자세히 살펴보겠습니다.

 

1. 마지막 레벨을 제외한 레벨은 노드를 가득 채웁니다.

2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없습니다.

 

완전이진트리에서 너비 우선 탐색을 하며 각 노드에 0, 1, 2, ... 값을 주면 배열에 저장하는 인덱스와 일대일로 대응한다는 것을 알 수 있습니다.

 

높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2^(k+1) - 1개입니다.

 

따라서 n개의 노드를 저장할 수 있는 완전이진트리의 높이는 log n입니다.

 

 

이진탐색트리

이진탐색트리(binary Search tree)는 이진트리가 다음 조건을 만족하면 됩니다.

 

1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 합니다.

2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 합니다.

3. 같은 키 값을 갖는 노드는 없습니다.

 

이진탐색트리는 중위 순회를 하면 키 값의 오름차순으로 노드를 얻을 수 있다는 점과 구조가 단순하다는 점,

이진탐색과 비슷한 방식으로 검색이 가능하다는 점,

노드의 삽입이 쉽다는 점 등의 특징이 있어 폭넓게 사용됩니다.