이진 탐색 트리(Data Search Tree)

이번 포스트에서는 자료 구조 중 하나인 이진 탐색 트리(Binary Search Tree)에 대해 다뤄보자.

효율적인 자료 검색을 목적으로 만들어진 기존 이진 트리에 몇 가지 제약 사항을 추가한 이진 탐색 트리는 기존의 빠른 검색의 특징을 가진 이진 탐색(binary search)과 잦은 데이터 변경에 유연하게 대처가 가능한 연결 리스트(linked list)의 특징을 모두 갖고 있다.

프로그래머 면접에서 자주 등장하는 자료 구조 관련 질문이며 실무에서 또한 사용되는 경우가 종종 있다.

자 그럼 이진 탐색 트리에 대해 알아보자.

이진 탐색 트리란?

(이진 탐색 트리의 예)

위에 첨부된 이미지와 아래 작성된 특징을 함께 참조하면 보다 이해하기 쉽다.

이진 탐색 트리가 가진 특징

1. 트리 내 각 노드들은 유일한 키를 가지고 있다.
2. 왼쪽 서브 트리에 있는 모든 노드의 키는 루트의 키보다 작다.
3. 오른쪽 서브 트리에 있는 모든 노드의 키는 루트의 키보다 크다.
4. 하나의 노드에는 최대 두 갈래 링크까지만 존재한다.
5. 한번 분기되어 나눠진 서브 트리 또한 하나의 이진 탐색 트리이다.

위 이미지를 예로 들면 ‘7’을 루트(기준)로 삼았을 때 ‘7’보다 작은 값은 좌측에, ‘7’보다 큰 값은 우측에 배치되었다.

그 후 ‘4’와 ‘9’를 기준으로 같은 규칙의 이진 탐색 트리가 각각 구성된 모습을 볼 수 있다.

이것이 이진 탐색 트리가 가진 제일 기본적인 특징이다.

빠른 정보 검색

위와 같이 적은 양의 숫자가 아닌 무수한 숫자(데이터)가 일렬로 배열되어 있다고 가정해보자.

이후 위와 같은 조건으로 ‘5’를 탐색할 일이 있다면 최초에 배치되어 있는 숫자부터 하나씩 값이 ‘5’인지 확인하며 탐색을 진행할 것이다.

하지만 이는 효율적인 방법이 아니다 만일 ‘5’가 전면에 배치되어 있을 경우, 탐색 시간이 오래 걸리지 않을 수 있지만 다른 값을 탐색하거나 후면에 배치되어 있을 경우에는 다소 시간이 필요할 수 있다.

하지만 이진 탐색 트리를 사용한다면 각 노드 별로 상하 관계에 의해 데이터를 탐색하기 때문에 비교적 적은 비용으로 원하는 데이터를 찾아낼 수 있는 것이다.

이진 탐색 트리를 다루는 방법

다음으로는 위와 같은 이진 탐색 트리를 구성하고 수정하는 방법에 대해 알아보자.

삽입 (insertion)

이진 탐색 트리의 노드 삽입 과정은 비교적 간단하다.
루트에서부터 대소 관계를 비교하며 삽입하고자 하는 노드의 값이 배치될 자리를 찾은 뒤, 해당 위치에 노드를 배치한다.

(보라색 화살표: 탐색, 붉은색 화살표: 탐색 및 삽입)

위 이미지는 ‘5’를 삽입하는 과정을 표현한 자료다. 아래 설명을 참조하자.

1. 루트(최상위 노드)인 ‘7’과 비교하였을 때 삽입하고자 하는 값이 작아 좌측으로 이동한다.
2. 이후 다음 노드인 ‘4’ 와 비교하였을때는 삽입하고자 하는 값이 더 크기 때문에 우측에 노드를 배치한다.

삭제 (deletion)

이진 탐색 트리의 노드 삭제 과정은 삽입 과정보다는 조금 복잡하다.
먼저 위 탐색하는 과정은 같으나 삭제하기 전 이진 탐색 트리의 특징을 유지하기 위해 아래와 같은 노드의 상태를 고려하여 삭제를 진행하여야만 한다.

1. 삭제하고자 하는 노드가 단일 노드일 경우 (자식 노드가 없는 경우)
2. 삭제하고자 하는 노드의 자식 노드가 하나일 경우
3. 삭제하고자 하는 노드의 자식 노드가 두 개의 서브 트리를 가지고 있을 경우

1. 삭제하고자 하는 노드가 단일 노드일 경우 (자식 노드가 없는 경우)

위와 같이 삭제하고자 하는 노드(11)가 단일 노드일 경우에는 별 다른 고려 사항 없이 해당 노드를 삭제하면 된다.

2. 삭제하고자 하는 노드의 자식 노드가 하나일 경우

위 이미지에서는 ‘9’를 삭제하려고 한다.

이 경우에는 ‘9’의 위치를 먼저 탐색한 뒤, 삭제하고자 하는 노드의 하위 노드(단일 노드, 11)와 삭제하고자 하는 상위 노드(7)를 연결시켜주고 ‘9’를 삭제하여 이진 탐색 트리의 특성을 잃지 않도록 유지한다.

3. 삭제하고자 하는 노드의 자식 노드가 두 개의 서브 트리를 가지고 있을 경우

다음으로는 삭제를 희망하는 노드의 하위 노드가 두 개의 서브 트리를 가지고 있을 때이다.

이진 트리의 구조를 유지하기 위해서 여러 가지 사항을 고려해야 하지만, 하나의 규칙만 기억하면 이해하기 쉽다.

먼저 ‘5’를 삭제하고자 하는 경우, 해당 노드는 좌측에 배치되어 있는 서브 트리다.

이와 같은 경우에는 좌측 서브 트리 중 제일 높은 값(삭제 노드 기준의 우측에 배치된 노드)와 교체한다.

반대로 ‘9’를 삭제하고자 하는 경우, 해당 노드는 우측에 배치되어 있는 서브 트리다.

이 경우는 우측 서브 트리 중 제일 낮은 값(삭제 노드 기준의 좌측에 배치된 노드)과 교체한다.

이 규칙을 적용하면 각각 아래의 이미지와 같이 노드 삭제 및 대체가 가능하며 이진 탐색 트리의 구조 또한 해치지 않는다.

마무리

오늘은 자료 구조 중 ‘이진 탐색 트리’에 대해 알아보았다.

한번 확실하게 학습해놓으면 잊지 않고 유용하게 사용할 수 있을 것 같다.

앞으로 자료 구조 공부도 꾸준히 진행하면서 계속해서 포스팅해볼 생각이다.

끝