Binary Search Tree란?
Binary Search Tree는 Binary Tree의 한 종류로써, 데이터를 저장하고 탐색하기 위한 자료 구조이다. Binary Search Tree는 각 노드가 특정한 값을 가지고 있고, 각 노드의 왼쪽 서브트리에는 노드의 값보다 더 작은 값의 노드들이, 오른쪽 서브트리에는 더 큰 값의 노드들이 위치하도록 만들어진다.
이러한 특성으로 인해 Binary Search Tree는 아래와 같은 특징을 가진다.
- 값들이 정렬되어 있는 Binary Tree 구조이다 : 특정 노드를 기준으로 해당 노드 왼쪽에 있는 노드들은 모두 해당 노드의 값보다 작은 값을 가지며, 해당 노드 오른쪽에 있는 노드들은 해당 노드의 값보다 큰 값을 가진다.
- 위와 같이 정렬되어 있어, Binary Search Tree는 탐색, 삽입, 삭제 연산에 매우 효율적이다.
Binary Search Tree의 한계
하지만 기본적인 Binary Search Tree는 아래와 같이 한쪽으로 모든 노드가 쏠려 있는 최악의 상황을 가질 수 있다.
이런 경우 Binary Search Tree의 장점은 모두 사라진다. 예를 들어 위 그림2에서 100을 찾기 위해 모든 노드를 다 탐색해야 하며, 150을 더하기 위해서도 모든 노드를 탐색해야 하고, 100을 삭제하기 위해서도 모든 노드를 다 탐색해야 한다. 즉, 탐색에 효율적인 Binary Search Tree의 장점이 모두 사라지는 것이다.
Kotlin, Java에서는 이를 어떻게 해결하는가?
이를 해결하기 위해 Kotlin, Java에서는 Binary Search 한쪽에 쏠리는 현상을 감지한 다음, Root 노드를 바꾸고 Tree를 다시 구성하는 방법을 취한다. Red Black Tree 등이 수행하는 연산이 바로 이것이다. Red Black Tree는 노드들이 한쪽으로 쏠리는 것을 인지해서 해당 쏠림을 해결하기 위해 Tree를 재구성하는 방법을 취한다.
이 동작 방식은 매우 복잡해서 만약 궁금하다면 아래 글을 참고하자.
레드-블랙 트리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년
ko.wikipedia.org
예를 들어 위 그림2의 Binary Search Tree는 아래와 같이 재구성 될 수 있다.
Binary Search Tree의 탐색 삽입, 삭제 연산에 대한 시간 복잡도
Binary Search Tree의 원소 개수가 N이라 할 때 시간 복잡도는 아래와 같다.
탐색 시간 복잡도
Binary Search Tree는 탐색을 위해 기본적으로 O(logN)의 시간 복잡도를 가진다. 탐색을 한 번 수행할 때마다 탐색해야 될 노드가 반으로 줄기 때문이다.
하지만 그림2와 같은 최악의 경우 O(N)이 될 수 있다.
삽입
Binary Search Tree는 삽입을 위해 기본적으로 O(logN)의 시간 복잡도를 가진다. 탐색을 한 번 수행할 때마다 삽입이 될 수 있는 가능성이 있는 노드가 반으로 줄기 때문이다.
하지만 그림2와 같은 최악의 경우 O(N)이 될 수 있다.
삭제
삭제 연산 또한 마찬가지이다. 기본적으로 O(logN)의 시간 복잡도를 가진다. 탐색을 한 번 수행할 때마다 삭제가 되어야 하는 노드의 후보군이 반으로 줄기 때문이다.
이 또한 그림2와 같은 최악의 경우 O(N)이 될 수 있다.
정리
Binary Search Tree는 이름 그대로 탐색(Search)을 매우 효율적으로 수행할 수 있는 탐색을 위한 Tree이다. 한 번 탐색을 수행할 때마다 후보군이 반으로 줄기 때문에 탐색에 O(logN)의 시간 복잡도를 가진다. 하지만 한쪽으로 쏠릴 위험성이 존재하며, 한쪽으로 쏠릴 시 탐색에 O(N)의 시간 복잡도를 가질 수 있다.
이를 해결하기 위해 Kotlin, Java에서는 한쪽으로 노드들이 치우치지 않도록 재구성(Restructuring)을 지속적으로 수행하는 작업을 하는 Red Black Tree 등을 사용하여, 아무리 많은 노드가 추가되더라도 탐색 성능을 O(logN) 으로 유지한다.
