이진 탐색 트리(BST)의 강력함과 활용

오늘 컴퓨터 과학 강의에서 새로운 자료구조인 '이진 탐색 트리(Binary Search Tree)'에 대해 배웠다. 이 자료구조가 얼마나 유용한지, 왜 필요한지 확실히 이해할 수 있었던 시간이었다.

1. 문제는 언제나 좋은 시작점이다.

교수님은 '활주로 예약 시스템'이라는 문제로 강의를 시작했다. 단일 활주로가 있는 공항에서 비행기 착륙 시간을 예약하는 시스템을 만들어야 하는데, 안전을 위해 모든 착륙 시간은 서로 k분(예: 3분) 이상 떨어져 있어야 한다. 이런 조건을 만족하는 시스템을 만들려면 어떤 자료구조가 필요할까?

2. 기존 자료구조들의 한계가 명확했다.

정렬되지 않은 배열은 검색에 O(n) 시간이 걸리고, 정렬된 배열은 검색은 빠르지만 삽입에 O(n) 시간이 걸린다. 연결 리스트는 삽입은 빠르지만 이진 검색을 할 수 없다. 힙(Heap)은 최소/최대값은 빠르게 찾을 수 있지만 k분 규칙을 검사하는 데 O(n) 시간이 필요하다. 모든 자료구조가 완벽하지 않았다.

3. 이진 탐색 트리는 이런 제약을 해결해주는 해답이었다.

무엇이 이진 탐색 트리를 특별하게 만드는가? 그것은 강력한 '불변성(invariant)'이다. 모든 노드 x에 대해, 왼쪽 서브트리의 모든 key는 x의 key보다 작거나 같고, 오른쪽 서브트리의 모든 key는 x의 key보다 크거나 같다. 이 단순한 규칙이 놀라운 효율성을 만든다.

4. 삽입 과정은 생각보다 단순했다.

현재 노드와 새 값을 비교해 왼쪽이나 오른쪽으로 이동하면서 적절한 위치를 찾는다. 우리의 활주로 예약 시스템에서는 이 과정에서 k분 규칙도 함께 검사할 수 있다. 예를 들어, 41, 46, 49, 79가 있는 트리에 42를 삽입하려고 할 때, 41과 너무 가깝기 때문에 삽입이 거부된다.

5. 속도는 트리의 높이에 비례한다.

탐색, 삽입, 삭제 모두 O(h) 시간이 걸린다. 최소값과 최대값을 찾는 것도 간단하다 - 왼쪽으로 계속 가면 최소값, 오른쪽으로 계속 가면 최대값이다. 이 모든 것이 트리의 높이에 비례하는 시간 안에 이루어진다.

6. 문제 요구사항이 변할 때도 대응할 수 있다.

갑자기 "시간 t 이전에 착륙 예정인 비행기가 몇 대인가?"라는 질문(rank(t))에 답해야 한다면 어떻게 해야 할까? 이진 탐색 트리는 '증강(augment)'이라는 기법으로 이런 변화에 적응할 수 있다. 각 노드에 '서브트리 크기'라는 추가 정보를 저장하면, 트리를 탐색하면서 이 값들을 활용해 rank(t)를 계산할 수 있다.

7. 하지만 현실의 문제는 여전히 남아있다.

트리가 균형잡히지 않으면 최악의 경우 높이가 O(n)이 될 수 있다. 만약 43, 46, 48, 49처럼 정렬된 순서로 삽입하면 트리는 연결 리스트처럼 한쪽으로 치우치게 된다. 그러면 모든 연산이 O(n) 시간이 걸리게 된다.

이론적으로는 이진 탐색 트리가 우리 문제를 해결할 수 있지만, 실제로 효율적이려면 트리가 균형을 유지해야 한다. 균형 잡힌 이진 탐색 트리가 있다면 높이가 O(log n)이 되고, 그때 비로소 모든 연산이 우리가 원하는 시간 복잡도를 가지게 된다.

결국 자료구조도 현실의 문제를 해결하기 위해 계속 발전하고 적응해야 한다. 완벽한 해결책은 없지만, 문제의 특성을 이해하고 적절한 도구를 선택하는 것이 중요하다. 이진 탐색 트리는 그 강력한 도구 중 하나임을 오늘 강의를 통해 배울 수 있었다.