이미지 로딩 중...
AI Generated
2025. 11. 7. · 3 Views
BST 기본 구조와 속성 완벽 가이드
Binary Search Tree의 핵심 개념부터 구현까지 초급 개발자를 위한 실무 중심 가이드입니다. 트리 구조의 기본부터 검색, 삽입, 삭제 연산까지 단계별로 알아봅니다. 실전 예제와 팁으로 BST를 완전히 이해할 수 있습니다.
목차
1. BST 기본 개념
시작하며
여러분이 대량의 데이터에서 특정 값을 빠르게 찾아야 할 때, 어떤 자료구조를 사용하시나요? 배열에서는 선형 탐색으로 O(n)의 시간이 걸리고, 정렬된 배열도 이진 탐색으로 O(log n)이 걸리지만 삽입과 삭제가 비효율적입니다.
이런 문제는 실무에서 사용자 데이터 관리, 파일 시스템, 데이터베이스 인덱싱 등에서 자주 발생합니다. 검색은 빠르지만 데이터 변경이 느리거나, 반대의 경우가 많죠.
바로 이럴 때 필요한 것이 Binary Search Tree(BST)입니다. BST는 검색, 삽입, 삭제 모두 평균적으로 O(log n)의 효율성을 제공합니다.
개요
간단히 말해서, BST는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 값을 갖는 트리 구조입니다. 이 구조가 필요한 이유는 데이터를 체계적으로 정리하면서도 동적인 변경에 유연하게 대응할 수 있기 때문입니다.
예를 들어, 실시간으로 들어오는 주식 거래 데이터를 가격 순서로 관리하면서 빠르게 특정 가격대를 찾아야 하는 경우에 매우 유용합니다. 배열이나 링크드 리스트를 사용했다면 탐색이나 정렬된 삽입에 O(n)이 걸렸겠지만, BST를 사용하면 트리의 높이만큼만 탐색하면 되므로 훨씬 빠릅니다.
BST의 핵심 특징은 세 가지입니다: 1) 각 노드는 왼쪽 서브트리의 모든 값보다 크고, 2) 오른쪽 서브트리의 모든 값보다 작으며, 3) 왼쪽과 오른쪽 서브트리도 각각 BST입니다. 이러한 재귀적 특성이 모든 연산을 효율적으로 만듭니다.
코드 예제
class Node {
constructor(value) {
this.value = value;
this.left = null; // 왼쪽 자식: 현재 노드보다 작은 값
this.right = null; // 오른쪽 자식: 현재 노드보다 큰 값
}
}
class BST {
constructor() {
this.root = null; // 트리의 시작점
}
// BST가 비어있는지 확인
isEmpty() {
return this.root === null;
}
}
설명
이것이 하는 일: BST의 기본 구조를 정의하고, 트리를 구성하는 노드와 트리 자체를 클래스로 표현합니다. 먼저 Node 클래스는 BST의 각 노드를 나타냅니다.
value는 해당 노드가 저장하는 데이터이고, left와 right는 각각 왼쪽과 오른쪽 자식 노드를 가리키는 포인터입니다. 초기에는 null로 설정되어 자식이 없는 상태로 시작합니다.
이렇게 설계하는 이유는 나중에 값을 비교하면서 동적으로 자식 노드를 연결할 수 있기 때문입니다. 그 다음으로 BST 클래스가 실행되면서 전체 트리를 관리합니다.
root는 트리의 최상위 노드를 가리키며, 모든 연산은 이 root에서 시작됩니다. isEmpty 메서드는 트리가 비어있는지 확인하는데, 이는 삽입이나 검색 전에 예외 케이스를 처리하는 데 유용합니다.
마지막으로, 이 기본 구조를 바탕으로 다양한 메서드들(insert, search, delete 등)을 추가할 수 있습니다. 최종적으로 완성된 BST는 대량의 데이터를 효율적으로 관리하는 강력한 도구가 됩니다.
여러분이 이 코드를 사용하면 데이터를 체계적으로 정리하면서도 빠른 검색이 가능한 자료구조를 구축할 수 있습니다. 또한 객체 지향 설계로 코드의 재사용성과 유지보수성이 높아지며, 추후 기능 확장이 쉬워집니다.
실전 팁
💡 Node 클래스를 BST 클래스 내부에 중첩 클래스로 만들면 캡슐화가 더 좋아집니다. 외부에서 Node를 직접 사용할 일이 없기 때문입니다.
💡 실무에서는 value뿐만 아니라 key-value 쌍을 저장하는 경우가 많습니다. this.key와 this.data를 따로 관리하는 것을 고려해보세요.
💡 TypeScript를 사용한다면 제네릭을 활용해 <T>로 다양한 타입을 지원하도록 설계하세요. class Node<T> { value: T; ... }
💡 디버깅을 위해 toString() 메서드를 추가하여 트리 구조를 시각적으로 출력할 수 있게 하면 개발 과정이 훨씬 수월합니다.
💡 프로덕션 환경에서는 노드 개수를 추적하는 size 속성을 추가하면 트리의 상태를 O(1)에 확인할 수 있습니다.
2. 노드 구조 설계
시작하며
여러분이 트리 구조를 처음 구현할 때, 노드에 어떤 정보를 담아야 할지 고민해본 적 있나요? 단순히 값만 저장하면 될까요, 아니면 더 많은 정보가 필요할까요?
이런 설계 결정은 나중에 트리의 성능과 기능에 큰 영향을 미칩니다. 필요한 정보가 부족하면 나중에 리팩토링이 어렵고, 불필요한 정보를 담으면 메모리 낭비가 발생합니다.
바로 이럴 때 필요한 것이 효율적인 노드 설계입니다. 실무에서 필요한 정보만 담으면서도 확장 가능한 구조를 만들어야 합니다.
개요
간단히 말해서, 노드는 데이터와 자식 노드에 대한 참조를 함께 저장하는 기본 단위입니다. 기본 BST 노드는 value, left, right만 있으면 충분하지만, 실무에서는 추가 정보가 필요한 경우가 많습니다.
예를 들어, AVL 트리나 Red-Black 트리 같은 균형 트리를 구현하려면 높이나 색상 정보가 필요하고, 부모 노드로의 역참조가 있으면 삭제 연산이 더 쉬워집니다. 기존에는 단순히 값만 저장했다면, 이제는 메타데이터를 함께 관리하여 더 복잡한 연산을 효율적으로 처리할 수 있습니다.
노드 설계의 핵심은 최소한의 정보로 최대한의 기능을 제공하는 것입니다. 불필요한 필드는 메모리를 낭비하고, 필수 정보가 없으면 복잡한 연산을 구현할 수 없습니다.
적절한 균형이 중요합니다.
코드 예제
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null; // 부모 노드 참조 (삭제 연산에 유용)
this.height = 1; // AVL 트리 균형 유지용
}
// 리프 노드인지 확인
isLeaf() {
return this.left === null && this.right === null;
}
// 자식이 하나만 있는지 확인
hasOneChild() {
return (this.left !== null) !== (this.right !== null);
}
}
설명
이것이 하는 일: 확장 가능한 노드 구조를 설계하고, 노드의 상태를 확인하는 유틸리티 메서드를 제공합니다. 첫 번째로, constructor는 기본 필드(value, left, right)와 함께 선택적 필드(parent, height)를 초기화합니다.
parent는 상향 탐색이나 삭제 연산에서 유용하고, height는 AVL 트리 같은 자가 균형 트리를 구현할 때 필수입니다. 이렇게 확장성을 고려하여 설계하면 나중에 고급 기능을 추가할 때 노드 구조를 변경하지 않아도 됩니다.
그 다음으로, isLeaf 메서드가 실행되면서 해당 노드가 자식이 없는 리프 노드인지 확인합니다. 이는 삭제 연산에서 가장 간단한 케이스를 처리할 때 사용됩니다.
리프 노드는 단순히 부모의 참조를 null로 만들면 삭제가 완료됩니다. hasOneChild 메서드는 노드가 자식을 하나만 가지는지 확인합니다.
XOR 연산자를 활용하여 left와 right 중 정확히 하나만 null이 아닌 경우를 감지합니다. 이는 삭제 연산에서 중간 난이도 케이스를 처리할 때 핵심적인 역할을 합니다.
여러분이 이 코드를 사용하면 다양한 트리 연산을 구현할 때 노드의 상태를 쉽게 파악할 수 있습니다. 또한 메서드로 추상화되어 있어 코드 가독성이 높아지고, 버그 발생 가능성이 줄어듭니다.
실전 팁
💡 parent 참조를 추가하면 메모리는 약간 증가하지만, 삭제 연산과 순회의 복잡도가 크게 감소합니다. 트레이드오프를 고려하세요.
💡 실무에서는 노드에 timestamp나 metadata 객체를 추가하여 생성 시간, 수정 횟수 등을 추적하면 디버깅과 분석에 도움됩니다.
💡 isLeaf 같은 상태 확인 메서드는 getter로 구현할 수도 있습니다: get isLeaf() { return !this.left && !this.right; }
💡 노드를 비교할 때는 compareTo 메서드를 구현하면 다양한 타입(숫자, 문자열, 객체)을 일관되게 처리할 수 있습니다.
💡 순환 참조(parent)를 사용할 때는 메모리 누수에 주의하세요. 노드를 삭제할 때 반드시 parent 참조도 끊어야 합니다.
3. 검색 연산 구현
시작하며
여러분이 수천 개의 데이터 중에서 특정 값을 찾아야 할 때, 처음부터 끝까지 하나씩 확인하시나요? 이런 선형 탐색은 데이터가 많아질수록 비효율적입니다.
이런 문제는 실시간 시스템이나 대용량 데이터 처리에서 심각한 성능 저하를 일으킵니다. 사용자가 검색 결과를 기다리는 시간이 길어지면 사용자 경험이 나빠집니다.
바로 이럴 때 필요한 것이 BST의 검색 연산입니다. 트리의 속성을 활용하여 매 단계마다 탐색 범위를 절반으로 줄일 수 있습니다.
개요
간단히 말해서, BST 검색은 현재 노드의 값과 찾는 값을 비교하여 왼쪽 또는 오른쪽으로 이동하는 과정을 반복합니다. 이 연산이 필요한 이유는 O(log n)의 시간 복잡도로 빠르게 데이터를 찾을 수 있기 때문입니다.
예를 들어, 1000개의 노드가 있는 균형 잡힌 BST에서는 최대 10번의 비교만으로 원하는 값을 찾을 수 있습니다. 배열의 선형 탐색이 O(n)이 걸린다면, BST 검색은 트리의 높이만큼만 탐색하므로 훨씬 효율적입니다.
정렬된 배열의 이진 탐색과 비슷한 성능이지만, 삽입과 삭제가 더 유연합니다. 검색 연산의 핵심은 BST의 정렬 속성을 활용하는 것입니다.
찾는 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른쪽으로만 가면 되므로 불필요한 비교를 생략할 수 있습니다.
코드 예제
class BST {
// ... 생성자 및 기타 메서드 ...
search(value) {
return this.searchNode(this.root, value);
}
searchNode(node, value) {
// 노드가 없으면 값을 찾지 못함
if (node === null) return false;
// 값을 찾음
if (value === node.value) return true;
// 찾는 값이 작으면 왼쪽 서브트리 탐색
if (value < node.value) {
return this.searchNode(node.left, value);
}
// 찾는 값이 크면 오른쪽 서브트리 탐색
return this.searchNode(node.right, value);
}
}
설명
이것이 하는 일: 재귀적으로 트리를 탐색하여 특정 값의 존재 여부를 확인합니다. 첫 번째로, search 메서드는 public 인터페이스 역할을 하며, 실제 탐색 로직은 searchNode라는 private 메서드에 위임합니다.
이렇게 분리하는 이유는 사용자가 root 노드를 직접 다룰 필요 없이 깔끔한 API를 제공하기 위함입니다. search(50)처럼 간단하게 호출할 수 있습니다.
그 다음으로, searchNode가 실행되면서 세 가지 케이스를 처리합니다. 첫째, node가 null이면 더 이상 탐색할 곳이 없으므로 false를 반환합니다.
둘째, value가 node.value와 같으면 값을 찾았으므로 true를 반환합니다. 셋째, value가 더 작거나 크면 해당하는 서브트리로 재귀 호출합니다.
재귀 호출이 진행되면서 탐색 범위가 계속 절반씩 줄어듭니다. 예를 들어, [50, 30, 70, 20, 40] 구조에서 40을 찾는다면 50 → 30 → 40 순서로 3번만 비교하면 됩니다.
최종적으로 값을 찾거나 null에 도달할 때까지 이 과정이 반복됩니다. 여러분이 이 코드를 사용하면 대량의 데이터에서도 빠르게 값을 찾을 수 있습니다.
또한 재귀적 구조 덕분에 코드가 간결하고 이해하기 쉬우며, BST의 정렬 속성을 자연스럽게 활용합니다.
실전 팁
💡 반복문 버전도 구현해보세요. 재귀는 직관적이지만 깊은 트리에서 스택 오버플로우 위험이 있습니다. while 루프로 구현하면 더 안전합니다.
💡 찾은 노드 자체를 반환하도록 수정하면(return node) 검색과 동시에 수정 작업을 할 수 있어 더 유용합니다.
💡 실무에서는 검색 경로를 배열로 기록하면 디버깅이나 경로 분석에 도움됩니다: const path = []; ... path.push(node.value);
💡 성능 최적화를 위해 자주 검색되는 값을 캐시하거나, 최근 검색 결과를 LRU 캐시에 저장하는 것을 고려하세요.
💡 비교 함수를 인자로 받도록 확장하면 숫자뿐만 아니라 문자열이나 객체도 비교할 수 있습니다: searchNode(node, value, compareFn)
4. 삽입 연산 구현
시작하며
여러분이 새로운 데이터를 트리에 추가할 때, 어디에 넣어야 BST의 속성이 유지될까요? 잘못된 위치에 삽입하면 트리 전체가 망가집니다.
이런 문제는 데이터 무결성을 해치고, 이후 모든 연산의 정확성에 영향을 미칩니다. 검색이 제대로 작동하지 않거나, 예상치 못한 결과가 나올 수 있습니다.
바로 이럴 때 필요한 것이 올바른 삽입 연산입니다. BST의 정렬 속성을 유지하면서 새 노드를 정확한 위치에 추가해야 합니다.
개요
간단히 말해서, 삽입은 리프 노드에 도달할 때까지 검색과 같은 방식으로 이동한 후, 적절한 위치에 새 노드를 생성합니다. 이 연산이 필요한 이유는 동적으로 데이터를 추가하면서도 BST의 효율성을 유지할 수 있기 때문입니다.
예를 들어, 실시간으로 들어오는 센서 데이터를 정렬된 상태로 유지하면서 빠르게 추가할 수 있습니다. 배열에 정렬을 유지하며 삽입하면 O(n)이 걸리지만, BST는 평균 O(log n)에 삽입할 수 있습니다.
연결 리스트처럼 삽입은 빠르지만 검색이 느린 것과 달리, BST는 둘 다 균형 잡힌 성능을 제공합니다. 삽입의 핵심은 올바른 리프 위치를 찾는 것입니다.
작으면 왼쪽으로, 크면 오른쪽으로 이동하다가 null을 만나면 그 자리가 새 노드의 위치입니다. 중복 값은 보통 무시하거나 카운트를 증가시킵니다.
코드 예제
class BST {
// ... 기타 메서드 ...
insert(value) {
const newNode = new Node(value);
if (this.root === null) {
// 트리가 비어있으면 루트로 설정
this.root = newNode;
return this;
}
// 삽입 위치 찾기
this.insertNode(this.root, newNode);
return this;
}
insertNode(node, newNode) {
// 새 값이 현재 노드보다 작으면 왼쪽으로
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode; // 삽입 완료
} else {
this.insertNode(node.left, newNode); // 계속 탐색
}
} else if (newNode.value > node.value) {
// 새 값이 크면 오른쪽으로
if (node.right === null) {
node.right = newNode; // 삽입 완료
} else {
this.insertNode(node.right, newNode); // 계속 탐색
}
}
// 중복 값은 무시 (필요시 카운트 증가 등 처리)
}
}
설명
이것이 하는 일: 새로운 값을 BST의 올바른 위치에 삽입하여 정렬 속성을 유지합니다. 첫 번째로, insert 메서드는 새 노드를 생성하고 트리가 비어있는지 확인합니다.
비어있다면 새 노드를 루트로 설정하고 종료합니다. 이는 가장 간단한 케이스이며, 첫 번째 노드는 항상 루트가 되어야 합니다.
return this를 통해 메서드 체이닝을 지원합니다(tree.insert(5).insert(3).insert(7)). 그 다음으로, insertNode가 실행되면서 재귀적으로 삽입 위치를 찾습니다.
newNode.value와 node.value를 비교하여 왼쪽 또는 오른쪽으로 이동합니다. 만약 해당 방향의 자식이 null이면 바로 그 자리에 새 노드를 삽입하고, 자식이 이미 있다면 그 자식을 대상으로 다시 재귀 호출합니다.
중복 값의 경우 아무 작업도 하지 않고 종료합니다. 실무에서는 중복을 허용할지, 카운트를 증가시킬지, 에러를 던질지 비즈니스 로직에 따라 결정해야 합니다.
최종적으로 새 노드는 항상 리프 위치에 추가되며, BST의 정렬 속성이 자동으로 유지됩니다. 여러분이 이 코드를 사용하면 동적으로 데이터를 추가하면서도 검색 효율성을 유지할 수 있습니다.
또한 재귀 구조 덕분에 코드가 간결하며, 트리의 크기에 관계없이 일관된 방식으로 동작합니다.
실전 팁
💡 반복문 버전이 더 효율적입니다. let current = this.root; while(current) { ... }로 구현하면 스택 오버플로우를 방지할 수 있습니다.
💡 parent 참조를 유지한다면 newNode.parent = node를 추가하여 양방향 연결을 만드세요. 삭제 연산이 훨씬 쉬워집니다.
💡 실무에서는 중복 처리를 명시적으로 정의하세요: node.count++를 추가하거나 Set처럼 중복을 거부하는 예외를 던지세요.
💡 삽입 후 트리의 높이가 불균형해질 수 있습니다. AVL이나 Red-Black 트리로 확장하여 자동 균형 조정을 구현하세요.
💡 대량 삽입 시에는 배열을 정렬한 후 중간값부터 삽입하면 균형 잡힌 트리를 만들 수 있습니다: insertBulk(sortedArray, start, end)
5. 최솟값과 최댓값 찾기
시작하며
여러분이 트리에서 가장 작은 값이나 가장 큰 값을 찾아야 할 때, 모든 노드를 순회하시나요? BST에서는 훨씬 똑똑한 방법이 있습니다.
이런 연산은 통계 분석, 우선순위 큐 구현, 범위 쿼리 등에서 자주 필요합니다. 비효율적으로 구현하면 O(n)이 걸려 BST의 장점을 살리지 못합니다.
바로 이럴 때 필요한 것이 BST의 구조적 특성을 활용한 최솟값/최댓값 찾기입니다. 단순히 한 방향으로만 계속 이동하면 됩니다.
개요
간단히 말해서, 최솟값은 가장 왼쪽 리프 노드이고, 최댓값은 가장 오른쪽 리프 노드입니다. 이 패턴이 중요한 이유는 O(h)의 시간 복잡도(h는 트리의 높이)로 매우 빠르게 극값을 찾을 수 있기 때문입니다.
예를 들어, 주식 거래 시스템에서 현재 최저가나 최고가를 실시간으로 찾아야 할 때 매우 유용합니다. 전체 트리를 순회하는 O(n) 방법과 달리, BST에서는 한 방향으로만 이동하므로 균형 잡힌 트리에서는 O(log n), 최악의 경우에도 O(n)입니다.
이 연산의 핵심은 BST의 정렬 속성입니다. 왼쪽 서브트리는 항상 부모보다 작으므로 계속 왼쪽으로 가면 최솟값, 오른쪽으로 가면 최댓값을 찾을 수 있습니다.
더 이상 갈 곳이 없는 리프 노드가 바로 답입니다.
코드 예제
class BST {
// ... 기타 메서드 ...
// 최솟값 찾기 (가장 왼쪽 노드)
findMin(node = this.root) {
if (node === null) return null;
// 왼쪽 자식이 없을 때까지 이동
while (node.left !== null) {
node = node.left;
}
return node.value;
}
// 최댓값 찾기 (가장 오른쪽 노드)
findMax(node = this.root) {
if (node === null) return null;
// 오른쪽 자식이 없을 때까지 이동
while (node.right !== null) {
node = node.right;
}
return node.value;
}
}
설명
이것이 하는 일: 트리의 한쪽 끝까지 이동하여 극값을 효율적으로 찾습니다. 첫 번째로, findMin은 트리가 비어있는지 확인한 후, 왼쪽 자식이 null이 될 때까지 계속 왼쪽으로 이동합니다.
매 단계마다 더 작은 값으로 이동하므로, 더 이상 갈 곳이 없는 지점이 바로 최솟값입니다. node 파라미터에 기본값으로 this.root를 설정하여 전체 트리뿐만 아니라 특정 서브트리의 최솟값도 찾을 수 있게 했습니다.
그 다음으로, findMax는 같은 논리로 오른쪽 방향으로 이동합니다. 이 메서드들은 반복문을 사용했는데, 재귀보다 더 효율적이고 스택 오버플로우 위험이 없기 때문입니다.
트리의 높이가 아무리 깊어도 안전하게 동작합니다. 이 메서드들의 반환값은 노드의 value입니다.
하지만 노드 자체(return node)를 반환하도록 수정하면 삭제 연산에서 활용할 수 있습니다. 예를 들어, 오른쪽 서브트리의 최솟값을 찾아 삭제할 노드와 교체하는 전략에 사용됩니다.
최종적으로 이 간단한 메서드들이 많은 고급 트리 연산의 기초가 됩니다. 여러분이 이 코드를 사용하면 정렬된 데이터의 양 끝값을 매우 빠르게 조회할 수 있습니다.
또한 서브트리에서도 동작하므로 범위 쿼리나 부분 통계에도 활용 가능합니다.
실전 팁
💡 노드 자체를 반환하도록 수정하면 findMin(node.right)처럼 서브트리에서 후속 노드를 찾을 때 유용합니다.
💡 재귀 버전도 간결합니다: return node.left ? findMin(node.left) : node.value. 하지만 반복문이 더 안전합니다.
💡 트리가 비어있을 때의 처리를 명확히 하세요. null 반환 대신 throw new Error('Empty tree')를 던지는 것도 방법입니다.
💡 predecessor(직전 값)와 successor(직후 값) 메서드도 이를 활용하여 구현할 수 있습니다. 노드의 왼쪽 서브트리에서 최댓값, 오른쪽 서브트리에서 최솟값을 찾으면 됩니다.
💡 실무에서는 캐싱을 고려하세요. 트리가 변경되지 않는다면 min/max를 저장해두고 재사용하면 O(1)로 조회 가능합니다.
6. 중위 순회 구현
시작하며
여러분이 BST의 모든 데이터를 정렬된 순서로 가져와야 할 때, 어떤 방법을 사용하시나요? 트리 구조를 배열로 변환하거나 정렬 알고리즘을 적용하시나요?
이런 문제는 보고서 생성, 데이터 내보내기, 범위 쿼리 등에서 자주 발생합니다. 비효율적인 방법을 사용하면 추가적인 정렬 비용이 발생합니다.
바로 이럴 때 필요한 것이 중위 순회(In-order Traversal)입니다. BST의 중위 순회는 자동으로 정렬된 순서로 모든 노드를 방문합니다.
개요
간단히 말해서, 중위 순회는 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 방문하는 재귀적 패턴입니다. 이 순회 방법이 중요한 이유는 BST의 구조적 특성 덕분에 자동으로 오름차순 정렬된 결과를 얻을 수 있기 때문입니다.
예를 들어, 사용자 목록을 이름 순으로 출력하거나, 가격 범위 내의 상품을 조회할 때 매우 유용합니다. 다른 순회 방법(전위, 후위)과 달리 중위 순회는 BST에서 특별한 의미를 갖습니다.
전위 순회는 트리 복사에, 후위 순회는 트리 삭제에 유용하지만, 중위 순회만이 정렬된 데이터를 제공합니다. 중위 순회의 핵심은 재귀적 구조입니다.
각 노드에서 왼쪽을 먼저 처리하고, 그 다음 자신을 처리하고, 마지막으로 오른쪽을 처리합니다. 이 순서가 BST의 정렬 속성과 완벽하게 일치합니다.
코드 예제
class 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);
}
}
}
설명
이것이 하는 일: 재귀적으로 트리를 순회하여 모든 값을 정렬된 순서로 수집합니다. 첫 번째로, inOrderTraversal은 빈 배열을 생성하고 재귀 헬퍼 메서드인 inOrder를 호출합니다.
결과 배열을 파라미터로 전달하는 이유는 재귀 호출 간에 상태를 공유하기 위함입니다. 함수형 프로그래밍 방식으로 새 배열을 반환하고 합치는 것보다 메모리 효율적입니다.
그 다음으로, inOrder 메서드가 실행되면서 세 단계로 동작합니다. 첫째, node.left가 null이 아니면 왼쪽 서브트리를 재귀적으로 순회합니다.
이는 더 작은 값들을 먼저 처리하는 것입니다. 둘째, 왼쪽이 모두 처리되면 현재 노드의 값을 result에 추가합니다.
셋째, node.right가 null이 아니면 오른쪽 서브트리를 순회하여 더 큰 값들을 처리합니다. 재귀 호출이 끝나면 result 배열에는 모든 값이 오름차순으로 정렬되어 있습니다.
예를 들어, [50, 30, 70, 20, 40] 구조라면 [20, 30, 40, 50, 70]이 반환됩니다. 최종적으로 이 결과를 활용하여 보고서를 생성하거나, 특정 범위의 값만 필터링하거나, 검증 목적으로 사용할 수 있습니다.
여러분이 이 코드를 사용하면 별도의 정렬 알고리즘 없이 O(n) 시간에 정렬된 데이터를 얻을 수 있습니다. 또한 BST의 근본적인 장점을 활용하여 효율적으로 데이터를 처리합니다.
실전 팁
💡 콜백 함수를 인자로 받으면 더 유연합니다: inOrder(node, callback) { ... callback(node.value); }. 이렇게 하면 출력, 수정, 필터링 등 다양한 작업이 가능합니다.
💡 제너레이터를 사용하면 메모리 효율이 더 좋습니다: *inOrder(node) { ... yield node.value; }. 대용량 트리에서 유리합니다.
💡 반복문 버전은 스택을 명시적으로 관리합니다: const stack = []; ... 재귀 깊이 제한이 없어 더 안전합니다.
💡 역순 정렬이 필요하면 오른쪽을 먼저 방문하세요: inOrder(node.right) → process → inOrder(node.left)
💡 범위 쿼리를 구현하려면 조건을 추가하세요: if (node.value >= min && node.value <= max) result.push(node.value)
7. 삭제 연산 구현
시작하며
여러분이 트리에서 노드를 삭제할 때, 단순히 제거만 하면 될까요? BST의 속성을 유지하면서 삭제하는 것은 가장 복잡한 연산입니다.
이런 문제는 세 가지 케이스(자식 없음, 하나, 둘)를 모두 처리해야 하기 때문에 까다롭습니다. 잘못 구현하면 트리 구조가 깨지고 이후 연산이 모두 실패합니다.
바로 이럴 때 필요한 것이 체계적인 삭제 알고리즘입니다. 각 케이스를 명확히 구분하여 처리해야 합니다.
개요
간단히 말해서, 삭제는 세 가지 경우로 나뉩니다: 리프 노드(자식 없음), 자식 하나, 자식 둘. 이 연산이 복잡한 이유는 특히 자식이 둘인 경우 대체 노드를 찾아 재배치해야 하기 때문입니다.
예를 들어, 부서장 노드를 삭제할 때 후임자를 찾아 승진시키는 것과 비슷합니다. 단순히 노드를 제거하는 것이 아니라, BST의 정렬 속성을 유지하면서 구조를 재구성해야 합니다.
특히 자식이 둘인 경우 오른쪽 서브트리의 최솟값(또는 왼쪽 서브트리의 최댓값)으로 대체하는 전략을 사용합니다. 삭제의 핵심은 각 케이스를 정확히 판단하고 적절히 처리하는 것입니다.
리프는 그냥 제거, 자식 하나는 부모와 자식을 직접 연결, 자식 둘은 후속 노드로 대체하는 패턴을 이해해야 합니다.
코드 예제
class BST {
// ... 기타 메서드 ...
delete(value) {
this.root = this.deleteNode(this.root, value);
return this;
}
deleteNode(node, value) {
if (node === null) return null;
// 삭제할 노드 찾기
if (value < node.value) {
node.left = this.deleteNode(node.left, value);
return node;
} else if (value > node.value) {
node.right = this.deleteNode(node.right, value);
return node;
}
// 노드를 찾음 - 삭제 처리
// Case 1: 자식이 없음 (리프 노드)
if (node.left === null && node.right === null) {
return null;
}
// Case 2: 자식이 하나만 있음
if (node.left === null) return node.right;
if (node.right === null) return node.left;
// Case 3: 자식이 둘 다 있음
// 오른쪽 서브트리의 최솟값으로 대체
const minRight = this.findMinNode(node.right);
node.value = minRight.value;
node.right = this.deleteNode(node.right, minRight.value);
return node;
}
findMinNode(node) {
while (node.left !== null) node = node.left;
return node;
}
}
설명
이것이 하는 일: 값을 찾아 삭제하고, BST 속성을 유지하도록 트리를 재구성합니다. 첫 번째로, delete 메서드는 재귀 헬퍼를 호출하고 새로운 루트를 받습니다.
루트를 재할당하는 이유는 루트 자체가 삭제될 수 있기 때문입니다. deleteNode는 값을 비교하며 삭제할 노드를 찾아 이동합니다.
찾는 과정은 검색과 동일합니다. 그 다음으로, 노드를 찾으면 세 가지 케이스를 처리합니다.
첫 번째 케이스는 리프 노드로, 가장 간단합니다. null을 반환하여 부모의 참조를 끊으면 노드가 삭제됩니다.
두 번째 케이스는 자식이 하나만 있는 경우로, 해당 자식을 반환하여 부모와 직접 연결합니다. 삭제된 노드를 건너뛰는 것입니다.
세 번째 케이스가 가장 복잡합니다. 자식이 둘이면 노드를 직접 제거할 수 없습니다.
대신 오른쪽 서브트리의 최솟값(후속 노드)을 찾아 현재 노드의 값을 대체합니다. 그런 다음 오른쪽 서브트리에서 그 후속 노드를 삭제합니다(재귀 호출).
최종적으로 재구성된 노드를 반환하여 부모와 연결합니다. 여러분이 이 코드를 사용하면 복잡한 삭제 로직을 체계적으로 처리할 수 있습니다.
또한 재귀 구조 덕분에 각 케이스가 명확히 분리되어 이해하기 쉽고, 버그 발생 가능성이 줄어듭니다.
실전 팁
💡 왼쪽 서브트리의 최댓값을 사용하는 방법도 있습니다. const maxLeft = findMaxNode(node.left). 둘 다 동일하게 작동합니다.
💡 parent 참조가 있다면 코드가 더 간단해집니다. 반복문으로 구현하고 부모의 left/right를 직접 수정하세요.
💡 삭제 후 트리의 균형이 깨질 수 있습니다. AVL이나 Red-Black 트리는 삭제 후 자동으로 재균형 조정을 수행합니다.
💡 실무에서는 soft delete를 고려하세요. node.isDeleted = true로 표시만 하고 실제로 제거하지 않으면 복구가 쉽습니다.
💡 삭제한 노드를 반환하도록 수정하면 실행 취소 기능이나 로깅에 유용합니다: return deletedNode;
8. BST 높이 계산
시작하며
여러분이 트리의 성능을 평가할 때, 어떤 지표를 확인하시나요? BST의 높이는 모든 연산의 시간 복잡도를 결정하는 핵심 지표입니다.
이런 정보는 트리가 균형 잡혀있는지, 리밸런싱이 필요한지, 성능 저하가 예상되는지를 판단하는 데 필수적입니다. 높이가 너무 크면 O(n)에 가까워져 BST의 장점이 사라집니다.
바로 이럴 때 필요한 것이 트리 높이 계산입니다. 재귀적으로 서브트리의 높이를 계산하여 전체 트리의 균형 상태를 파악할 수 있습니다.
개요
간단히 말해서, 트리의 높이는 루트에서 가장 먼 리프까지의 경로 길이입니다. 이 정보가 중요한 이유는 BST의 성능이 높이에 직접적으로 영향을 받기 때문입니다.
예를 들어, 1000개 노드의 균형 트리는 높이가 약 10이지만, 불균형 트리는 최악의 경우 1000이 될 수 있습니다. 균형 잡힌 트리는 O(log n)의 성능을 보장하지만, 편향된 트리는 O(n)으로 퇴화됩니다.
연결 리스트와 다를 바 없어집니다. 높이 계산의 핵심은 재귀적 사고입니다.
각 노드의 높이는 왼쪽과 오른쪽 서브트리 중 더 높은 쪽에 1을 더한 값입니다. 리프 노드는 높이가 1(또는 0, 정의에 따라)입니다.
코드 예제
class BST {
// ... 기타 메서드 ...
// 트리의 높이 계산
height(node = this.root) {
// 빈 트리의 높이는 0
if (node === null) return 0;
// 왼쪽과 오른쪽 서브트리의 높이를 재귀적으로 계산
const leftHeight = this.height(node.left);
const rightHeight = this.height(node.right);
// 더 높은 쪽 + 1이 현재 노드의 높이
return Math.max(leftHeight, rightHeight) + 1;
}
// 트리가 균형 잡혔는지 확인 (AVL 기준)
isBalanced(node = this.root) {
if (node === null) return true;
const leftHeight = this.height(node.left);
const rightHeight = this.height(node.right);
// 높이 차이가 1 이하이고, 양쪽 서브트리도 균형이어야 함
return Math.abs(leftHeight - rightHeight) <= 1 &&
this.isBalanced(node.left) &&
this.isBalanced(node.right);
}
}
설명
이것이 하는 일: 재귀적으로 서브트리의 높이를 계산하고, 트리의 균형 여부를 판단합니다. 첫 번째로, height 메서드는 기저 케이스를 처리합니다.
node가 null이면 높이는 0입니다(또는 -1로 정의하기도 합니다). 빈 트리나 리프 노드의 자식에 대한 재귀 호출이 여기서 종료됩니다.
node 파라미터에 기본값을 주어 특정 서브트리의 높이도 계산할 수 있습니다. 그 다음으로, 왼쪽과 오른쪽 서브트리의 높이를 재귀적으로 계산합니다.
각 재귀 호출은 더 작은 서브트리로 내려가며, 결국 리프 노드에 도달합니다. 리프 노드는 양쪽이 null이므로 0 + 0 + 1 = 1의 높이를 갖습니다.
그 위의 노드들은 자식들의 높이 중 최댓값에 1을 더한 값이 됩니다. isBalanced 메서드는 AVL 트리의 균형 조건을 확인합니다.
모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하이고, 두 서브트리 자체도 균형 잡혀있어야 합니다. 최종적으로 이 메서드를 통해 리밸런싱이 필요한지 판단할 수 있습니다.
여러분이 이 코드를 사용하면 트리의 성능 상태를 정량적으로 평가할 수 있습니다. 또한 균형 여부를 확인하여 AVL이나 Red-Black 트리로 전환할 시점을 결정할 수 있습니다.
실전 팁
💡 높이를 노드에 캐싱하면 매번 재계산하지 않아도 됩니다: node.height = ... 삽입/삭제 시에만 업데이트하세요.
💡 isBalanced의 시간 복잡도는 O(n²)입니다. 높이 계산을 함께 하는 최적화 버전을 구현하면 O(n)으로 줄일 수 있습니다.
💡 높이 기반 균형 인자를 계산하여 AVL 트리의 회전이 필요한 시점을 감지하세요: balanceFactor = leftHeight - rightHeight
💡 노드 개수와 높이의 관계를 모니터링하면 트리의 효율성을 평가할 수 있습니다. 이상적으로는 height ≈ log₂(nodeCount)입니다.
💡 실무에서는 높이 제한을 설정하여 최악의 경우를 방지하세요. 높이가 특정 임계값을 넘으면 리밸런싱을 강제하거나 경고를 발생시키세요.