트리 및 이진 탐색 트리(BST)

트리는 계층 구조를 표현하는 기본적인 자료 구조이다. 노드와 간선으로 구성되며, 최상위 노드를 루트 노드라고 부른다. 트리는 파일 시스템, 조직도, XML 문서 구조 등 다양한 분야에서 계층적 데이터를 표현하는 데 널리 사용된다.

이진 탐색 트리는 트리의 특별한 형태로, 각 노드가 최대 두 개의 자식 노드를 가지는 이진 트리에 추가적인 정렬 속성을 부여한 것이다. 이 속성 덕분에 데이터의 효율적인 탐색, 삽입, 삭제가 가능해진다. BST는 정렬된 데이터를 유지하면서도 배열보다 유연한 구조를 제공한다.

트리와 BST는 알고리즘과 소프트웨어 공학의 핵심 개념으로, 데이터베이스 인덱싱, 심볼 테이블, 우선순위 큐 등 여러 고급 자료 구조와 알고리즘의 기초를 이룬다. 특히 BST의 변형인 균형 이진 탐색 트리는 성능 저하를 방지하는 데 중요한 역할을 한다.

트리는 노드와 간선으로 구성된 계층적 자료 구조이다. 하나의 루트 노드에서 시작하여 각 노드는 0개 이상의 자식 노드를 가질 수 있으며, 사이클이 존재하지 않는다는 특징이 있다. 이는 그래프의 특수한 형태로 볼 수 있다. 트리는 데이터를 계층적으로 표현하고 저장하는 데 널리 사용된다.

트리를 설명하는 주요 용어는 다음과 같다.

트리는 구조와 제약 조건에 따라 여러 종류로 나뉜다. 가장 기본적인 분류는 이진 트리와 이진 탐색 트리이다. 이진 트리는 각 노드의 자식 노드가 최대 두 개인 트리이다. 이진 탐색 트리는 이진 트리의 일종으로, 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값들만, 오른쪽 서브트리에는 큰 값들만 존재하도록 구성된 트리이다. 이 외에도 균형 트리, 포화 이진 트리, 완전 이진 트리 등 다양한 특성을 가진 트리가 존재한다.

이진 탐색 트리는 이진 트리의 일종으로, 특정한 순서 속성을 만족하는 자료 구조이다. 모든 노드에 대해, 해당 노드의 왼쪽 서브트리에 있는 모든 노드의 키 값은 현재 노드의 키 값보다 작고, 오른쪽 서브트리에 있는 모든 노드의 키 값은 현재 노드의 키 값보다 크다는 규칙을 따른다. 이 규칙은 트리의 모든 노드에 대해 재귀적으로 적용된다.

이 핵심 속성 덕분에 이진 탐색과 유사한 방식으로 데이터를 효율적으로 탐색할 수 있다. 트리의 루트 노드부터 시작하여, 찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동하는 과정을 반복한다. 이 구조는 정렬된 데이터를 저장하고 검색하는 데 매우 적합하다.

BST의 주요 장점은 평균적인 경우 연결 리스트나 배열에 비해 빠른 탐색, 삽입, 삭제 연산을 제공한다는 점이다. 또한, 중위 순회를 수행하면 저장된 데이터를 정렬된 순서로 쉽게 얻을 수 있다. 그러나 이 장점은 트리가 균형을 유지할 때 최대화된다. 트리가 한쪽으로 치우치는 편향 트리가 되면 연산의 효율성이 선형 시간 복잡도로 떨어질 수 있다[1].

이진 탐색 트리의 기본 연산은 주로 세 가지로 구분된다. 각 연산은 트리의 핵심 속성인 "왼쪽 서브트리의 모든 노드 값 < 루트 노드 값 < 오른쪽 서브트리의 모든 노드 값"을 바탕으로 동작한다.

탐색(Search) 연산은 주어진 키 값을 가진 노드를 찾는다. 루트 노드에서 시작하여, 찾는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 재귀적으로 이동한다. 값이 일치하는 노드를 찾거나 더 이상 자식 노드가 없는 리프 노드에 도달할 때까지 이 과정을 반복한다. 탐색 경로는 트리의 높이에 비례한다.

삽입(Insertion) 연산은 새로운 노드를 적절한 위치에 추가하여 트리의 속성을 유지한다. 먼저 탐색 연산과 유사한 과정으로 새 노드가 위치해야 할 빈 자리(NULL 포인터)를 찾는다. 그 후, 해당 위치의 부모 노드 포인터를 이용해 새 노드를 연결한다. 삽입 연산은 항상 새로운 노드를 리프 노드로 추가하므로, 기존 노드들의 구조를 크게 변경하지 않는다.

삭제(Deletion) 연산은 세 가지 경우로 나누어 처리된다.

1. 삭제할 노드가 자식이 없는 경우(리프 노드): 해당 노드를 단순히 제거한다.

2. 삭제할 노드가 자식을 하나만 가진 경우: 해당 노드를 제거하고, 그 자식 노드를 부모 노드에 직접 연결한다.

3. 삭제할 노드가 두 개의 자식을 모두 가진 경우: 이는 가장 복잡한 경우이다. 일반적으로 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값(중위 순회 후속자)을 찾거나, 왼쪽 서브트리에서 가장 큰 값(중위 순회 선행자)을 찾아 그 값으로 삭제할 노드를 대체한다. 그 후, 대체에 사용된 노드(후속자 또는 선행자)를 원래 위치에서 제거하는데, 이 노드는 최대 하나의 자식만을 가지므로 경우 1 또는 2에 해당하게 된다. 이 방법으로 트리의 순서 속성을 보존한다.

이진 탐색 트리의 시간 복잡도는 트리의 구조, 즉 균형 상태에 크게 의존한다. 이상적인 균형 상태에서는 각 연산의 시간 복잡도가 트리 높이에 비례하여 O(log n)이다. 여기서 n은 트리에 저장된 노드의 총 개수를 의미한다. 이는 각 단계에서 탐색 범위가 절반으로 줄어들기 때문이다.

그러나 이진 탐색 트리에 데이터가 순차적으로 삽입되는 등의 이유로 트리가 편향될 경우, 최악의 시나리오가 발생한다. 예를 들어, 키가 1, 2, 3, ... 순으로 삽입되면 트리는 연결 리스트와 유사한 형태를 띠게 된다. 이 경우 트리의 높이는 n이 되며, 탐색, 삽입, 삭제 연산 모두 최악의 경우 O(n)의 시간이 소요된다.

다음 표는 균형 상태에 따른 이진 탐색 트리의 시간 복잡도를 요약한다.

이러한 최악의 경우를 방지하고 효율적인 O(log n)의 성능을 보장하기 위해 AVL 트리나 레드-블랙 트리와 같은 균형 이진 탐색 트리가 고안되었다. 이러한 자료구조는 삽입 및 삭제 연산 중에 추가적인 작업을 통해 트리의 균형을 자동으로 유지한다.

이진 탐색 트리는 데이터의 삽입 순서에 따라 트리의 구조가 편향될 수 있다. 이 경우 탐색, 삽입, 삭제 연산의 시간 복잡도가 최악의 경우 O(n)으로 저하될 수 있다. 이를 해결하기 위해 삽입과 삭제 시 트리의 균형을 자동으로 유지하는 균형 이진 탐색 트리가 개발되었다. 대표적인 균형 트리로는 AVL 트리와 레드-블랙 트리가 있다.

AVL 트리는 1962년 G. M. Adelson-Velsky와 Evgenii Landis가 제안한 최초의 균형 이진 탐색 트리이다. 이 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 인수)가 -1, 0, 1 중 하나가 되도록 유지한다. 균형이 깨지면 회전 연산(단일 회전, 이중 회전)을 통해 균형을 복구한다. AVL 트리는 엄격한 균형을 유지하여 탐색 성능이 매우 우수하지만, 삽입과 삭제 시 빈번한 회전 연산이 필요할 수 있다는 단점이 있다.

레드-블랙 트리는 각 노드에 레드 또는 블랙의 색상 속성을 부여하여 균형을 유지한다. 다음의 다섯 가지 규칙을 만족해야 한다[6]. AVL 트리보다 덜 엄격한 균형 조건을 가지므로 삽입과 삭제 시 필요한 회전 횟수가 상대적으로 적다. 이로 인해 많은 프로그래밍 언어의 표준 라이브러리(C++의 std::map, 자바의 TreeMap 등)에서 내부적으로 레드-블랙 트리를 구현에 사용한다.

이진 탐색 트리는 그 구조적 특성 덕분에 다양한 컴퓨터 과학 및 소프트웨어 공학 분야에서 폭넓게 응용된다. 가장 대표적인 응용은 데이터의 효율적인 정렬과 탐색이다. BST를 중위 순회(in-order traversal)하면 저장된 데이터를 정렬된 순서로 얻을 수 있어, 동적으로 데이터가 추가되거나 삭제되는 상황에서도 정렬 상태를 유지하는 데 유용하다. 또한, 데이터베이스 시스템의 인덱스 구조나 파일 시스템의 디렉토리 계층을 구현하는 데에도 활용된다.

보다 구체적인 응용 분야는 다음과 같다.

또한, 3D 그래픽스 및 게임 엔진에서 공간 분할을 위한 이진 공간 분할(BSP) 트리나, 데이터 압축에 쓰이는 허프만 코딩 트리도 이진 트리 구조를 기반으로 한다. 이러한 광범위한 응용은 BST가 제공하는 로그 시간 복잡도의 효율적인 연산과 데이터 간의 계층적 관계 표현 능력에서 비롯된다.

이진 탐색 트리의 구현은 재귀 또는 반복문을 사용하여 이루어진다. 핵심 연산인 탐색, 삽입, 삭제는 모두 트리의 루트 노드부터 시작하여 이진 탐색 원리에 따라 적절한 서브트리로 내려가며 수행된다.

다음은 C++를 사용한 간단한 이진 탐색 트리 클래스의 구현 예시이다. 이 예시는 정수 값을 저장하며, 각 노드는 Node 구조체로 표현된다.

```cpp

#include <iostream>

class BinarySearchTree {

private:

struct Node {

int data;

Node* left;

Node* right;

Node(int val) : data(val), left(nullptr), right(nullptr) {}

};

Node* root;

// 재귀적 삽입 보조 함수

Node* insertRec(Node* node, int value) {

if (node == nullptr) {

return new Node(value);

}

if (value < node->data) {

node->left = insertRec(node->left, value);

} else if (value > node->data) {

node->right = insertRec(node->right, value);

}

return node;

}

// 재귀적 탐색 보조 함수

bool searchRec(Node* node, int value) {

if (node == nullptr) return false;

if (node->data == value) return true;

if (value < node->data) return searchRec(node->left, value);

else return searchRec(node->right, value);

}

// 중위 순회 보조 함수 (오름차순 출력)

void inorderRec(Node* node) {

if (node == nullptr) return;

inorderRec(node->left);

std::cout << node->data << " ";

inorderRec(node->right);

}

// 최소값 노드 찾기 (삭제 연산에 사용)

Node* findMin(Node* node) {

while (node && node->left != nullptr) {

node = node->left;

}

return node;

}

// 재귀적 삭제 보조 함수

Node* deleteRec(Node* node, int value) {

if (node == nullptr) return node;

if (value < node->data) {

node->left = deleteRec(node->left, value);

} else if (value > node->data) {

node->right = deleteRec(node->right, value);

} else {

// 삭제할 노드를 찾은 경우

// 자식이 하나 또는 없는 경우

if (node->left == nullptr) {

Node* temp = node->right;

delete node;

return temp;

} else if (node->right == nullptr) {

Node* temp = node->left;

delete node;

return temp;

}

// 자식이 둘인 경우: 오른쪽 서브트리의 최소값 노드로 대체

Node* temp = findMin(node->right);

node->data = temp->data;

node->right = deleteRec(node->right, temp->data);

}

return node;

}

public:

BinarySearchTree() : root(nullptr) {}

void insert(int value) {

root = insertRec(root, value);

}

bool search(int value) {

return searchRec(root, value);

}

void remove(int value) {

root = deleteRec(root, value);

}

void display() {

inorderRec(root);

std::cout << std::endl;

}

};

// 사용 예시

int main() {

BinarySearchTree bst;

bst.insert(50);

bst.insert(30);

bst.insert(70);

bst.insert(20);

bst.insert(40);

std::cout << "트리 내용 (중위 순회): ";

bst.display(); // 20 30 40 50 70 출력

std::cout << "40 검색: " << (bst.search(40) ? "찾음" : "없음") << std::endl;

std::cout << "60 검색: " << (bst.search(60) ? "찾음" : "없음") << std::endl;

bst.remove(30);

std::cout << "30 삭제 후: ";

bst.display(); // 20 40 50 70 출력

return 0;

}

```

다른 프로그래밍 언어에서의 구현 방식도 유사하다. 파이썬에서는 클래스와 재귀를, 자바에서는 제네릭을 활용하여 일반화된 버전을 구현할 수 있다. 삭제 연산은 세 가지 경우(자식이 없음, 하나 있음, 둘 있음)를 정확히 처리하는 것이 핵심이다. 이 기본 구현은 균형 이진 탐색 트리가 아니므로, 입력 순서에 따라 성능이 저하될 수 있다는 점에 유의해야 한다.

• Wikipedia - 트리 (자료 구조)

• Wikipedia - 이진 탐색 트리

• GeeksforGeeks - Binary Search Tree

• 나무위키 - 이진 탐색 트리

• Khan Academy - Binary Search Tree

• Microsoft Learn - 이진 트리 및 이진 검색 트리

• Programiz - Binary Search Tree