이미지 로딩 중...
AI Generated
2025. 11. 7. · 3 Views
BST 탐색과 최소/최대값 찾기 완벽 가이드
이진 탐색 트리(BST)에서 효율적으로 값을 찾고, 최소값과 최대값을 구하는 방법을 배웁니다. 트리의 특성을 활용한 O(log n) 시간복잡도의 탐색 알고리즘을 실무 예제와 함께 학습합니다.
목차
1. BST_기본_구조와_노드_정의
시작하며
여러분이 데이터베이스에서 특정 값을 찾아야 할 때, 배열을 처음부터 끝까지 검색하면 너무 오래 걸린다는 것을 느낀 적이 있나요? 만약 백만 개의 데이터가 있다면, 최악의 경우 백만 번의 비교가 필요합니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 특히 실시간으로 검색 결과를 보여줘야 하는 애플리케이션이나, 대량의 데이터를 다루는 시스템에서는 치명적인 성능 저하를 일으킵니다.
바로 이럴 때 필요한 것이 이진 탐색 트리(Binary Search Tree, BST)입니다. BST는 데이터를 특별한 규칙으로 정렬하여 저장함으로써, 탐색 시간을 획기적으로 줄여줍니다.
백만 개의 데이터에서도 약 20번의 비교만으로 원하는 값을 찾을 수 있습니다.
개요
간단히 말해서, BST는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 트리 구조입니다. 왜 이 구조가 필요한지 실무 관점에서 보면, 데이터 검색, 삽입, 삭제 연산을 모두 O(log n) 시간에 처리할 수 있기 때문입니다.
예를 들어, 사용자 정보를 ID로 검색하거나, 상품 가격 범위를 조회하거나, 순위 시스템을 구현할 때 매우 유용합니다. 기존에는 배열이나 연결 리스트에서 순차적으로 검색했다면, 이제는 BST를 사용하여 절반씩 탐색 범위를 줄여가며 빠르게 찾을 수 있습니다.
BST의 핵심 특징은 첫째, 정렬된 순서를 유지한다는 점, 둘째, 각 비교마다 탐색 범위가 절반으로 줄어든다는 점, 셋째, 재귀적 구조로 코드가 간결하다는 점입니다. 이러한 특징들이 알고리즘 문제뿐만 아니라 실제 시스템 설계에서도 중요한 역할을 합니다.
코드 예제
// BST 노드 클래스 정의
class Node {
constructor(value) {
this.value = value; // 노드에 저장될 값
this.left = null; // 왼쪽 자식 노드 (작은 값들)
this.right = null; // 오른쪽 자식 노드 (큰 값들)
}
}
// BST 클래스 정의
class BinarySearchTree {
constructor() {
this.root = null; // 트리의 루트 노드
}
}
설명
이것이 하는 일: BST의 기본 구조는 노드(Node)와 트리(Tree) 두 가지 클래스로 구성됩니다. 각 노드는 값과 두 개의 자식 포인터를 가지며, 트리는 루트 노드를 관리합니다.
첫 번째로, Node 클래스는 트리의 각 노드를 표현합니다. constructor에서 value를 받아 저장하고, left와 right 포인터를 null로 초기화합니다.
이 포인터들이 나중에 자식 노드를 가리키게 되며, null이면 자식이 없다는 의미입니다. 두 번째로, BinarySearchTree 클래스가 실행되면서 root 프로퍼티를 null로 초기화합니다.
처음에는 트리가 비어있으므로 루트가 없습니다. 노드를 삽입하면 첫 번째 노드가 루트가 되고, 이후 노드들은 BST 규칙에 따라 적절한 위치에 배치됩니다.
BST의 핵심 규칙은 간단합니다. 어떤 노드 N에 대해, N의 왼쪽 서브트리의 모든 노드는 N보다 작은 값을, 오른쪽 서브트리의 모든 노드는 N보다 큰 값을 가집니다.
이 규칙이 재귀적으로 모든 노드에 적용되어 트리 전체가 정렬된 상태를 유지합니다. 여러분이 이 구조를 사용하면 데이터를 정렬된 상태로 유지하면서도 빠른 검색이 가능합니다.
배열처럼 인덱스 접근은 안 되지만, 대신 동적으로 데이터를 추가하고 삭제하면서도 효율적인 검색을 보장받을 수 있습니다. 또한 트리 순회를 통해 정렬된 순서로 데이터를 출력하는 것도 간단합니다.
실전 팁
💡 Node 클래스를 정의할 때 value의 타입을 명확히 하세요. 숫자만 저장할지, 객체도 저장할지에 따라 비교 로직이 달라집니다.
💡 실무에서는 중복 값 처리 정책을 미리 정해야 합니다. 중복을 허용할지, 왼쪽에 둘지 오른쪽에 둘지, 아예 거부할지 결정하세요.
💡 메모리 누수를 방지하려면 노드 삭제 시 자식 포인터를 명시적으로 null로 설정하는 습관을 들이세요.
💡 큰 데이터셋을 다룬다면 노드에 추가 정보(높이, 서브트리 크기 등)를 저장하여 균형 잡힌 트리를 유지하는 것을 고려하세요.
2. BST에서_값_탐색하기
시작하며
여러분이 전화번호부에서 특정 사람의 번호를 찾을 때, 가나다 순으로 정렬되어 있다면 중간을 펼쳐서 앞쪽인지 뒤쪽인지 판단하고 다시 절반을 펼치죠? BST 탐색도 정확히 같은 원리입니다.
이 탐색 방법은 실제 개발 현장에서 사용자 인증, 캐시 검색, 설정 값 조회 등 수많은 곳에서 활용됩니다. 단순한 배열 검색보다 10배, 100배 빠른 성능을 제공합니다.
바로 이럴 때 필요한 것이 BST 탐색 알고리즘입니다. 트리의 정렬 속성을 활용하여 매 단계마다 탐색 범위를 절반으로 줄여나갑니다.
개요
간단히 말해서, BST 탐색은 루트부터 시작해서 찾는 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동하며 목표 값을 찾는 알고리즘입니다. 왜 이 방법이 효율적인지 보면, 각 비교마다 남은 노드의 절반을 탐색 대상에서 제외할 수 있기 때문입니다.
예를 들어, 1000개의 노드가 있는 트리에서도 최대 10번의 비교면 충분합니다(2^10 = 1024). 순차 탐색이라면 최악의 경우 1000번이 필요합니다.
기존에는 배열을 처음부터 순회하며 일일이 비교했다면, 이제는 BST를 사용하여 로그 시간에 찾을 수 있습니다. 이 알고리즘의 핵심 특징은 첫째, 재귀나 반복문으로 간단히 구현할 수 있다는 점, 둘째, 평균 O(log n) 시간복잡도를 가진다는 점, 셋째, 트리가 균형 잡혀있을수록 성능이 좋다는 점입니다.
이러한 특징들이 실시간 검색 기능을 구현할 때 매우 중요합니다.
코드 예제
// BST에서 값을 탐색하는 메서드
search(value) {
return this.searchNode(this.root, value);
}
// 재귀적으로 노드를 탐색하는 헬퍼 메서드
searchNode(node, value) {
// 노드가 null이면 값을 찾지 못함
if (node === null) return false;
// 찾는 값이 현재 노드보다 작으면 왼쪽 탐색
if (value < node.value) {
return this.searchNode(node.left, value);
}
// 찾는 값이 현재 노드보다 크면 오른쪽 탐색
else if (value > node.value) {
return this.searchNode(node.right, value);
}
// 값을 찾음
else {
return true;
}
}
설명
이것이 하는 일: BST 탐색 알고리즘은 트리의 정렬 속성을 활용하여 효율적으로 값의 존재 여부를 확인합니다. 재귀적 접근으로 코드가 매우 간결하고 이해하기 쉽습니다.
첫 번째로, search 메서드는 외부 인터페이스 역할을 합니다. 사용자는 단순히 값만 전달하면 되고, 내부적으로 루트 노드와 함께 searchNode 헬퍼 메서드를 호출합니다.
이렇게 분리하면 사용자는 트리의 내부 구조를 알 필요가 없습니다. 두 번째로, searchNode 메서드가 실행되면서 먼저 베이스 케이스를 확인합니다.
node가 null이면 더 이상 탐색할 곳이 없으므로 false를 반환합니다. 이는 값이 트리에 존재하지 않는다는 의미입니다.
세 번째로, 값을 비교하는 로직이 실행됩니다. value가 node.value보다 작으면 왼쪽 서브트리로 재귀 호출하고, 크면 오른쪽 서브트리로 재귀 호출합니다.
같으면 값을 찾은 것이므로 true를 반환합니다. 이 과정이 재귀적으로 반복되며 탐색 범위가 절반씩 줄어듭니다.
마지막으로, 재귀 호출이 스택에 쌓였다가 값을 찾거나 null에 도달하면 결과가 역순으로 반환됩니다. 각 단계의 결과가 상위 호출로 전달되어 최종적으로 search 메서드의 호출자에게 boolean 결과가 반환됩니다.
여러분이 이 코드를 사용하면 대량의 데이터에서도 빠르게 값의 존재를 확인할 수 있습니다. 예를 들어, 사용자 ID 중복 체크, 권한 확인, 설정 값 조회 등에서 즉각적인 응답을 제공할 수 있습니다.
또한 재귀 구조 덕분에 코드가 직관적이어서 유지보수도 쉽습니다.
실전 팁
💡 반복문 버전도 구현해보세요. 재귀는 깊은 트리에서 스택 오버플로우 위험이 있지만, 반복문은 안전합니다.
💡 값이 아닌 노드 자체를 반환하도록 수정하면, 찾은 노드의 다른 정보도 활용할 수 있어 더 유용합니다.
💡 탐색 경로를 배열에 저장하면 디버깅이나 시각화에 활용할 수 있습니다. 예: [50, 30, 40] 경로로 40을 찾았다.
💡 성능 측정을 위해 비교 횟수를 카운터로 세어보세요. 트리가 얼마나 균형 잡혀있는지 판단할 수 있습니다.
💡 실무에서는 대소문자 구분, 문자열 비교 등 데이터 타입에 맞는 비교 함수를 별도로 정의하여 사용하세요.
3. BST_최소값_찾기
시작하며
여러분이 전체 데이터 중에서 가장 작은 값, 즉 최솟값을 찾아야 하는 상황을 생각해보세요. 배열이라면 모든 요소를 확인해야 하지만, BST에서는 단 하나의 규칙만 따르면 됩니다.
이 문제는 실제 개발 현장에서 순위 시스템의 최저 점수, 가격 범위의 최저가, 시간순 정렬의 가장 오래된 기록 등을 찾을 때 반복적으로 등장합니다. 바로 이럴 때 필요한 것이 BST 최소값 탐색입니다.
BST의 왼쪽 자식은 항상 부모보다 작다는 특성을 활용하여, 계속 왼쪽으로만 이동하면 최솟값을 찾을 수 있습니다.
개요
간단히 말해서, BST의 최소값은 루트에서 시작해서 왼쪽 자식이 없을 때까지 계속 왼쪽으로 이동한 노드의 값입니다. 왜 이 방법이 작동하는지 보면, BST의 정의상 왼쪽 서브트리의 모든 값이 부모보다 작기 때문입니다.
예를 들어, 온라인 쇼핑몰에서 가격순으로 정렬된 상품 트리가 있다면, 가장 저렴한 상품은 항상 최좌측 노드에 위치합니다. 기존에는 모든 노드를 방문하여 비교했다면, 이제는 트리의 높이만큼만 이동하면 됩니다.
이 알고리즘의 핵심 특징은 첫째, 단순히 왼쪽으로만 이동한다는 직관적인 로직, 둘째, O(h) 시간복잡도(h는 트리 높이)로 균형 트리에서는 O(log n), 셋째, 반복문이나 재귀 모두 쉽게 구현 가능하다는 점입니다. 이러한 특징들이 실시간 순위 조회 시스템에서 매우 효율적입니다.
코드 예제
// BST에서 최소값을 찾는 메서드
findMin() {
if (this.root === null) {
return null; // 빈 트리인 경우
}
return this.findMinNode(this.root).value;
}
// 주어진 노드의 서브트리에서 최소값 노드를 찾는 헬퍼 메서드
findMinNode(node) {
// 왼쪽 자식이 없을 때까지 계속 왼쪽으로 이동
while (node.left !== null) {
node = node.left;
}
// 가장 왼쪽 노드가 최소값
return node;
}
설명
이것이 하는 일: BST 최소값 탐색은 트리의 왼쪽 끝 노드를 찾는 간단하지만 강력한 알고리즘입니다. 트리의 정렬 속성을 완벽히 활용하여 O(log n) 시간에 최솟값을 찾습니다.
첫 번째로, findMin 메서드는 트리가 비어있는지 확인합니다. root가 null이면 트리에 노드가 없으므로 null을 반환합니다.
이 에러 처리는 매우 중요합니다. 빈 트리에서 최솟값을 찾으려 할 때 런타임 에러를 방지합니다.
두 번째로, 트리가 비어있지 않으면 findMinNode 헬퍼 메서드를 호출합니다. 이 메서드는 주어진 노드를 시작점으로 하여 최소값 노드를 찾습니다.
while 루프를 사용하여 node.left가 null이 아닌 동안 계속 왼쪽으로 이동합니다. 세 번째로, 루프가 종료되는 시점은 node.left가 null일 때입니다.
이는 더 이상 작은 값이 없다는 의미이므로, 현재 node가 최소값을 가진 노드입니다. 이 노드를 반환하고, findMin 메서드에서 .value로 실제 값을 추출하여 반환합니다.
마지막으로, findMinNode가 노드 자체를 반환하는 이유는 다른 연산에서 재사용하기 위함입니다. 예를 들어, 노드 삭제 연산에서 후계자를 찾을 때 이 메서드를 활용할 수 있습니다.
여러분이 이 코드를 사용하면 순위 시스템에서 최하위 점수를 즉시 조회하거나, 이벤트 큐에서 가장 오래된 이벤트를 찾거나, 가격 필터링에서 최저가를 표시하는 등의 기능을 효율적으로 구현할 수 있습니다. 또한 중위 순회의 시작점을 찾는 등 다른 트리 알고리즘의 빌딩 블록으로도 활용됩니다.
실전 팁
💡 findMinNode를 public으로 노출하면 서브트리의 최솟값도 찾을 수 있어 유연성이 높아집니다.
💡 재귀 버전도 간단합니다: if (!node.left) return node; return findMinNode(node.left); 하지만 반복문이 더 효율적입니다.
💡 빈 트리 처리 대신 예외를 던지는 방식도 고려해보세요. 상황에 따라 null 반환보다 명시적 에러가 나을 수 있습니다.
💡 최소값 탐색 경로를 스택에 저장하면, 최솟값 삭제 후 트리 재구성이 더 쉬워집니다.
💡 성능 최적화를 위해 루트에 최소값 캐시를 저장하고, 삽입/삭제 시 업데이트하는 방법도 있습니다. 조회가 매우 빈번하다면 유용합니다.
4. BST_최대값_찾기
시작하며
여러분이 게임 리더보드에서 최고 점수를 표시해야 하거나, 재고 관리 시스템에서 가장 비싼 상품을 찾아야 한다면 어떻게 하시겠어요? BST에서는 최소값 찾기와 정확히 반대 방향으로 이동하면 됩니다.
이 문제는 실제 개발 현장에서 최고 기록 조회, 최대 용량 확인, 최신 타임스탬프 찾기 등 다양한 상황에서 필요합니다. 바로 이럴 때 필요한 것이 BST 최대값 탐색입니다.
BST의 오른쪽 자식은 항상 부모보다 크다는 특성을 활용하여, 계속 오른쪽으로만 이동하면 최댓값을 찾을 수 있습니다.
개요
간단히 말해서, BST의 최대값은 루트에서 시작해서 오른쪽 자식이 없을 때까지 계속 오른쪽으로 이동한 노드의 값입니다. 왜 이 방법이 효과적인지 보면, BST의 정의상 오른쪽 서브트리의 모든 값이 부모보다 크기 때문입니다.
예를 들어, 사용자 활동 로그를 타임스탬프 기준으로 BST에 저장했다면, 가장 최근 활동은 항상 최우측 노드에 위치합니다. 기존에는 전체 데이터를 스캔하여 최댓값을 찾았다면, 이제는 트리의 오른쪽 경로만 따라가면 됩니다.
이 알고리즘의 핵심 특징은 첫째, 최소값 찾기와 대칭적이어서 이해하기 쉽다는 점, 둘째, O(h) 시간복잡도로 매우 빠르다는 점, 셋째, 코드가 간결하여 버그 가능성이 낮다는 점입니다. 이러한 특징들이 대시보드나 통계 화면에서 실시간 최댓값을 보여줄 때 매우 유용합니다.
코드 예제
// BST에서 최대값을 찾는 메서드
findMax() {
if (this.root === null) {
return null; // 빈 트리인 경우
}
return this.findMaxNode(this.root).value;
}
// 주어진 노드의 서브트리에서 최대값 노드를 찾는 헬퍼 메서드
findMaxNode(node) {
// 오른쪽 자식이 없을 때까지 계속 오른쪽으로 이동
while (node.right !== null) {
node = node.right;
}
// 가장 오른쪽 노드가 최대값
return node;
}
설명
이것이 하는 일: BST 최대값 탐색은 트리의 오른쪽 끝 노드를 찾는 알고리즘으로, 최소값 찾기와 완벽히 대칭적인 구조를 가집니다. 트리의 정렬 속성을 활용하여 효율적으로 최댓값을 찾습니다.
첫 번째로, findMax 메서드는 트리가 비어있는지 체크합니다. root가 null이면 최댓값을 찾을 수 없으므로 null을 반환합니다.
이런 방어적 프로그래밍은 프로덕션 코드에서 필수적입니다. 두 번째로, 트리에 노드가 있으면 findMaxNode 헬퍼 메서드를 호출합니다.
이 메서드는 시작 노드부터 오른쪽 자식을 따라 이동합니다. while 루프는 node.right가 null이 아닌 동안 계속 오른쪽으로 진행하며, 각 단계마다 더 큰 값으로 이동합니다.
세 번째로, 루프가 멈추는 순간은 node.right가 null일 때입니다. 이는 더 이상 큰 값이 없다는 의미이므로, 현재 node가 서브트리에서 가장 큰 값을 가집니다.
이 노드를 반환하면 findMax에서 .value로 실제 값을 추출합니다. 네 번째로, findMaxNode가 노드 객체를 반환하는 설계는 재사용성을 고려한 것입니다.
노드 삭제 연산에서 선행자(predecessor)를 찾을 때, 왼쪽 서브트리의 최댓값이 필요한데 이 메서드를 그대로 사용할 수 있습니다. 여러분이 이 코드를 사용하면 게임에서 최고 점수를 즉시 표시하거나, 센서 데이터에서 최대 측정값을 찾거나, 경매 시스템에서 최고가를 확인하는 등의 기능을 빠르게 구현할 수 있습니다.
또한 범위 쿼리(range query)에서 상한값을 찾는 등 복잡한 검색 기능의 기초로도 활용됩니다.
실전 팁
💡 최소값과 최대값을 함께 반환하는 findMinMax() 메서드를 만들면 범위 통계에 유용합니다.
💡 트리 높이가 매우 깊다면 꼬리 재귀 최적화를 적용한 재귀 버전을 고려해보세요. 일부 엔진에서 최적화됩니다.
💡 최댓값을 자주 조회한다면 루트에 캐시하고 O(1)로 조회하세요. 단, 삽입/삭제 시 캐시 업데이트를 잊지 마세요.
💡 노드에 부모 포인터가 있다면 최댓값부터 역순으로 순회하는 reverse iterator를 쉽게 구현할 수 있습니다.
💡 분산 시스템에서는 최댓값 노드에 락(lock)을 걸어 동시성 문제를 방지해야 합니다. 여러 스레드가 동시에 최댓값을 수정할 수 있기 때문입니다.
5. BST_삽입_연산
시작하며
여러분이 새로운 데이터를 추가하면서도 정렬 상태를 유지해야 하는 상황을 떠올려보세요. 배열이라면 정렬된 위치를 찾아 요소들을 이동시켜야 하지만, BST는 훨씬 효율적입니다.
이 문제는 실제 개발 현장에서 실시간 데이터 스트림 처리, 동적 순위 시스템, 우선순위 큐 구현 등에서 끊임없이 발생합니다. 데이터를 추가할 때마다 전체를 재정렬하면 성능이 급격히 저하됩니다.
바로 이럴 때 필요한 것이 BST 삽입 연산입니다. 새 값을 적절한 위치에 삽입하면서도 BST의 정렬 속성을 유지하며, O(log n) 시간에 완료됩니다.
개요
간단히 말해서, BST 삽입은 루트부터 시작해서 새 값과 현재 노드를 비교하며 왼쪽 또는 오른쪽으로 이동하다가, null 위치를 찾으면 그곳에 새 노드를 추가하는 연산입니다. 왜 이 연산이 중요한지 보면, 정렬을 유지하면서도 O(log n) 시간에 삽입할 수 있기 때문입니다.
예를 들어, 실시간 채팅 애플리케이션에서 메시지를 타임스탬프 순으로 저장하면서도 빠르게 조회할 수 있습니다. 기존에는 배열에 삽입 후 정렬하거나, 삽입 정렬로 O(n) 시간이 걸렸다면, 이제는 BST로 로그 시간에 처리할 수 있습니다.
이 연산의 핵심 특징은 첫째, 재귀나 반복으로 구현 가능하다는 점, 둘째, 트리 구조를 자동으로 유지한다는 점, 셋째, 중복 처리 정책을 유연하게 설정할 수 있다는 점입니다. 이러한 특징들이 동적으로 변하는 데이터셋을 다룰 때 매우 강력합니다.
코드 예제
// BST에 새 값을 삽입하는 메서드
insert(value) {
const newNode = new Node(value);
// 트리가 비어있으면 루트로 설정
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
// 재귀적으로 올바른 위치에 노드를 삽입하는 헬퍼 메서드
insertNode(node, newNode) {
// 새 값이 현재 노드보다 작으면 왼쪽으로
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode; // 왼쪽이 비어있으면 삽입
} else {
this.insertNode(node.left, newNode); // 왼쪽 서브트리로 재귀
}
}
// 새 값이 현재 노드보다 크거나 같으면 오른쪽으로
else {
if (node.right === null) {
node.right = newNode; // 오른쪽이 비어있으면 삽입
} else {
this.insertNode(node.right, newNode); // 오른쪽 서브트리로 재귀
}
}
}
설명
이것이 하는 일: BST 삽입 연산은 새로운 값을 트리의 적절한 위치에 추가하면서 BST의 정렬 속성을 유지하는 핵심 연산입니다. 재귀적 접근으로 코드가 간결하면서도 강력합니다.
첫 번째로, insert 메서드는 새 노드를 생성합니다. 먼저 트리가 비어있는지 확인하여, root가 null이면 새 노드를 루트로 설정합니다.
이는 첫 번째 노드를 삽입하는 특별한 케이스를 처리합니다. 두 번째로, 트리에 이미 노드가 있으면 insertNode 헬퍼 메서드를 호출합니다.
이 메서드는 newNode의 값을 현재 node의 값과 비교합니다. 작으면 왼쪽 서브트리로, 크거나 같으면 오른쪽 서브트리로 진행합니다.
여기서 "크거나 같으면"은 중복 값을 오른쪽에 배치하는 정책입니다. 세 번째로, 이동하려는 방향의 자식이 null인지 확인합니다.
null이면 그 위치가 새 노드가 들어갈 자리이므로 newNode를 연결하고 종료합니다. null이 아니면 해당 자식 노드로 재귀 호출하여 더 깊이 탐색합니다.
네 번째로, 재귀가 진행되면서 스택에 쌓인 함수 호출들은 삽입이 완료되면 역순으로 반환됩니다. 하지만 실제로 반환값은 사용하지 않습니다.
단순히 적절한 위치를 찾아 포인터를 연결하는 것이 목적이기 때문입니다. 여러분이 이 코드를 사용하면 실시간으로 데이터를 추가하면서도 언제나 정렬된 상태를 유지할 수 있습니다.
예를 들어, 주식 거래 시스템에서 새로운 주문을 가격순으로 관리하거나, 게임 서버에서 플레이어를 점수순으로 저장하거나, 로그 시스템에서 이벤트를 시간순으로 기록하는 등의 작업을 효율적으로 수행할 수 있습니다.
실전 팁
💡 중복 값 처리는 요구사항에 따라 달라집니다. 중복을 거부하려면 if (newNode.value === node.value) return; 을 추가하세요.
💡 반복문 버전이 재귀보다 메모리 효율적입니다. while 루프로 부모를 추적하며 삽입 위치를 찾으세요.
💡 삽입 후 트리 높이가 너무 깊어지면 AVL이나 Red-Black 트리로 자동 균형을 맞추는 것을 고려하세요.
💡 대량 삽입 시에는 값들을 정렬한 후 중간값부터 삽입하면 균형 잡힌 트리를 만들 수 있습니다.
💡 삽입 시 경로를 배열에 저장하면, 나중에 부모 노드를 찾거나 트리를 재구성할 때 유용합니다.
6. BST_삭제_연산
시작하며
여러분이 데이터를 제거하면서도 트리 구조를 유지해야 하는 상황은 어떨까요? 삭제는 삽입보다 훨씬 복잡합니다.
왜냐하면 삭제된 노드의 자리를 채우는 방법이 세 가지 경우로 나뉘기 때문입니다. 이 문제는 실제 개발 현장에서 사용자 계정 삭제, 만료된 세션 제거, 오래된 캐시 항목 삭제 등에서 필수적입니다.
잘못 삭제하면 트리 구조가 깨져서 이후 모든 연산이 실패할 수 있습니다. 바로 이럴 때 필요한 것이 BST 삭제 연산입니다.
삭제할 노드의 자식 개수에 따라 세 가지 케이스를 처리하며, 트리의 BST 속성을 완벽히 유지합니다.
개요
간단히 말해서, BST 삭제는 세 가지 경우를 다룹니다: (1) 자식이 없는 리프 노드는 그냥 제거, (2) 자식이 하나면 그 자식을 부모에 연결, (3) 자식이 둘이면 후계자(오른쪽 서브트리의 최솟값)를 찾아 값을 교체 후 후계자를 삭제합니다. 왜 이렇게 복잡한지 보면, 노드를 삭제한 후에도 BST의 정렬 속성이 유지되어야 하기 때문입니다.
예를 들어, 루트 노드를 삭제할 때 단순히 제거하면 트리가 두 개로 분리되므로, 적절한 후계자를 찾아 루트 자리를 채워야 합니다. 기존에는 노드를 삭제한 후 전체 트리를 재구성했다면, 이제는 로컬 변경만으로 O(log n) 시간에 처리할 수 있습니다.
이 연산의 핵심 특징은 첫째, 세 가지 케이스를 정확히 구분해야 한다는 점, 둘째, 후계자 찾기에 findMinNode를 재사용할 수 있다는 점, 셋째, 재귀적 구현이 가장 깔끔하다는 점입니다. 이러한 특징들이 복잡한 데이터 구조를 안전하게 관리할 수 있게 해줍니다.
코드 예제
// BST에서 값을 삭제하는 메서드
remove(value) {
this.root = this.removeNode(this.root, value);
}
// 재귀적으로 노드를 삭제하는 헬퍼 메서드
removeNode(node, value) {
if (node === null) return null;
// 삭제할 값을 찾아 이동
if (value < node.value) {
node.left = this.removeNode(node.left, value);
} else if (value > node.value) {
node.right = this.removeNode(node.right, value);
} else {
// 값을 찾음 - 세 가지 케이스 처리
// 케이스 1: 자식이 없는 리프 노드
if (node.left === null && node.right === null) {
return null;
}
// 케이스 2: 자식이 하나만 있는 경우
if (node.left === null) return node.right;
if (node.right === null) return node.left;
// 케이스 3: 자식이 둘 다 있는 경우
// 오른쪽 서브트리의 최솟값(후계자)을 찾음
const successor = this.findMinNode(node.right);
node.value = successor.value; // 값을 후계자로 교체
node.right = this.removeNode(node.right, successor.value);
}
return node;
}
설명
이것이 하는 일: BST 삭제 연산은 노드를 제거하면서도 트리의 정렬 속성을 유지하는 가장 복잡한 BST 연산입니다. 재귀적으로 구현하면 각 케이스를 명확하게 처리할 수 있습니다.
첫 번째로, remove 메서드는 루트부터 시작하여 removeNode를 호출합니다. removeNode는 수정된 서브트리의 새로운 루트를 반환하므로, 이를 다시 this.root에 할당하여 트리를 업데이트합니다.
이 패턴이 재귀 전체에서 일관되게 적용됩니다. 두 번째로, removeNode는 먼저 삭제할 값을 찾아 이동합니다.
value가 node.value보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 재귀 호출합니다. 이 과정은 탐색과 동일합니다.
세 번째로, 값을 찾으면(value === node.value) 세 가지 케이스를 처리합니다. 케이스 1은 자식이 없는 경우로, null을 반환하여 부모의 포인터가 null을 가리키게 합니다.
케이스 2는 자식이 하나인 경우로, 유일한 자식을 반환하여 부모가 직접 손자를 가리키게 합니다. 네 번째로, 케이스 3은 자식이 둘인 가장 복잡한 경우입니다.
이때는 오른쪽 서브트리에서 최솟값(후계자)을 찾습니다. 후계자는 현재 노드보다 크면서도 가장 작은 값이므로, 이 값으로 교체해도 BST 속성이 유지됩니다.
값을 교체한 후, 오른쪽 서브트리에서 후계자를 삭제하는 재귀 호출을 합니다. 마지막으로, 각 재귀 단계에서 수정된 node를 반환합니다.
이 반환값이 상위 재귀의 node.left나 node.right에 할당되면서 트리가 재구성됩니다. 여러분이 이 코드를 사용하면 데이터를 안전하게 삭제하면서도 트리 구조를 유지할 수 있습니다.
예를 들어, 세션 관리에서 만료된 세션을 제거하거나, 작업 큐에서 완료된 작업을 삭제하거나, 인벤토리 시스템에서 품절된 상품을 제거하는 등의 작업을 안정적으로 수행할 수 있습니다.
실전 팁
💡 후계자 대신 선행자(왼쪽 서브트리의 최댓값)를 사용해도 됩니다. 번갈아 사용하면 트리 균형이 더 잘 유지됩니다.
💡 삭제 후 트리 높이가 불균형해질 수 있습니다. 삭제 빈도가 높다면 자가 균형 트리(AVL, Red-Black)를 고려하세요.
💡 실무에서는 실제 삭제 대신 "삭제 표시"(soft delete)를 사용하는 경우가 많습니다. 노드에 isDeleted 플래그를 추가하세요.
💡 부모 포인터를 유지한다면 반복문으로 더 효율적으로 구현할 수 있습니다. 재귀 없이 O(h) 시간에 처리됩니다.
💡 삭제 연산을 로깅하면 디버깅과 감사(audit)에 유용합니다. 어떤 케이스가 처리되었는지 기록하세요.
7. BST_중위_순회
시작하며
여러분이 트리에 저장된 모든 데이터를 정렬된 순서로 출력해야 한다면 어떻게 하시겠어요? 배열이라면 정렬 알고리즘을 실행해야 하지만, BST는 이미 정렬되어 있으므로 순회만 하면 됩니다.
이 문제는 실제 개발 현장에서 데이터 익스포트, 보고서 생성, 디버깅 출력, API 응답 생성 등에서 매우 자주 발생합니다. 사용자에게 정렬된 목록을 보여주는 것은 기본적인 요구사항입니다.
바로 이럴 때 필요한 것이 BST 중위 순회(In-order Traversal)입니다. 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 방문하면, 자동으로 오름차순 정렬된 결과를 얻을 수 있습니다.
개요
간단히 말해서, 중위 순회는 재귀적으로 왼쪽 자식을 먼저 방문하고, 그 다음 현재 노드를 처리한 후, 마지막으로 오른쪽 자식을 방문하는 트리 순회 방법입니다. 왜 이 방법이 정렬된 결과를 만드는지 보면, BST의 정의상 왼쪽 < 현재 < 오른쪽 순서이기 때문입니다.
예를 들어, 상품 데이터를 가격순 BST에 저장했다면, 중위 순회로 저렴한 것부터 비싼 순서로 출력됩니다. 기존에는 데이터를 추출한 후 정렬 알고리즘을 실행했다면, 이제는 순회만으로 O(n) 시간에 정렬된 결과를 얻을 수 있습니다.
이 순회의 핵심 특징은 첫째, 재귀로 매우 간결하게 구현된다는 점, 둘째, O(n) 시간복잡도로 모든 노드를 정확히 한 번씩 방문한다는 점, 셋째, 배열이나 콜백으로 결과를 수집할 수 있다는 점입니다. 이러한 특징들이 데이터 시각화나 리포팅에 매우 유용합니다.
코드 예제
// BST를 중위 순회하는 메서드 (오름차순 정렬 결과)
inOrderTraversal() {
const result = [];
this.inOrder(this.root, result);
return result;
}
// 재귀적으로 중위 순회하는 헬퍼 메서드
inOrder(node, result) {
if (node !== null) {
// 1. 왼쪽 서브트리 순회 (작은 값들)
this.inOrder(node.left, result);
// 2. 현재 노드 처리
result.push(node.value);
// 3. 오른쪽 서브트리 순회 (큰 값들)
this.inOrder(node.right, result);
}
}
설명
이것이 하는 일: BST 중위 순회는 트리의 모든 노드를 정렬된 순서로 방문하는 핵심 알고리즘입니다. 재귀의 특성을 완벽히 활용하여 코드가 매우 간결합니다.
첫 번째로, inOrderTraversal 메서드는 빈 result 배열을 생성하고 inOrder 헬퍼 메서드를 호출합니다. result를 참조로 전달하므로, 재귀 호출 전체에서 같은 배열에 값을 추가할 수 있습니다.
순회가 완료되면 정렬된 값들이 담긴 배열을 반환합니다. 두 번째로, inOrder 메서드는 현재 노드가 null인지 확인합니다.
null이면 베이스 케이스로 아무것도 하지 않고 반환합니다. 이는 리프 노드의 자식이나 빈 트리를 처리합니다.
세 번째로, 노드가 null이 아니면 세 단계를 순서대로 실행합니다. 첫째, node.left로 재귀 호출하여 왼쪽 서브트리의 모든 노드(현재 노드보다 작은 값들)를 먼저 result에 추가합니다.
이 재귀가 완전히 끝나야 다음 단계로 진행됩니다. 네 번째로, 왼쪽 서브트리 순회가 완료되면 현재 node.value를 result에 추가합니다.
이 시점에서 왼쪽의 모든 작은 값들은 이미 배열에 들어가 있으므로, 현재 값이 올바른 위치에 추가됩니다. 다섯 번째로, node.right로 재귀 호출하여 오른쪽 서브트리의 모든 노드(현재 노드보다 큰 값들)를 result에 추가합니다.
이렇게 왼쪽 → 현재 → 오른쪽 순서가 재귀적으로 모든 서브트리에 적용되어, 최종적으로 전체 트리가 오름차순으로 정렬됩니다. 여러분이 이 코드를 사용하면 트리에 저장된 데이터를 정렬된 형태로 쉽게 추출할 수 있습니다.
예를 들어, 사용자 목록을 이름순으로 표시하거나, 로그 이벤트를 시간순으로 출력하거나, 재고 목록을 가격순으로 정렬하는 등의 작업을 추가 정렬 없이 O(n) 시간에 수행할 수 있습니다.
실전 팁
💡 콜백 함수를 파라미터로 받으면 더 유연합니다. inOrder(node, callback) 형태로 각 노드에 원하는 작업을 적용하세요.
💡 전위 순회(pre-order)는 루트 → 왼쪽 → 오른쪽, 후위 순회(post-order)는 왼쪽 → 오른쪽 → 루트 순서입니다. 용도에 맞게 선택하세요.
💡 스택을 사용한 반복문 버전도 구현해보세요. 재귀보다 메모리 효율적이며 스택 오버플로우 위험이 없습니다.
💡 역순 정렬이 필요하면 오른쪽 → 현재 → 왼쪽 순서로 순회하면 됩니다. 내림차순 결과를 얻을 수 있습니다.
💡 제너레이터(generator) 함수로 구현하면 메모리를 절약하며 순회할 수 있습니다. 대용량 트리에서 유용합니다.
8. BST_균형_확인
시작하며
여러분이 BST를 사용하는 이유는 O(log n) 성능 때문이죠? 하지만 트리가 불균형해지면 최악의 경우 O(n)으로 퇴화할 수 있습니다.
마치 연결 리스트처럼 한쪽으로 치우친 트리가 되는 것입니다. 이 문제는 실제 개발 현장에서 정렬된 데이터를 순차적으로 삽입할 때 자주 발생합니다.
예를 들어, 1, 2, 3, 4, 5 순서로 삽입하면 오른쪽으로만 뻗은 트리가 만들어져 성능이 급격히 저하됩니다. 바로 이럴 때 필요한 것이 BST 균형 확인입니다.
트리의 높이 차이를 측정하여 재구성이 필요한지 판단하고, 필요하다면 AVL이나 Red-Black 트리로 전환을 고려할 수 있습니다.
개요
간단히 말해서, 균형 잡힌 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 트리입니다. 이를 확인하려면 각 서브트리의 높이를 재귀적으로 계산해야 합니다.
왜 균형이 중요한지 보면, 균형 잡힌 트리는 높이가 O(log n)으로 유지되어 모든 연산이 로그 시간에 완료되기 때문입니다. 예를 들어, 백만 개의 노드가 있어도 높이는 약 20 정도로, 최대 20번의 비교면 충분합니다.
기존에는 단순 BST를 사용하여 최악의 경우 성능 저하를 감수했다면, 이제는 균형을 확인하여 필요시 재구성하거나 자가 균형 트리를 사용할 수 있습니다. 이 확인의 핵심 특징은 첫째, 재귀로 높이를 계산한다는 점, 둘째, O(n) 시간에 모든 노드를 검사한다는 점, 셋째, 성능 모니터링 지표로 활용할 수 있다는 점입니다.
이러한 특징들이 트리의 건강 상태를 진단하는 데 매우 유용합니다.
코드 예제
// 트리의 높이를 계산하는 메서드
height(node = this.root) {
if (node === null) return 0;
const leftHeight = this.height(node.left);
const rightHeight = this.height(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
// 트리가 균형 잡혀있는지 확인하는 메서드
isBalanced(node = this.root) {
if (node === null) return true;
// 왼쪽과 오른쪽 서브트리의 높이 차이
const leftHeight = this.height(node.left);
const rightHeight = this.height(node.right);
const heightDiff = Math.abs(leftHeight - rightHeight);
// 높이 차이가 1 이하이고, 양쪽 서브트리도 균형 잡혀있어야 함
return heightDiff <= 1 &&
this.isBalanced(node.left) &&
this.isBalanced(node.right);
}
설명
이것이 하는 일: BST 균형 확인은 트리의 성능을 진단하는 중요한 도구입니다. 높이를 계산하고 균형 여부를 판단하여 최적화 필요성을 알려줍니다.
첫 번째로, height 메서드는 주어진 노드를 루트로 하는 서브트리의 높이를 계산합니다. 노드가 null이면 높이는 0입니다.
이는 베이스 케이스로, 빈 트리나 리프 노드의 자식을 처리합니다. 두 번째로, 노드가 있으면 왼쪽과 오른쪽 서브트리의 높이를 재귀적으로 계산합니다.
이 두 재귀 호출은 독립적이며, 각각 서브트리 전체를 탐색하여 높이를 반환합니다. Math.max로 둘 중 큰 값을 선택하고 +1을 하여 현재 노드를 포함한 높이를 계산합니다.
세 번째로, isBalanced 메서드는 균형 여부를 확인합니다. 먼저 null 노드는 균형 잡힌 것으로 간주합니다.
그런 다음 현재 노드의 왼쪽과 오른쪽 서브트리 높이를 구하고, 그 차이를 계산합니다. 네 번째로, 균형 조건을 검사합니다.
heightDiff가 1 이하여야 하고, 동시에 왼쪽과 오른쪽 서브트리도 각각 균형 잡혀있어야 합니다. 이 세 조건을 AND 연산으로 결합하여, 모두 true일 때만 전체 트리가 균형 잡힌 것입니다.
다섯 번째로, 재귀가 진행되면서 모든 노드에서 균형을 검사합니다. 하나라도 불균형 노드가 있으면 false가 전파되어 최종 결과가 false가 됩니다.
여러분이 이 코드를 사용하면 트리의 성능 상태를 모니터링할 수 있습니다. 예를 들어, 주기적으로 균형을 확인하여 불균형해지면 트리를 재구성하거나, 성능 지표로 로깅하거나, 사용자에게 경고를 표시하는 등의 작업을 수행할 수 있습니다.
또한 트리 구현이 올바른지 테스트하는 용도로도 활용됩니다.
실전 팁
💡 height 메서드가 O(n) 시간이므로, 빈번히 호출하면 비효율적입니다. 노드에 높이를 캐시하는 것을 고려하세요.
💡 균형 계수(balance factor = 왼쪽 높이 - 오른쪽 높이)를 -1, 0, 1로 유지하는 것이 AVL 트리의 핵심입니다.
💡 isBalanced를 최적화하려면 높이 계산과 균형 확인을 한 번의 순회로 처리하세요. 불필요한 재계산을 피할 수 있습니다.
💡 균형이 깨지는 패턴을 로깅하면 데이터 삽입 순서의 문제를 발견할 수 있습니다. 정렬된 데이터가 입력되는지 확인하세요.
💡 실무에서는 완벽한 균형(높이 차이 1)보다 느슨한 균형(높이 차이 2-3)을 허용하는 것이 삽입/삭제 비용을 줄여 전체 성능을 높일 수 있습니다.