이미지 로딩 중...
AI Generated
2025. 11. 7. · 3 Views
BST 후속자와 선행자 찾기 완벽 가이드
이진 탐색 트리에서 특정 노드의 후속자(Successor)와 선행자(Predecessor)를 찾는 핵심 알고리즘을 학습합니다. 실무에서 범위 검색, 정렬된 데이터 탐색 등에 필수적인 BST 연산을 마스터해보세요.
목차
- BST의 후속자(Successor) 개념 이해
- BST의 선행자(Predecessor) 개념 이해
- 부모 포인터 없이 후속자 찾기
- 중위 순회를 활용한 후속자 찾기
- 실전 활용: 범위 쿼리 구현
- 노드 삭제와 후속자/선행자 활용
- Morris 순회로 후속자 찾기 (상수 공간)
- 중복 값이 있는 BST에서 후속자 처리
1. BST의 후속자(Successor) 개념 이해
시작하며
여러분이 사용자 목록을 나이 순으로 관리하는 시스템을 개발할 때, "30세보다 큰 나이 중 가장 작은 값"을 찾아야 하는 상황을 겪어본 적 있나요? 또는 게임 리더보드에서 특정 점수보다 바로 높은 점수의 플레이어를 찾아야 할 때 말이죠.
이런 문제는 정렬된 데이터를 다루는 실제 개발 현장에서 매우 자주 발생합니다. 단순히 배열을 순회하면 O(n)의 시간이 걸리고, 매번 정렬하면 더욱 비효율적입니다.
데이터가 수만 개라면 성능 문제가 심각해질 수 있습니다. 바로 이럴 때 필요한 것이 BST의 후속자(Successor) 연산입니다.
이진 탐색 트리의 특성을 활용하면 O(log n) 또는 O(h) 시간에 "다음으로 큰 값"을 효율적으로 찾을 수 있습니다.
개요
간단히 말해서, 후속자(Successor)는 주어진 노드보다 큰 값들 중에서 가장 작은 값을 가진 노드입니다. BST의 중위 순회(Inorder Traversal) 순서에서 바로 다음에 오는 노드라고 생각하면 쉽습니다.
왜 이 개념이 필요한지 실무 관점에서 생각해봅시다. 예를 들어, 예약 시스템에서 "오후 3시 이후의 가장 빠른 예약 시간"을 찾거나, 데이터베이스 인덱스에서 범위 검색을 수행할 때 매우 유용합니다.
많은 데이터베이스 시스템이 내부적으로 B-Tree(BST의 확장)를 사용하는 이유도 이러한 연산의 효율성 때문입니다. 기존에 배열에서 선형 탐색으로 다음 값을 찾았다면, 이제는 트리 구조의 특성을 활용하여 훨씬 빠르게 찾을 수 있습니다.
후속자를 찾는 핵심 특징은 두 가지 경우로 나뉩니다: (1) 노드에 오른쪽 자식이 있으면, 오른쪽 서브트리의 최솟값이 후속자입니다. (2) 오른쪽 자식이 없으면, 조상 노드 중 처음으로 왼쪽 자식으로 연결된 조상이 후속자입니다.
이러한 특징들을 이해하면 트리 구조에서의 순서 관계를 정확히 파악할 수 있습니다.
코드 예제
// BST 노드 정의
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
this.parent = null; // 부모 노드 참조 (선택적)
}
}
// 후속자(Successor) 찾기
function findSuccessor(node) {
// 경우 1: 오른쪽 자식이 있는 경우
// 오른쪽 서브트리의 최솟값을 찾습니다
if (node.right !== null) {
return findMin(node.right);
}
// 경우 2: 오른쪽 자식이 없는 경우
// 조상 노드를 거슬러 올라가며 찾습니다
let parent = node.parent;
let current = node;
// 현재 노드가 부모의 오른쪽 자식인 동안 계속 올라갑니다
while (parent !== null && current === parent.right) {
current = parent;
parent = parent.parent;
}
return parent; // 첫 번째 왼쪽 자식 관계의 부모가 후속자
}
// 최솟값 찾기 (가장 왼쪽 노드)
function findMin(node) {
while (node.left !== null) {
node = node.left;
}
return node;
}
설명
이것이 하는 일: 후속자 알고리즘은 BST의 정렬된 순서에서 다음 노드를 찾습니다. 전체 트리를 순회하지 않고, 트리의 구조적 특성만을 이용하여 효율적으로 탐색합니다.
첫 번째로, 주어진 노드에 오른쪽 자식이 있는지 확인합니다. 오른쪽 자식이 있다면, 현재 노드보다 큰 값들이 모두 오른쪽 서브트리에 있다는 BST의 특성을 활용합니다.
이 경우 오른쪽 서브트리에서 가장 작은 값(최좌측 노드)이 바로 후속자가 됩니다. 예를 들어, 노드 값이 20이고 오른쪽 서브트리가 [25, 22, 30]이라면, 22가 후속자입니다.
그 다음으로, 오른쪽 자식이 없는 경우를 처리합니다. 이 상황은 더 흥미롭습니다.
현재 노드보다 큰 값을 찾기 위해 부모 노드로 거슬러 올라가야 합니다. 하지만 무조건 부모가 후속자인 것은 아닙니다.
현재 노드가 부모의 오른쪽 자식이라면, 그 부모는 현재 노드보다 작습니다. 따라서 현재 노드가 왼쪽 자식인 첫 번째 조상을 찾을 때까지 계속 올라가야 합니다.
마지막으로, 알고리즘은 조상을 탐색하며 올라가다가 처음으로 "왼쪽 자식" 관계를 만나면 멈춥니다. 그 부모 노드가 바로 후속자입니다.
만약 루트까지 올라갔는데도 그런 관계를 찾지 못했다면(parent가 null), 현재 노드가 트리에서 가장 큰 값이므로 후속자가 없습니다. 여러분이 이 코드를 사용하면 정렬된 데이터에서 범위 검색, 순차 접근, 다음 값 찾기 등을 O(h) 시간에 수행할 수 있습니다.
균형 잡힌 BST에서는 O(log n)의 성능을 보장하며, 이는 선형 탐색의 O(n)보다 훨씬 효율적입니다. 실무에서는 데이터베이스 커서 이동, 이벤트 스케줄링, 타임라인 탐색 등 다양한 곳에 활용됩니다.
실전 팁
💡 부모 포인터가 없는 경우, 루트에서 시작하여 탐색 경로를 스택에 저장하면 조상 추적이 가능합니다. 공간 복잡도 O(h)가 추가되지만 부모 포인터 없이도 구현할 수 있습니다.
💡 후속자가 null을 반환하면 현재 노드가 최댓값이므로, 이를 활용하여 범위의 끝을 감지할 수 있습니다. 반복 탐색 시 종료 조건으로 사용하세요.
💡 성능 최적화를 위해 자주 접근하는 노드의 후속자를 캐싱하는 것도 고려해보세요. 읽기가 많은 시스템에서 효과적입니다.
💡 균형 잡힌 BST(AVL, Red-Black Tree)를 사용하면 최악의 경우에도 O(log n)을 보장할 수 있습니다. 불균형한 트리에서는 O(n)까지 떨어질 수 있으니 주의하세요.
💡 디버깅 시 중위 순회로 전체 트리를 출력해보고, 찾은 후속자가 순회 결과에서 실제로 다음 위치인지 확인하면 검증에 도움이 됩니다.
2. BST의 선행자(Predecessor) 개념 이해
시작하며
여러분이 음악 스트리밍 앱에서 "이전 곡"을 재생하거나, 달력 앱에서 "오늘 이전의 가장 최근 일정"을 찾아야 하는 경우를 생각해보세요. 이런 "바로 이전 값" 찾기는 사용자 경험의 핵심입니다.
이런 역방향 탐색은 후속자만큼이나 자주 사용되지만, 많은 개발자들이 구현 방법을 헷갈려합니다. 특히 트리 구조에서 "이전"의 의미를 정확히 이해하지 못하면 버그가 발생하기 쉽습니다.
바로 이럴 때 필요한 것이 BST의 선행자(Predecessor) 연산입니다. 후속자의 정확한 반대 개념으로, 왼쪽 방향으로 탐색하는 대칭적인 알고리즘입니다.
개요
간단히 말해서, 선행자(Predecessor)는 주어진 노드보다 작은 값들 중에서 가장 큰 값을 가진 노드입니다. BST의 중위 순회 순서에서 바로 이전에 오는 노드를 의미합니다.
왜 이 개념이 필요한지 실무에서 살펴봅시다. 예를 들어, 버전 관리 시스템에서 "현재 버전 이전의 최신 버전"을 찾거나, 가격 비교 사이트에서 "주어진 예산보다 낮은 가격 중 가장 비싼 상품"을 찾을 때 매우 유용합니다.
양방향 순회가 필요한 모든 애플리케이션에서 필수적입니다. 기존에는 배열을 역순으로 탐색하거나 정렬을 다시 해야 했다면, 이제는 트리 구조 하나로 정방향과 역방향 탐색을 모두 효율적으로 처리할 수 있습니다.
선행자를 찾는 핵심 특징도 두 가지 경우로 나뉩니다: (1) 노드에 왼쪽 자식이 있으면, 왼쪽 서브트리의 최댓값이 선행자입니다. (2) 왼쪽 자식이 없으면, 조상 노드 중 처음으로 오른쪽 자식으로 연결된 조상이 선행자입니다.
이는 후속자의 완벽한 미러 이미지입니다.
코드 예제
// 선행자(Predecessor) 찾기
function findPredecessor(node) {
// 경우 1: 왼쪽 자식이 있는 경우
// 왼쪽 서브트리의 최댓값을 찾습니다
if (node.left !== null) {
return findMax(node.left);
}
// 경우 2: 왼쪽 자식이 없는 경우
// 조상 노드를 거슬러 올라가며 찾습니다
let parent = node.parent;
let current = node;
// 현재 노드가 부모의 왼쪽 자식인 동안 계속 올라갑니다
while (parent !== null && current === parent.left) {
current = parent;
parent = parent.parent;
}
return parent; // 첫 번째 오른쪽 자식 관계의 부모가 선행자
}
// 최댓값 찾기 (가장 오른쪽 노드)
function findMax(node) {
while (node.right !== null) {
node = node.right;
}
return node;
}
// 실전 예제: 선행자와 후속자를 활용한 범위 검색
function findInRange(root, min, max) {
const result = [];
// min의 후속자부터 시작
let current = findSuccessorOrEqual(root, min);
// max보다 작거나 같을 때까지 순회
while (current !== null && current.val <= max) {
result.push(current.val);
current = findSuccessor(current);
}
return result;
}
설명
이것이 하는 일: 선행자 알고리즘은 후속자의 정확한 반대 방향으로 작동합니다. BST의 정렬 순서에서 이전 노드를 찾으며, 왼쪽 방향을 우선적으로 탐색합니다.
첫 번째로, 주어진 노드에 왼쪽 자식이 있는지 확인합니다. 왼쪽 자식이 있다면, 현재 노드보다 작은 값들이 모두 왼쪽 서브트리에 있습니다.
이 중에서 가장 큰 값을 찾아야 하므로, 왼쪽 서브트리의 최댓값(최우측 노드)을 찾습니다. 예를 들어, 노드 값이 50이고 왼쪽 서브트리가 [30, 40, 25]라면, 40이 선행자입니다.
그 다음으로, 왼쪽 자식이 없는 경우를 처리합니다. 이때는 부모 방향으로 올라가야 하는데, 현재 노드가 부모의 왼쪽 자식이라면 그 부모는 현재 노드보다 큽니다.
따라서 현재 노드가 오른쪽 자식인 첫 번째 조상을 찾을 때까지 계속 올라갑니다. 이는 후속자 로직을 좌우 반전한 것과 같습니다.
마지막으로, 조상 탐색 중 처음으로 "오른쪽 자식" 관계를 만나면 그 부모가 선행자입니다. 루트까지 올라갔는데도 찾지 못했다면 현재 노드가 트리에서 가장 작은 값이므로 선행자가 없습니다.
여러분이 이 코드를 사용하면 양방향 탐색이 필요한 모든 상황을 효율적으로 처리할 수 있습니다. 페이지네이션의 "이전/다음" 버튼, 미디어 플레이어의 트랙 이동, 캘린더의 날짜 탐색 등 실무에서 즉시 활용할 수 있습니다.
후속자와 선행자를 조합하면 BST에서 양방향 이터레이터를 구현할 수도 있습니다.
실전 팁
💡 선행자와 후속자는 대칭적이므로, 하나를 정확히 이해하면 다른 하나는 left/right만 바꾸면 됩니다. 코드 재사용성을 높이세요.
💡 노드 삭제 시 선행자나 후속자를 사용하여 대체 노드를 찾는 것이 일반적입니다. 두 방법 모두 BST 속성을 유지합니다.
💡 범위 검색 구현 시 시작점의 후속자부터 종료점까지 순회하면 O(k + log n) 시간에 k개 결과를 얻을 수 있습니다.
💡 부모 포인터 대신 경로 스택을 사용할 때는 메모리 관리에 주의하세요. 스택 재사용으로 메모리 할당을 최소화할 수 있습니다.
💡 테스트 시 극단적인 경우를 체크하세요: 최솟값의 선행자(null), 최댓값의 후속자(null), 단일 노드 트리 등을 확인하면 엣지 케이스 버그를 방지할 수 있습니다.
3. 부모 포인터 없이 후속자 찾기
시작하며
여러분이 BST를 구현하다가 "부모 포인터를 추가하면 메모리가 너무 많이 쓰이는데, 다른 방법은 없을까?"라고 고민해본 적 있나요? 실제로 많은 트리 구현은 메모리 효율을 위해 부모 포인터를 생략합니다.
이 문제는 대규모 데이터를 다루는 시스템에서 특히 중요합니다. 백만 개의 노드가 있다면, 각 노드당 8바이트의 부모 포인터만 해도 8MB의 추가 메모리가 필요합니다.
모바일 환경이나 임베디드 시스템에서는 이것이 큰 부담이 될 수 있습니다. 바로 이럴 때 필요한 것이 부모 포인터 없이 후속자를 찾는 기법입니다.
탐색 경로를 스택에 저장하거나, 루트에서 다시 탐색하는 방법으로 동일한 기능을 구현할 수 있습니다.
개요
간단히 말해서, 이 기법은 루트에서 시작하여 목표 노드까지의 경로를 추적하면서 후속자 후보를 기록하는 방식입니다. 부모 포인터 대신 탐색 과정에서 필요한 정보를 수집합니다.
왜 이 방법이 필요한지 실무에서 생각해봅시다. 많은 표준 라이브러리의 트리 구현(예: Java의 TreeMap 내부 구조)은 메모리 효율을 위해 부모 포인터를 사용하지 않습니다.
그럼에도 불구하고 이터레이터와 범위 검색을 제공하는데, 바로 이런 기법을 사용하기 때문입니다. 기존에는 부모 포인터 없이는 조상을 찾을 수 없다고 생각했다면, 이제는 탐색 경로 정보를 활용하여 동일한 결과를 얻을 수 있습니다.
이 방법의 핵심은 목표 노드로 가는 경로에서 "마지막으로 왼쪽으로 내려간 노드"를 기억하는 것입니다. 그 노드가 바로 후속자 후보입니다.
시간 복잡도는 여전히 O(h)이지만, 공간은 O(1) (반복) 또는 O(h) (재귀/스택)입니다.
코드 예제
// 부모 포인터 없이 후속자 찾기 (반복 방식)
function findSuccessorWithoutParent(root, targetNode) {
let successor = null;
let current = root;
// 목표 노드를 찾으면서 후속자 후보를 추적
while (current !== null) {
if (targetNode.val < current.val) {
// 왼쪽으로 내려갈 때, 현재 노드가 후속자 후보
successor = current;
current = current.left;
} else if (targetNode.val > current.val) {
// 오른쪽으로 내려갈 때는 후속자 후보 업데이트 안 함
current = current.right;
} else {
// 목표 노드를 찾음
// 오른쪽 자식이 있으면 그 서브트리의 최솟값이 후속자
if (current.right !== null) {
successor = findMin(current.right);
}
// 오른쪽 자식이 없으면 이미 추적한 successor가 답
break;
}
}
return successor;
}
// 부모 포인터 없이 선행자 찾기 (대칭 구조)
function findPredecessorWithoutParent(root, targetNode) {
let predecessor = null;
let current = root;
while (current !== null) {
if (targetNode.val > current.val) {
// 오른쪽으로 내려갈 때, 현재 노드가 선행자 후보
predecessor = current;
current = current.right;
} else if (targetNode.val < current.val) {
current = current.left;
} else {
// 목표 노드를 찾음
if (current.left !== null) {
predecessor = findMax(current.left);
}
break;
}
}
return predecessor;
}
설명
이것이 하는 일: 이 알고리즘은 루트에서 시작하여 목표 노드까지 BST 탐색을 수행하면서, 동시에 후속자 정보를 수집합니다. 부모 포인터 없이도 조상 정보를 얻을 수 있는 영리한 방법입니다.
첫 번째로, 루트에서 시작하여 BST의 탐색 규칙을 따릅니다. 목표 값보다 현재 노드가 크면 왼쪽으로, 작으면 오른쪽으로 이동합니다.
핵심은 왼쪽으로 내려갈 때마다 현재 노드를 successor 변수에 저장한다는 것입니다. 왜냐하면 왼쪽으로 간다는 것은 "현재 노드가 목표 노드보다 크다"는 의미이고, 이는 후속자의 조건이기 때문입니다.
그 다음으로, 목표 노드를 찾았을 때 두 가지 경우를 처리합니다. 오른쪽 자식이 있다면, 그 서브트리의 최솟값이 진짜 후속자입니다.
이는 부모 포인터 방식의 "경우 1"과 동일합니다. 오른쪽 자식이 없다면, 탐색 과정에서 마지막으로 저장한 successor가 답입니다.
이것이 "경우 2"에 해당합니다. 이 방법의 우아함은 탐색과 후속자 찾기를 한 번에 처리한다는 점입니다.
별도로 조상을 거슬러 올라갈 필요가 없습니다. 경로를 내려가면서 필요한 정보(왼쪽으로 내려간 노드)를 자연스럽게 수집합니다.
여러분이 이 코드를 사용하면 메모리 효율적인 BST를 구현하면서도 완전한 기능을 제공할 수 있습니다. 특히 불변(immutable) 트리 구조나 함수형 프로그래밍 스타일에서 부모 포인터를 유지하기 어려울 때 이 방식이 매우 유용합니다.
시간 복잡도는 부모 포인터 방식과 동일한 O(h)이며, 공간 복잡도는 O(1)로 더 효율적입니다.
실전 팁
💡 이 방식은 노드 값으로 비교하므로, 중복 값이 있는 트리에서는 주의가 필요합니다. 노드 ID나 참조 비교를 추가로 사용하세요.
💡 재귀 방식으로도 구현 가능하지만, 반복 방식이 스택 오버플로우 위험이 없어 더 안전합니다. 깊은 트리에서는 반복을 선택하세요.
💡 이터레이터를 구현할 때는 경로 스택을 유지하면 다음 호출 시 O(1) 평균 시간을 달성할 수 있습니다. 매번 루트부터 탐색하지 마세요.
💡 성능 프로파일링을 해보면, 부모 포인터 방식이 더 빠를 것 같지만 캐시 지역성 측면에서는 이 방식이 유리할 수 있습니다. 실제 데이터로 측정하세요.
💡 값이 아닌 노드 객체를 비교해야 한다면, 탐색 경로 스택을 명시적으로 유지하는 방식으로 확장할 수 있습니다.
4. 중위 순회를 활용한 후속자 찾기
시작하며
여러분이 "BST의 후속자가 중위 순회에서 다음 노드라는 건 알겠는데, 그럼 중위 순회로 직접 찾으면 안 되나?"라고 생각해본 적 있나요? 실제로 많은 개발자들이 이 질문을 합니다.
이 접근법은 직관적이고 이해하기 쉽지만, 성능 측면에서는 trade-off가 있습니다. 모든 경우에 최선은 아니지만, 특정 상황에서는 매우 유용할 수 있습니다.
바로 이럴 때 필요한 것이 중위 순회 기반의 후속자 찾기입니다. 트리의 정렬된 순서를 직접 활용하여 다음 노드를 찾는 방법으로, 교육 목적이나 디버깅에 특히 좋습니다.
개요
간단히 말해서, 이 방법은 중위 순회(Inorder Traversal)를 수행하면서 목표 노드를 찾고, 그 다음에 방문하는 노드를 후속자로 반환하는 방식입니다. 트리의 정렬 순서를 문자 그대로 따라갑니다.
왜 이 방법을 알아야 할까요? 실무에서 전체 순회가 필요한 경우(예: 트리 검증, 디버깅 출력, 전체 데이터 내보내기)에는 이 방식이 더 간단하고 명확할 수 있습니다.
또한 BST 개념을 처음 배우는 사람들에게 후속자의 의미를 설명할 때 매우 유용합니다. 기존의 트리 순회 방식을 그대로 사용하되, 목표 노드를 찾은 후의 다음 노드를 특별히 추적하면 됩니다.
이 방법의 특징은 단순함과 명확함입니다. 복잡한 경우 분석이나 포인터 조작이 필요 없으며, 중위 순회 로직만 이해하면 됩니다.
하지만 시간 복잡도는 O(n)이므로, 한 번의 후속자 탐색에는 비효율적입니다. 대신 여러 노드의 후속자를 한 번에 찾거나, 전체 순서를 배열로 만들어 놓는 경우에 유용합니다.
코드 예제
// 중위 순회로 후속자 찾기 (재귀 방식)
function findSuccessorInorder(root, targetNode) {
let found = false;
let successor = null;
function inorderTraversal(node) {
if (node === null || successor !== null) {
return;
}
// 왼쪽 서브트리 방문
inorderTraversal(node.left);
// 현재 노드 처리
if (found) {
// 목표 노드를 이미 찾았으면, 현재 노드가 후속자
successor = node;
return;
}
if (node === targetNode) {
found = true;
}
// 오른쪽 서브트리 방문
inorderTraversal(node.right);
}
inorderTraversal(root);
return successor;
}
// 모든 노드의 후속자를 효율적으로 찾기
function getAllSuccessors(root) {
const inorderList = [];
const successorMap = new Map();
// 중위 순회로 정렬된 노드 리스트 생성
function inorder(node) {
if (node === null) return;
inorder(node.left);
inorderList.push(node);
inorder(node.right);
}
inorder(root);
// 각 노드의 후속자를 맵에 저장
for (let i = 0; i < inorderList.length - 1; i++) {
successorMap.set(inorderList[i], inorderList[i + 1]);
}
// 마지막 노드는 후속자가 없음
successorMap.set(inorderList[inorderList.length - 1], null);
return successorMap;
}
설명
이것이 하는 일: 이 알고리즘은 BST를 중위 순회(왼쪽-루트-오른쪽)하면서 목표 노드를 찾고, 그 직후에 방문하는 노드를 후속자로 식별합니다. 트리의 정렬 순서를 직접적으로 활용하는 가장 직관적인 방법입니다.
첫 번째로, 중위 순회를 시작합니다. 이 순회 방식은 BST를 오름차순으로 방문하므로, 순회 순서 자체가 정렬된 시퀀스입니다.
found 플래그를 사용하여 목표 노드를 찾았는지 추적합니다. 목표 노드를 만나면 플래그를 true로 설정합니다.
그 다음으로, 목표 노드를 찾은 후(found = true) 처음으로 방문하는 노드가 바로 후속자입니다. successor 변수에 저장하고 즉시 순회를 종료합니다.
조기 종료는 불필요한 순회를 막아 실제 성능을 약간 개선합니다. 이 방법은 최악의 경우 전체 트리를 순회해야 하므로 O(n) 시간이 걸립니다.
하지만 코드가 매우 단순하고 버그가 적으며, 이해하기 쉽다는 장점이 있습니다. 특히 BST 개념을 학습할 때나, 작은 트리에서 디버깅할 때 유용합니다.
여러분이 이 코드를 사용하면 복잡한 포인터 조작 없이도 정확한 결과를 얻을 수 있습니다. 더 나아가, getAllSuccessors 함수처럼 한 번의 순회로 모든 노드의 후속자를 미리 계산해두면, 이후 조회는 O(1)에 가능합니다.
읽기가 많은 시스템에서 전처리 방식으로 활용하면 효과적입니다. 트리가 자주 변경되지 않고, 여러 번의 후속자 조회가 필요한 상황에서 특히 유용합니다.
실전 팁
💡 교육용 코드나 프로토타입에서는 이 방식이 가장 이해하기 쉽습니다. 성능 최적화는 나중에 하세요.
💡 전체 순회가 필요한 경우(예: 전체 데이터 검증, 통계 계산), 순회 중에 후속자 관계를 함께 처리하면 추가 비용이 거의 없습니다.
💡 반복적 중위 순회(스택 사용)로 구현하면 메모리 사용을 더 잘 제어할 수 있습니다. 재귀보다 스택 오버플로우 위험이 적습니다.
💡 이 방식으로 후속자/선행자 맵을 미리 만들어두면, 이후 O(1) 조회가 가능하여 읽기 중심 워크로드에 적합합니다. 쓰기 시에만 맵을 갱신하세요.
💡 디버깅 시 이 방법으로 찾은 후속자와 최적화된 알고리즘의 결과를 비교하면, 구현 검증에 도움이 됩니다.
5. 실전 활용: 범위 쿼리 구현
시작하며
여러분이 전자상거래 사이트에서 "가격이 10,000원에서 50,000원 사이인 모든 상품"을 찾아야 하는 상황을 생각해보세요. 또는 로그 시스템에서 "오전 9시부터 11시 사이의 모든 이벤트"를 검색해야 할 때 말이죠.
이런 범위 검색은 실무에서 가장 흔한 쿼리 패턴 중 하나입니다. 단순히 배열을 순회하면 O(n)이 걸리지만, BST와 후속자 개념을 활용하면 O(k + log n)으로 개선할 수 있습니다 (k는 결과 개수).
바로 이럴 때 필요한 것이 후속자를 활용한 범위 쿼리입니다. 시작점을 찾고, 후속자를 따라가며 범위 내의 모든 값을 효율적으로 수집하는 기법입니다.
개요
간단히 말해서, 범위 쿼리는 [min, max] 구간에 속하는 모든 노드를 찾는 연산입니다. BST에서는 시작점을 O(log n)에 찾고, 후속자를 따라 O(k)에 결과를 수집할 수 있습니다.
왜 이 기법이 중요한지 실무 관점에서 살펴봅시다. 데이터베이스의 B-Tree 인덱스, 파일 시스템의 디렉토리 구조, 메모리 관리의 주소 범위 검색 등 수많은 시스템이 이 패턴을 사용합니다.
NoSQL 데이터베이스의 스캔 연산도 본질적으로 동일한 방식입니다. 기존에 선형 탐색으로 O(n)을 감수했다면, 이제는 BST를 사용하여 훨씬 빠르게 처리할 수 있습니다.
특히 범위가 작고 데이터가 클수록 성능 차이가 극적입니다. 이 방법의 핵심 단계는 세 가지입니다: (1) min 이상인 첫 번째 노드를 찾습니다 (시작점).
(2) 후속자를 반복적으로 따라가며 max 이하인 노드들을 수집합니다. (3) max를 초과하면 중단합니다.
이렇게 하면 불필요한 노드를 전혀 방문하지 않습니다.
코드 예제
// min 이상의 첫 번째 노드 찾기 (하한값)
function findLowerBound(root, min) {
let result = null;
let current = root;
while (current !== null) {
if (current.val >= min) {
// min 이상이면 후보로 저장하고 더 작은 값 탐색
result = current;
current = current.left;
} else {
// min 미만이면 오른쪽으로
current = current.right;
}
}
return result;
}
// 범위 쿼리: [min, max] 사이의 모든 값 찾기
function rangeQuery(root, min, max) {
const result = [];
// 시작점 찾기: min 이상의 첫 번째 노드
let current = findLowerBound(root, min);
// 후속자를 따라가며 max 이하인 값들 수집
while (current !== null && current.val <= max) {
result.push(current.val);
current = findSuccessorWithoutParent(root, current);
}
return result;
}
// 실전 예제: 범위 내 노드 개수 세기
function countInRange(root, min, max) {
let count = 0;
let current = findLowerBound(root, min);
while (current !== null && current.val <= max) {
count++;
current = findSuccessorWithoutParent(root, current);
}
return count;
}
// 범위 검색 최적화: 재귀적으로 불필요한 서브트리 제외
function rangeQueryOptimized(node, min, max, result = []) {
if (node === null) return result;
// 현재 노드가 min보다 크면 왼쪽 서브트리 탐색
if (node.val > min) {
rangeQueryOptimized(node.left, min, max, result);
}
// 현재 노드가 범위 내에 있으면 결과에 추가
if (node.val >= min && node.val <= max) {
result.push(node.val);
}
// 현재 노드가 max보다 작으면 오른쪽 서브트리 탐색
if (node.val < max) {
rangeQueryOptimized(node.right, min, max, result);
}
return result;
}
설명
이것이 하는 일: 범위 쿼리 알고리즘은 BST의 정렬 특성과 후속자 연산을 결합하여, 특정 범위에 속하는 모든 값을 효율적으로 찾습니다. 불필요한 노드를 건너뛰어 성능을 최적화합니다.
첫 번째로, findLowerBound 함수로 min 이상인 첫 번째 노드를 찾습니다. 이는 이진 탐색과 유사하게 작동하여 O(log n) 시간이 걸립니다.
핵심은 min 이상인 값을 만날 때마다 후보로 저장하고 더 작은 값이 있는지 왼쪽을 계속 탐색하는 것입니다. 이렇게 하면 정확히 min 이상의 최솟값을 찾을 수 있습니다.
그 다음으로, 찾은 시작점부터 후속자를 반복적으로 따라갑니다. 각 노드가 max 이하인지 확인하고, 맞다면 결과에 추가합니다.
max를 초과하는 순간 즉시 중단하여 불필요한 탐색을 방지합니다. 이 과정은 정확히 k개의 결과 노드만 방문하므로 O(k)입니다.
rangeQueryOptimized 함수는 다른 접근법으로, 재귀적으로 트리를 순회하되 범위 밖의 서브트리는 완전히 건너뜁니다. 예를 들어, 현재 노드가 min보다 작으면 왼쪽 서브트리를 아예 탐색하지 않습니다.
이 방식도 O(k + log n)이지만, 후속자 함수 호출이 없어 실제로는 더 빠를 수 있습니다. 여러분이 이 코드를 사용하면 대규모 데이터셋에서도 빠른 범위 검색이 가능합니다.
예를 들어, 백만 개의 데이터에서 100개를 찾는 경우, 선형 탐색은 백만 번 비교하지만 이 방법은 약 120번(log₂(1,000,000) ≈ 20 + 100)만 하면 됩니다. 실무에서는 날짜 범위 검색, 가격 필터, 점수 범위 조회 등에 즉시 적용할 수 있으며, 페이지네이션과 결합하면 더욱 강력합니다.
실전 팁
💡 후속자를 반복 호출하는 방식은 구현이 간단하지만, 재귀적 범위 쿼리가 실제로는 더 빠릅니다. 성능이 중요하면 최적화 버전을 사용하세요.
💡 범위가 매우 크거나 전체 트리에 가까우면 단순 중위 순회가 오히려 빠를 수 있습니다. 범위 크기를 확인하여 전략을 선택하세요.
💡 페이지네이션 구현 시 시작 노드를 캐싱하고 offset만큼 후속자를 건너뛰면 효율적입니다. 매번 처음부터 찾지 마세요.
💡 동시성 환경에서는 범위 검색 중 트리가 변경될 수 있습니다. 읽기 잠금이나 스냅샷 격리를 고려하세요.
💡 결과를 스트림으로 반환하면 메모리를 절약할 수 있습니다. 모든 결과를 배열에 담지 말고 이터레이터 패턴을 사용하세요.
6. 노드 삭제와 후속자/선행자 활용
시작하며
여러분이 BST에서 노드를 삭제하려는데, "자식이 둘 다 있는 노드는 어떻게 삭제하지?"라고 막막해한 경험이 있나요? 이는 BST 연산 중 가장 까다로운 부분입니다.
이 문제는 트리의 BST 속성을 유지하면서 노드를 제거해야 하므로 복잡합니다. 단순히 노드를 지우면 트리가 망가지고, 자식들을 어떻게 재배치할지 결정해야 합니다.
바로 이럴 때 필요한 것이 후속자나 선행자를 활용한 삭제 기법입니다. 삭제할 노드를 후속자나 선행자 값으로 대체하면, BST 속성을 자연스럽게 유지할 수 있습니다.
개요
간단히 말해서, 자식이 둘인 노드를 삭제할 때는 후속자나 선행자의 값으로 덮어쓰고, 그 후속자/선행자 노드를 대신 삭제하는 방식입니다. 이렇게 하면 BST 속성이 자동으로 유지됩니다.
왜 이 방법이 작동하는지 생각해봅시다. 후속자는 현재 노드보다 크면서 가장 작은 값이므로, 왼쪽 서브트리의 모든 값보다 크고 오른쪽 서브트리의 대부분보다 작습니다.
따라서 후속자로 대체해도 BST 속성이 깨지지 않습니다. 선행자도 마찬가지 논리입니다.
기존에는 복잡한 케이스 분석과 포인터 조작이 필요했지만, 이제는 후속자/선행자 개념만 이해하면 삭제를 간단하게 구현할 수 있습니다. 이 방법의 핵심 통찰은 "후속자/선행자는 최대 하나의 자식만 가진다"는 점입니다.
후속자는 오른쪽 서브트리의 최솟값이므로 왼쪽 자식이 없고, 선행자는 왼쪽 서브트리의 최댓값이므로 오른쪽 자식이 없습니다. 따라서 이들을 삭제하는 것은 간단한 케이스(자식 0개 또는 1개)로 귀결됩니다.
코드 예제
// BST에서 노드 삭제 (후속자 활용)
function deleteNode(root, key) {
if (root === null) return null;
// 삭제할 노드 찾기
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
// 삭제할 노드를 찾음
// 경우 1: 리프 노드 (자식 없음)
if (root.left === null && root.right === null) {
return null;
}
// 경우 2: 자식이 하나만 있는 경우
if (root.left === null) {
return root.right;
}
if (root.right === null) {
return root.left;
}
// 경우 3: 자식이 둘 다 있는 경우
// 후속자(오른쪽 서브트리의 최솟값)를 찾아서 대체
const successor = findMin(root.right);
root.val = successor.val; // 값을 복사
// 후속자 노드를 삭제 (재귀적으로)
root.right = deleteNode(root.right, successor.val);
}
return root;
}
// 선행자를 사용한 삭제 (대안 방법)
function deleteNodeWithPredecessor(root, key) {
if (root === null) return null;
if (key < root.val) {
root.left = deleteNodeWithPredecessor(root.left, key);
} else if (key > root.val) {
root.right = deleteNodeWithPredecessor(root.right, key);
} else {
// 자식이 0개 또는 1개인 경우는 동일
if (root.left === null) return root.right;
if (root.right === null) return root.left;
// 자식이 둘 다 있는 경우: 선행자 사용
const predecessor = findMax(root.left);
root.val = predecessor.val;
root.left = deleteNodeWithPredecessor(root.left, predecessor.val);
}
return root;
}
// 실전 예제: 여러 노드 삭제하기
function deleteMultiple(root, keysToDelete) {
// 삭제할 키들을 정렬 (최적화)
keysToDelete.sort((a, b) => a - b);
for (const key of keysToDelete) {
root = deleteNode(root, key);
}
return root;
}
설명
이것이 하는 일: 노드 삭제 알고리즘은 세 가지 경우를 처리합니다. 자식이 없거나 하나인 경우는 간단하지만, 자식이 둘인 경우는 후속자나 선행자를 활용하여 BST 속성을 유지하면서 삭제합니다.
첫 번째로, 삭제할 노드를 찾습니다. BST 탐색과 동일하게 값을 비교하며 재귀적으로 내려갑니다.
노드를 찾으면 자식 개수에 따라 다르게 처리합니다. 자식이 없으면(리프 노드) 단순히 null을 반환하고, 자식이 하나면 그 자식으로 대체합니다.
그 다음으로, 가장 복잡한 경우인 자식이 둘인 상황을 처리합니다. 여기서 후속자 개념이 빛을 발합니다.
오른쪽 서브트리에서 최솟값(후속자)을 찾아 그 값을 현재 노드에 복사합니다. 이렇게 하면 현재 노드가 "논리적으로 삭제"됩니다.
왜냐하면 후속자 값이 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작거나 같기 때문입니다. 마지막으로, 실제 후속자 노드를 물리적으로 삭제합니다.
후속자는 오른쪽 서브트리의 최솟값이므로 왼쪽 자식이 없습니다. 따라서 오른쪽 자식만 있거나 아예 없는 간단한 경우가 되어, 쉽게 삭제할 수 있습니다.
이것이 후속자를 사용하는 핵심 이유입니다. 여러분이 이 코드를 사용하면 BST의 모든 삭제 연산을 O(h) 시간에 안전하게 수행할 수 있습니다.
후속자와 선행자 중 어느 것을 사용해도 정확성은 동일하지만, 트리의 균형을 고려하면 교대로 사용하는 것이 좋습니다. 실무에서는 데이터베이스 레코드 삭제, 캐시 엔트리 제거, 우선순위 큐 구현 등에 이 패턴이 광범위하게 사용됩니다.
삭제 후에도 BST 속성이 완벽히 유지되므로 다른 모든 연산(검색, 삽입, 범위 쿼리)이 정상적으로 작동합니다.
실전 팁
💡 후속자와 선행자를 번갈아 사용하면 트리의 균형을 더 잘 유지할 수 있습니다. 항상 한쪽만 사용하면 불균형이 심화됩니다.
💡 반복적(iterative) 삭제 구현도 가능하지만 재귀가 훨씬 간결합니다. 스택 오버플로우가 걱정되는 경우에만 반복을 고려하세요.
💡 노드 값 대신 노드 객체를 교체하려면 부모 포인터를 업데이트해야 합니다. 값 복사 방식이 더 간단하지만 메모리는 재활용되지 않습니다.
💡 대량 삭제 시 삭제할 키를 정렬하고 한 번의 순회로 처리하면 효율적입니다. 무작위 순서보다 빠릅니다.
💡 삭제 후 트리 높이가 log n을 초과하면 균형 잡기(AVL 회전, Red-Black 조정)를 고려하세요. 일반 BST는 불균형해질 수 있습니다.
7. Morris 순회로 후속자 찾기 (상수 공간)
시작하며
여러분이 메모리가 극도로 제한된 임베디드 시스템에서 트리 순회를 구현해야 한다면 어떻게 하시겠어요? 재귀는 스택을 사용하고, 반복 방식도 명시적 스택이 필요하여 O(h) 공간이 듭니다.
이 문제는 IoT 기기, 마이크로컨트롤러, 또는 매우 큰 트리를 다루는 시스템에서 심각합니다. 메모리가 부족하거나, 수백만 노드의 트리에서 O(h)도 부담될 수 있습니다.
바로 이럴 때 필요한 것이 Morris 순회 기법입니다. 임시로 트리 구조를 변경했다가 복원하는 방식으로, O(1) 공간에 중위 순회와 후속자 찾기가 가능합니다.
개요
간단히 말해서, Morris 순회는 트리의 빈 포인터를 임시로 활용하여 부모로 돌아가는 "스레드"를 만드는 기법입니다. 이를 통해 재귀나 스택 없이도 순회할 수 있습니다.
왜 이 고급 기법을 알아야 할까요? 실무에서 메모리 제약이 있는 환경이나, 트리가 매우 깊어서 스택 오버플로우가 걱정되는 경우에 유용합니다.
또한 알고리즘 인터뷰에서 "O(1) 공간으로 트리를 순회하라"는 문제가 나올 때 필수 지식입니다. 기존에는 순회에 항상 O(h) 공간이 필요하다고 생각했다면, 이제는 트리 구조 자체를 영리하게 활용하여 상수 공간으로 해결할 수 있습니다.
이 방법의 핵심 아이디어는 "Threaded Binary Tree" 개념입니다. 각 노드의 오른쪽 자식이 없는 경우, 그 null 포인터를 후속자를 가리키도록 임시로 변경합니다.
순회가 끝나면 원래대로 복원하여 트리를 손상시키지 않습니다. 시간 복잡도는 여전히 O(n)이지만, 공간은 O(1)입니다.
코드 예제
// Morris 중위 순회 (O(1) 공간)
function morrisInorderTraversal(root) {
const result = [];
let current = root;
while (current !== null) {
if (current.left === null) {
// 왼쪽 자식이 없으면 현재 노드 처리 후 오른쪽으로
result.push(current.val);
current = current.right;
} else {
// 왼쪽 서브트리의 최우측 노드(predecessor)를 찾기
let predecessor = current.left;
while (predecessor.right !== null &&
predecessor.right !== current) {
predecessor = predecessor.right;
}
if (predecessor.right === null) {
// 스레드 생성: predecessor가 current를 가리키게
predecessor.right = current;
current = current.left;
} else {
// 스레드가 이미 있음: 왼쪽 서브트리 순회 완료
// 스레드 제거하고 현재 노드 처리
predecessor.right = null;
result.push(current.val);
current = current.right;
}
}
}
return result;
}
// Morris 방식으로 후속자 찾기
function findSuccessorMorris(root, targetNode) {
let found = false;
let successor = null;
let current = root;
while (current !== null && successor === null) {
if (current.left === null) {
if (found) {
successor = current;
} else if (current === targetNode) {
found = true;
}
current = current.right;
} else {
let predecessor = current.left;
while (predecessor.right !== null &&
predecessor.right !== current) {
predecessor = predecessor.right;
}
if (predecessor.right === null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
if (found) {
successor = current;
} else if (current === targetNode) {
found = true;
}
current = current.right;
}
}
}
return successor;
}
설명
이것이 하는 일: Morris 순회는 트리 노드의 사용되지 않는 right 포인터를 임시로 부모 노드를 가리키도록 변경하여, 재귀나 스택 없이 트리를 순회합니다. 순회 후에는 트리를 원래 상태로 복원합니다.
첫 번째로, 현재 노드의 왼쪽 자식 유무를 확인합니다. 왼쪽 자식이 없다면 현재 노드를 처리하고 오른쪽으로 이동합니다.
이는 일반적인 중위 순회와 동일합니다. 하지만 왼쪽 자식이 있는 경우가 흥미롭습니다.
그 다음으로, 왼쪽 서브트리에서 선행자(최우측 노드)를 찾습니다. 이 노드의 right 포인터는 원래 null이거나, 이미 스레드가 생성되어 현재 노드를 가리킵니다.
null이라면 스레드를 생성합니다. 즉, predecessor.right = current로 설정하여, 왼쪽 서브트리 순회 후 현재 노드로 돌아올 수 있게 합니다.
스레드가 이미 존재한다면, 이는 왼쪽 서브트리를 이미 방문했다는 의미입니다. 이때 스레드를 제거하여 트리를 원래대로 복원하고, 현재 노드를 처리한 후 오른쪽으로 이동합니다.
이 과정이 재귀나 스택 없이 부모로 돌아가는 핵심 메커니즘입니다. 여러분이 이 코드를 사용하면 극도로 메모리 효율적인 트리 순회가 가능합니다.
각 간선을 최대 두 번 방문하므로(스레드 생성 시 한 번, 제거 시 한 번) 시간 복잡도는 O(n)이지만, 추가 공간은 단지 몇 개의 포인터 변수뿐입니다. 임베디드 시스템, 매우 큰 트리, 또는 깊이가 수천 수만인 불균형 트리에서 특히 유용합니다.
다만 코드가 복잡하고 이해하기 어려우므로, 실무에서는 정말 필요한 경우에만 사용하세요. 대부분의 경우 일반적인 순회로 충분합니다.
실전 팁
💡 Morris 순회는 동시성 환경에서 안전하지 않습니다. 트리를 일시적으로 변경하므로 단일 스레드에서만 사용하세요.
💡 이 기법은 코딩 인터뷰에서 인상적이지만, 실무 코드에는 가독성과 유지보수성 때문에 권장되지 않습니다. 주석을 충분히 달아야 합니다.
💡 전위 순회(Preorder)도 Morris 방식으로 구현 가능하지만, 후위 순회(Postorder)는 훨씬 복잡합니다. 필요성을 먼저 평가하세요.
💡 디버깅 시 스레드가 제대로 제거되는지 확인하세요. 버그가 있으면 트리가 손상되어 무한 루프나 잘못된 결과가 나올 수 있습니다.
💡 성능 프로파일링을 해보면, 캐시 지역성이 나쁘고 분기 예측이 어려워 실제로는 재귀보다 느릴 수 있습니다. 메모리가 정말 부족할 때만 사용하세요.
8. 중복 값이 있는 BST에서 후속자 처리
시작하며
여러분이 타임스탬프로 이벤트를 저장하는 시스템을 만들 때, "동일한 시각에 여러 이벤트가 발생하면 어떻게 하지?"라고 고민해본 적 있나요? 실무에서는 중복 값을 허용하는 BST가 종종 필요합니다.
이 문제는 점수가 같은 게임 플레이어, 동일한 가격의 상품, 같은 우선순위의 작업 등 실제 데이터에서 흔히 발생합니다. 표준 BST는 중복을 허용하지 않는다고 배웠지만, 약간의 변형으로 처리할 수 있습니다.
바로 이럴 때 필요한 것이 중복 값을 고려한 후속자 찾기입니다. BST 속성을 유지하면서 중복 값을 저장하고, 정확히 다음 값을 찾는 기법입니다.
개요
간단히 말해서, 중복을 허용하는 BST는 두 가지 방식으로 구현됩니다: (1) 같은 값은 오른쪽으로 저장하거나, (2) 각 노드에 카운터나 리스트를 두는 방법입니다. 후속자 정의도 약간 달라집니다.
왜 이 개념이 중요한지 실무에서 살펴봅시다. 데이터베이스의 non-unique 인덱스, 멀티맵 자료구조, 우선순위 큐의 동일 우선순위 처리 등에서 필수적입니다.
중복을 무시하면 데이터가 손실되거나 잘못된 결과가 나올 수 있습니다. 기존의 고유 값 BST에서는 후속자가 명확했지만, 중복이 있으면 "다음"의 의미를 재정의해야 합니다.
"같은 값의 다음 항목"인지, "진짜 다음 큰 값"인지 명확히 해야 합니다. 이 방법의 핵심은 BST 규칙을 약간 수정하는 것입니다.
일반적으로 "같은 값은 오른쪽"으로 정하면 (val <= current.val → left, val > current.val → right) 중위 순회가 비감소 수열을 만듭니다. 후속자는 중위 순회에서 다음 노드이며, 같은 값일 수도 있습니다.
코드 예제
// 중복을 허용하는 BST 삽입 (같은 값은 오른쪽으로)
function insertWithDuplicates(root, val) {
if (root === null) {
return new TreeNode(val);
}
// 같은 값을 포함하여 크거나 같으면 오른쪽으로
if (val >= root.val) {
root.right = insertWithDuplicates(root.right, val);
} else {
root.left = insertWithDuplicates(root.left, val);
}
return root;
}
// 중복 허용 BST에서 후속자 찾기
// 현재 값과 같거나 큰 다음 값
function findSuccessorWithDuplicates(root, node) {
// 오른쪽 자식이 있으면 그쪽의 최솟값
if (node.right !== null) {
return findMin(node.right);
}
// 오른쪽 자식이 없으면 조상 탐색
let successor = null;
let current = root;
while (current !== null) {
if (node.val < current.val) {
successor = current;
current = current.left;
} else {
// node.val >= current.val
current = current.right;
}
}
return successor;
}
// 진짜 다음 큰 값 찾기 (같은 값은 건너뛰기)
function findNextLargerValue(root, node) {
let successor = findSuccessorWithDuplicates(root, node);
// 같은 값을 건너뛰고 진짜 큰 값 찾기
while (successor !== null && successor.val === node.val) {
successor = findSuccessorWithDuplicates(root, successor);
}
return successor;
}
// 카운터 방식: 각 노드가 중복 개수를 저장
class TreeNodeWithCount {
constructor(val) {
this.val = val;
this.count = 1; // 이 값의 개수
this.left = null;
this.right = null;
}
}
function insertWithCount(root, val) {
if (root === null) {
return new TreeNodeWithCount(val);
}
if (val === root.val) {
root.count++; // 중복 값은 카운터 증가
} else if (val < root.val) {
root.left = insertWithCount(root.left, val);
} else {
root.right = insertWithCount(root.right, val);
}
return root;
}
설명
이것이 하는 일: 중복 허용 BST 알고리즘은 동일한 값의 여러 인스턴스를 저장하면서도 효율적인 탐색을 유지합니다. 후속자 개념은 "중위 순회의 다음 노드"로 일관되게 적용되지만, 같은 값이 나올 수 있다는 점이 다릅니다.
첫 번째로, 삽입 시 중복을 어떻게 처리할지 정책을 정합니다. "같은 값은 오른쪽"으로 규칙을 정하면, 중위 순회 결과가 비감소 수열(non-decreasing)이 됩니다.
예를 들어, [3, 5, 5, 5, 7]처럼 같은 값이 연속으로 나타납니다. 이 규칙은 일관성이 있고 구현이 간단합니다.
그 다음으로, 후속자를 찾을 때 두 가지 의미를 구분합니다. (1) "중위 순회의 다음 노드"는 같은 값일 수도 있습니다.
예를 들어, 값 5의 후속자가 또 다른 5일 수 있습니다. (2) "진짜 다음 큰 값"은 같은 값을 모두 건너뛰고 처음으로 큰 값을 찾습니다.
어떤 의미가 필요한지는 애플리케이션 요구사항에 따라 다릅니다. 카운터 방식은 메모리를 절약하는 대안입니다.
같은 값을 여러 노드로 저장하지 않고, 하나의 노드에 count 필드를 두어 개수를 기록합니다. 이 경우 후속자는 항상 다른 값을 가진 노드입니다.
범위 쿼리 시 count만큼 결과에 추가하면 됩니다. 메모리는 효율적이지만, 삭제가 복잡해지고 동일 값의 순서를 구분할 수 없다는 단점이 있습니다.
여러분이 이 코드를 사용하면 실제 데이터의 중복성을 정확히 반영할 수 있습니다. 예를 들어, 점수 리더보드에서 동점자를 모두 저장하거나, 로그 시스템에서 동일 타임스탬프 이벤트를 관리할 수 있습니다.
정책을 명확히 문서화하고, 테스트 케이스에 중복 값을 포함하여 엣지 케이스를 검증하세요. 실무에서는 요구사항에 따라 적절한 방식(별도 노드 vs 카운터)을 선택하면 됩니다.
실전 팁
💡 중복 처리 정책을 프로젝트 초기에 명확히 정하고 문서화하세요. 나중에 바꾸면 전체 코드를 수정해야 합니다.
💡 카운터 방식은 메모리 효율적이지만, 동일 값의 개별 항목을 구분할 수 없습니다. 각 항목이 고유한 속성(ID, 타임스탬프 등)을 가지면 별도 노드가 필요합니다.
💡 중복이 많은 데이터에서는 카운터 방식이 트리 높이를 낮춰 성능을 개선합니다. 동일 값이 1000개면 높이를 10 줄일 수 있습니다.
💡 범위 쿼리 시 카운터를 고려하여 결과 개수를 계산하세요. 단순히 노드 개수가 아니라 sum(count)입니다.
💡 삭제 시 카운터를 감소시키고, 0이 되면 노드를 제거합니다. 음수가 되지 않도록 검증 로직을 추가하세요.