이미지 로딩 중...
AI Generated
2025. 11. 7. · 5 Views
중위 순회로 BST 정렬하기 완벽 가이드
이진 탐색 트리(BST)의 중위 순회를 통해 데이터를 정렬된 순서로 가져오는 방법을 배웁니다. 트리 구조의 특성을 활용하여 효율적인 정렬과 검색을 구현하는 실전 가이드입니다.
목차
1. 이진_탐색_트리_기본
시작하며
여러분이 수천 개의 사용자 데이터를 관리하는 시스템을 개발할 때, 단순히 배열에 저장하고 정렬하면 될까요? 데이터를 추가하거나 삭제할 때마다 전체를 다시 정렬하는 것은 너무 비효율적입니다.
실제 서비스에서는 데이터가 실시간으로 추가되고 삭제됩니다. 예를 들어 게임 랭킹 시스템에서 사용자 점수가 계속 업데이트되는 상황을 생각해보세요.
매번 전체 데이터를 정렬하면 성능이 급격히 저하됩니다. 바로 이럴 때 필요한 것이 이진 탐색 트리(BST)입니다.
BST는 데이터를 삽입하는 순간부터 정렬된 상태를 유지하며, 검색과 수정도 효율적으로 처리할 수 있습니다.
개요
간단히 말해서, 이진 탐색 트리는 각 노드가 최대 2개의 자식을 가지며, 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 값을 갖는 트리 구조입니다. 실무에서 BST가 필요한 이유는 명확합니다.
O(log n)의 시간 복잡도로 검색, 삽입, 삭제를 수행할 수 있어 대규모 데이터를 다룰 때 매우 효율적입니다. 데이터베이스 인덱스, 파일 시스템, 메모리 관리 등 다양한 곳에서 활용됩니다.
기존에는 정렬된 배열을 유지하기 위해 삽입 시 O(n) 시간이 걸렸다면, BST를 사용하면 O(log n) 시간으로 단축됩니다. 10만 개의 데이터에서 이 차이는 엄청나게 큽니다.
BST의 핵심 특징은 세 가지입니다. 첫째, 구조 자체가 정렬 속성을 유지합니다.
둘째, 균형 잡힌 트리에서는 모든 연산이 로그 시간에 처리됩니다. 셋째, 중위 순회를 통해 정렬된 순서로 데이터를 가져올 수 있습니다.
이러한 특징들이 BST를 강력한 데이터 구조로 만듭니다.
코드 예제
// BST 노드 클래스 정의
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// BST 클래스 구현
class BinarySearchTree {
constructor() {
this.root = null;
}
// 값 삽입: 트리의 정렬 속성 유지
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value < current.value) {
// 왼쪽으로: 현재 노드보다 작은 값
if (current.left === null) {
current.left = newNode;
return this;
}
current = current.left;
} else {
// 오른쪽으로: 현재 노드보다 큰 값
if (current.right === null) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
}
설명
이것이 하는 일: 이진 탐색 트리는 데이터를 효율적으로 저장하고 검색할 수 있는 계층적 구조를 만듭니다. 각 노드는 최대 두 개의 자식을 가지며, 특정 규칙에 따라 데이터를 배치합니다.
첫 번째로, TreeNode 클래스는 트리의 각 노드를 표현합니다. value는 노드가 저장하는 실제 데이터이고, left와 right는 각각 왼쪽과 오른쪽 자식 노드를 가리킵니다.
이 단순한 구조가 복잡한 트리를 만드는 기본 단위입니다. 그 다음으로, BinarySearchTree 클래스가 전체 트리를 관리합니다.
root 속성은 트리의 최상위 노드를 가리키며, 이것이 전체 트리의 진입점이 됩니다. insert 메서드는 새로운 값을 올바른 위치에 삽입하는 핵심 로직입니다.
insert 메서드의 동작을 자세히 보면, 먼저 루트가 비어있는지 확인합니다. 비어있다면 새 노드를 루트로 설정하고 끝납니다.
그렇지 않으면 현재 노드와 삽입할 값을 비교하며 트리를 내려갑니다. 값이 작으면 왼쪽으로, 크면 오른쪽으로 이동하며 빈 자리를 찾을 때까지 반복합니다.
마지막으로, 이 과정이 완료되면 트리는 자동으로 정렬된 상태를 유지합니다. 예를 들어 [50, 30, 70, 20, 40]을 순서대로 삽입하면, 50이 루트가 되고 30은 왼쪽, 70은 오른쪽에 배치됩니다.
20은 30의 왼쪽, 40은 30의 오른쪽에 놓입니다. 여러분이 이 코드를 사용하면 검색, 삽입, 삭제 작업을 평균 O(log n) 시간에 수행할 수 있습니다.
데이터가 많아질수록 선형 자료구조 대비 성능 이점이 극명하게 드러납니다. 또한 트리 구조 특성상 범위 검색, 최솟값/최댓값 찾기 등의 연산도 효율적으로 처리할 수 있습니다.
실전 팁
💡 BST를 사용할 때는 항상 트리의 균형을 고려하세요. 최악의 경우 한쪽으로 치우친 트리가 되어 O(n) 시간이 걸릴 수 있습니다. 실무에서는 AVL 트리나 Red-Black 트리 같은 자가 균형 트리를 사용하는 것이 안전합니다.
💡 중복 값 처리 전략을 명확히 하세요. 위 코드는 중복을 허용하지 않지만, 실무에서는 카운터를 추가하거나 같은 값을 오른쪽에 배치하는 방식으로 처리할 수 있습니다.
💡 값 비교 시 일관된 비교 함수를 사용하세요. 숫자가 아닌 객체를 저장할 때는 생성자에서 비교 함수를 받아 사용하면 유연성이 높아집니다.
💡 삽입 후 트리 높이를 추적하면 성능 모니터링에 유용합니다. 높이가 log(n)을 크게 벗어나면 리밸런싱이 필요하다는 신호입니다.
2. 중위_순회_개념
시작하며
여러분이 BST에 저장된 데이터를 정렬된 순서로 출력해야 하는 상황을 생각해보세요. 트리 구조는 계층적으로 퍼져있어서 어떤 순서로 방문해야 할지 막막할 수 있습니다.
실제로 많은 개발자들이 트리 순회에서 혼란을 겪습니다. 전위, 중위, 후위 순회의 차이를 이해하지 못하면 원하는 결과를 얻을 수 없습니다.
특히 BST에서는 순회 방법에 따라 결과가 완전히 달라집니다. 바로 이럴 때 필요한 것이 중위 순회(In-order Traversal)입니다.
BST에서 중위 순회를 사용하면 자동으로 오름차순 정렬된 결과를 얻을 수 있습니다.
개요
간단히 말해서, 중위 순회는 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 트리를 방문하는 방법입니다. 이 순회 방법이 BST에서 특별한 이유는 트리의 정렬 속성과 완벽하게 맞아떨어지기 때문입니다.
BST는 왼쪽에 작은 값, 오른쪽에 큰 값이 있으므로, 왼쪽을 먼저 방문하고 자신을 처리한 뒤 오른쪽으로 가면 자연스럽게 오름차순이 됩니다. 정렬 알고리즘을 별도로 구현할 필요가 없습니다.
기존에는 트리에서 데이터를 꺼내 배열에 담고 sort()를 호출했다면, 이제는 중위 순회만으로 이미 정렬된 순서로 데이터를 처리할 수 있습니다. 이는 O(n) 시간에 정렬된 데이터를 얻을 수 있다는 의미입니다.
중위 순회의 핵심 특징은 세 가지입니다. 첫째, 재귀적 구조로 구현이 매우 간결합니다.
둘째, BST에서 항상 정렬된 순서를 보장합니다. 셋째, 스택 기반 반복문으로도 구현 가능하여 스택 오버플로우를 방지할 수 있습니다.
이러한 특징들이 중위 순회를 BST의 필수 연산으로 만듭니다.
코드 예제
// 재귀로 구현한 중위 순회
class BinarySearchTree {
// ... (이전 코드)
// 중위 순회: 정렬된 순서로 노드 방문
inOrderTraversal(node = this.root, result = []) {
// 베이스 케이스: 노드가 없으면 종료
if (node === null) return result;
// 1단계: 왼쪽 서브트리 방문 (작은 값들)
this.inOrderTraversal(node.left, result);
// 2단계: 현재 노드 처리 (중간 값)
result.push(node.value);
// 3단계: 오른쪽 서브트리 방문 (큰 값들)
this.inOrderTraversal(node.right, result);
return result;
}
// 정렬된 배열로 변환
toSortedArray() {
return this.inOrderTraversal();
}
}
// 사용 예시
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));
console.log(bst.toSortedArray()); // [20, 30, 40, 50, 60, 70, 80]
설명
이것이 하는 일: 중위 순회는 트리의 모든 노드를 특정 순서로 방문하여 처리하는 알고리즘입니다. BST의 경우 이 순서가 자동으로 정렬된 순서가 됩니다.
첫 번째로, 함수는 현재 노드가 null인지 확인하는 베이스 케이스로 시작합니다. 이것은 재귀의 종료 조건으로, 더 이상 방문할 노드가 없을 때 현재까지의 결과를 반환합니다.
이 체크가 없으면 무한 재귀에 빠지게 됩니다. 그 다음으로, 왼쪽 서브트리를 재귀적으로 방문합니다.
이 단계에서는 현재 노드보다 작은 모든 값들이 먼저 result 배열에 추가됩니다. 재귀가 깊이 들어가면서 가장 왼쪽 끝의 가장 작은 값부터 처리되기 시작합니다.
현재 노드를 처리하는 단계는 왼쪽 서브트리가 완전히 처리된 후에 실행됩니다. 이 시점에서 현재 노드의 값을 result에 추가하면, 이미 추가된 왼쪽 값들보다는 크고 앞으로 추가될 오른쪽 값들보다는 작은 위치에 놓이게 됩니다.
이것이 정렬이 자동으로 이루어지는 핵심 원리입니다. 마지막으로, 오른쪽 서브트리를 재귀적으로 방문합니다.
현재 노드보다 큰 모든 값들이 순서대로 result에 추가되면서 전체 순회가 완료됩니다. 최종적으로 반환되는 배열은 트리의 모든 값을 오름차순으로 담고 있습니다.
여러분이 이 코드를 사용하면 별도의 정렬 알고리즘 없이도 O(n) 시간에 정렬된 데이터를 얻을 수 있습니다. 메모리 사용도 결과 배열과 재귀 스택(O(h), h는 트리 높이)만 필요하므로 효율적입니다.
실무에서는 이를 활용해 범위 쿼리, 순위 계산, 데이터 내보내기 등 다양한 기능을 구현할 수 있습니다.
실전 팁
💡 재귀 깊이가 너무 깊으면 스택 오버플로우가 발생할 수 있습니다. 트리 높이가 수천 이상인 경우 반복문 기반 구현을 고려하세요.
💡 result 배열을 매번 생성하지 말고 파라미터로 전달하면 메모리 효율이 높아집니다. 위 코드처럼 기본값으로 빈 배열을 제공하되 재사용 가능하게 설계하세요.
💡 중위 순회 중간에 조건을 체크하여 조기 종료할 수 있습니다. 예를 들어 특정 값을 찾거나 K개만 수집하는 경우 불필요한 순회를 줄일 수 있습니다.
💡 오름차순이 아닌 내림차순이 필요하면 오른쪽 → 현재 → 왼쪽 순서로 방문하면 됩니다. 순서만 바꾸면 역순 정렬도 간단합니다.
💡 각 노드 방문 시 콜백 함수를 받도록 설계하면 유연성이 높아집니다. 배열에 담는 것 외에도 출력, 검증, 변환 등 다양한 작업을 수행할 수 있습니다.
3. 재귀_중위_순회_상세
시작하며
여러분이 처음 트리 순회를 배울 때 가장 이해하기 쉬운 방법은 무엇일까요? 복잡한 반복문과 스택 관리보다는 직관적으로 문제를 쪼개는 재귀가 훨씬 자연스럽습니다.
실제로 트리는 태생적으로 재귀적 구조입니다. 하나의 트리는 루트와 두 개의 서브트리로 구성되고, 각 서브트리도 같은 구조를 가집니다.
이런 특성은 재귀로 표현하기에 완벽합니다. 바로 이럴 때 필요한 것이 재귀로 구현하는 중위 순회입니다.
코드는 단 몇 줄이지만 트리의 모든 노드를 정확히 정렬된 순서로 방문할 수 있습니다.
개요
간단히 말해서, 재귀 중위 순회는 자기 자신을 호출하여 왼쪽과 오른쪽 서브트리를 처리하는 방식으로, 마치 문제를 작은 부분으로 나누어 해결하는 분할 정복 패턴입니다. 재귀가 강력한 이유는 우리가 전체 트리를 한 번에 생각할 필요가 없다는 점입니다.
현재 노드에서 해야 할 일만 정의하면, 나머지는 재귀 호출이 알아서 처리해줍니다. 100개 노드든 10,000개 노드든 동일한 로직이 작동합니다.
기존에는 명시적으로 스택을 만들고 while 루프로 노드를 관리해야 했다면, 재귀를 사용하면 시스템 콜 스택이 이 모든 것을 자동으로 처리해줍니다. 코드는 더 짧아지고 의도는 더 명확해집니다.
재귀 중위 순회의 핵심 특징은 세 가지입니다. 첫째, 코드가 매우 간결하여 유지보수가 쉽습니다.
둘째, 트리의 재귀적 구조와 자연스럽게 매칭되어 직관적입니다. 셋째, 베이스 케이스만 잘 설정하면 모든 경우가 자동으로 처리됩니다.
이러한 특징들이 재귀를 트리 순회의 기본 방법으로 만듭니다.
코드 예제
// 다양한 재귀 중위 순회 패턴
class BinarySearchTree {
// ... (이전 코드)
// 패턴 1: 배열 수집
inOrderArray(node = this.root, result = []) {
if (node !== null) {
this.inOrderArray(node.left, result);
result.push(node.value);
this.inOrderArray(node.right, result);
}
return result;
}
// 패턴 2: 콜백 실행
inOrderCallback(callback, node = this.root) {
if (node !== null) {
this.inOrderCallback(callback, node.left);
callback(node.value);
this.inOrderCallback(callback, node.right);
}
}
// 패턴 3: 조건부 순회 (특정 값 찾기)
findInOrder(target, node = this.root) {
if (node === null) return false;
// 왼쪽 검색
if (this.findInOrder(target, node.left)) return true;
// 현재 노드 확인
if (node.value === target) return true;
// 오른쪽 검색
return this.findInOrder(target, node.right);
}
// 패턴 4: 범위 수집 (start와 end 사이의 값들)
rangeQuery(start, end, node = this.root, result = []) {
if (node === null) return result;
// 왼쪽 가지치기: start보다 클 때만 왼쪽 방문
if (node.value > start) {
this.rangeQuery(start, end, node.left, result);
}
// 범위 내의 값만 수집
if (node.value >= start && node.value <= end) {
result.push(node.value);
}
// 오른쪽 가지치기: end보다 작을 때만 오른쪽 방문
if (node.value < end) {
this.rangeQuery(start, end, node.right, result);
}
return result;
}
}
설명
이것이 하는 일: 재귀 중위 순회는 복잡한 트리 구조를 단순한 재귀 호출로 해결하여 모든 노드를 정렬된 순서로 처리합니다. 각 함수 호출은 하나의 서브트리를 담당합니다.
첫 번째 패턴인 inOrderArray는 가장 기본적인 형태로, 모든 값을 배열에 수집합니다. null 체크를 먼저 하고 null이 아닐 때만 세 단계를 실행하는 구조입니다.
이 패턴은 전체 데이터를 한 번에 가져와야 할 때 유용합니다. 두 번째 패턴인 inOrderCallback은 더 유연합니다.
값을 수집하는 대신 각 노드에서 콜백 함수를 실행합니다. 이를 통해 출력, 카운팅, 검증 등 다양한 작업을 수행할 수 있습니다.
예를 들어 bst.inOrderCallback(val => console.log(val))로 모든 값을 정렬된 순서로 출력할 수 있습니다. 세 번째 패턴인 findInOrder는 조건부 순회의 예시입니다.
특정 값을 찾으면 즉시 true를 반환하여 불필요한 순회를 중단합니다. 이는 최적화 기법으로, 모든 노드를 방문할 필요가 없을 때 성능을 크게 개선합니다.
네 번째 패턴인 rangeQuery는 가장 실전적입니다. BST의 정렬 속성을 활용하여 범위 밖의 서브트리는 아예 방문하지 않습니다.
예를 들어 현재 노드가 100인데 찾는 범위가 1-50이면 오른쪽 서브트리는 볼 필요가 없습니다. 이런 가지치기(pruning)로 시간 복잡도를 O(n)에서 O(log n + k)로 줄일 수 있습니다(k는 결과 개수).
여러분이 이 패턴들을 사용하면 다양한 상황에 맞는 순회를 구현할 수 있습니다. 전체 데이터가 필요하면 패턴 1, 각 요소를 처리하려면 패턴 2, 특정 값을 찾으려면 패턴 3, 범위 검색이 필요하면 패턴 4를 선택하세요.
실무에서는 이런 패턴들을 조합하여 복잡한 쿼리도 효율적으로 처리할 수 있습니다.
실전 팁
💡 재귀 함수에서 베이스 케이스를 반드시 먼저 작성하세요. null 체크를 빠뜨리면 무한 재귀로 스택 오버플로우가 발생합니다.
💡 파라미터 순서를 일관되게 유지하세요. 일반적으로 콜백/타겟 같은 인자를 먼저, 노드와 결과 배열을 나중에 배치하면 가독성이 좋습니다.
💡 대규모 트리에서는 재귀 대신 반복문 구현을 고려하세요. JavaScript의 기본 스택 크기는 제한적이므로 수만 개의 노드에서는 위험할 수 있습니다.
💡 디버깅 시 각 재귀 호출의 깊이를 추적하면 도움이 됩니다. 파라미터에 depth를 추가하고 console.log(' '.repeat(depth) + node.value)로 트리 구조를 시각화할 수 있습니다.
💡 tail call optimization을 기대하지 마세요. JavaScript 엔진 대부분이 이를 지원하지 않으므로 깊은 재귀는 여전히 스택을 소비합니다.
4. 반복문_중위_순회
시작하며
여러분이 수백만 개의 노드를 가진 대규모 트리를 처리해야 한다면 재귀는 위험할 수 있습니다. 재귀 깊이 제한에 걸려 프로그램이 중단되는 상황을 경험해본 적이 있나요?
실제 프로덕션 환경에서는 입력 크기를 예측할 수 없습니다. 사용자가 업로드한 데이터가 얼마나 클지, 트리가 얼마나 깊어질지 알 수 없을 때 재귀는 시한폭탄이 될 수 있습니다.
바로 이럴 때 필요한 것이 반복문으로 구현하는 중위 순회입니다. 명시적 스택을 사용하여 재귀와 같은 동작을 하면서도 스택 오버플로우 걱정 없이 안전하게 실행할 수 있습니다.
개요
간단히 말해서, 반복문 중위 순회는 시스템 콜 스택 대신 직접 만든 스택 자료구조를 사용하여 노드를 추적하면서 트리를 순회하는 방법입니다. 이 방법이 중요한 이유는 명확합니다.
스택 오버플로우를 완전히 방지할 수 있고, 순회 과정을 더 세밀하게 제어할 수 있습니다. 예를 들어 순회를 일시 중지했다가 나중에 재개하거나, 특정 시점의 스택 상태를 저장할 수도 있습니다.
기존 재귀 방식이 시스템 스택에 의존하여 깊이 제한이 있었다면, 반복문 방식은 힙 메모리를 사용하므로 이론적으로 메모리가 허용하는 한 무제한입니다. 실무에서는 이것이 안정성의 차이를 만듭니다.
반복문 중위 순회의 핵심 특징은 세 가지입니다. 첫째, 스택 오버플로우가 발생하지 않아 대규모 데이터에 안전합니다.
둘째, 순회 상태를 명시적으로 관리하여 중단과 재개가 가능합니다. 셋째, 디버깅이 쉽습니다.
각 반복마다 스택 내용을 확인할 수 있기 때문입니다. 이러한 특징들이 반복문 구현을 프로덕션 환경의 선택으로 만듭니다.
코드 예제
// 스택을 사용한 반복문 중위 순회
class BinarySearchTree {
// ... (이전 코드)
// 기본 반복문 중위 순회
inOrderIterative() {
const result = [];
const stack = [];
let current = this.root;
// current가 null이고 스택도 비면 순회 완료
while (current !== null || stack.length > 0) {
// 왼쪽 끝까지 이동하며 스택에 저장
while (current !== null) {
stack.push(current);
current = current.left;
}
// 스택에서 꺼내기: 가장 왼쪽 노드
current = stack.pop();
// 현재 노드 처리
result.push(current.value);
// 오른쪽 서브트리로 이동
current = current.right;
}
return result;
}
// 제너레이터를 활용한 지연 순회
*inOrderGenerator() {
const stack = [];
let current = this.root;
while (current !== null || stack.length > 0) {
while (current !== null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
yield current.value; // 값을 하나씩 생성
current = current.right;
}
}
}
// 사용 예시
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));
// 일반 반복문 방식
console.log(bst.inOrderIterative()); // [20, 30, 40, 50, 60, 70, 80]
// 제너레이터 방식: 필요한 만큼만 순회
const gen = bst.inOrderGenerator();
console.log(gen.next().value); // 20
console.log(gen.next().value); // 30
// 나머지는 필요할 때 호출
설명
이것이 하는 일: 반복문 중위 순회는 재귀 호출 스택을 배열로 대체하여 같은 순회 순서를 구현합니다. while 루프와 명시적 스택으로 트리의 모든 노드를 방문합니다.
첫 번째로, 두 개의 while 루프 구조를 이해해야 합니다. 바깥쪽 루프는 순회가 완료될 때까지 계속 실행됩니다.
현재 노드가 있거나 스택에 노드가 남아있으면 계속됩니다. 안쪽 루프는 현재 노드에서 왼쪽 끝까지 내려가면서 모든 노드를 스택에 푸시합니다.
그 다음으로, 왼쪽 끝에 도달하면(current가 null) 스택에서 노드를 하나 꺼냅니다. 이 노드가 바로 정렬 순서상 다음으로 처리해야 할 노드입니다.
재귀에서 "왼쪽 서브트리 처리 완료 후 현재 노드 처리"와 동일한 시점입니다. 현재 노드를 처리한 후에는 오른쪽 자식으로 이동합니다.
오른쪽 자식이 있다면 다시 안쪽 루프가 실행되어 그 서브트리의 왼쪽 끝까지 내려갑니다. 없다면 스택에서 다음 노드를 꺼내 계속합니다.
이 과정이 트리의 모든 노드가 처리될 때까지 반복됩니다. 제너레이터 버전은 더 흥미롭습니다.
yield 키워드를 사용하여 값을 하나씩 생성하므로, 전체 트리를 순회하지 않고도 필요한 만큼만 값을 가져올 수 있습니다. 예를 들어 "처음 10개 값만 필요"하거나 "특정 조건을 만족하는 첫 번째 값 찾기" 같은 경우에 매우 효율적입니다.
여러분이 이 코드를 사용하면 어떤 크기의 트리든 안전하게 순회할 수 있습니다. 스택 오버플로우 걱정 없이 수백만 노드를 처리할 수 있고, 제너레이터를 활용하면 메모리도 절약할 수 있습니다.
실무에서는 대용량 데이터 처리, 스트리밍 응답, 페이지네이션 구현 등에 이 패턴을 활용합니다.
실전 팁
💡 스택 크기는 트리 높이에 비례합니다. 균형 잡힌 트리에서는 O(log n)이지만 편향 트리에서는 O(n)까지 커질 수 있으니 메모리를 모니터링하세요.
💡 제너레이터는 for...of 루프와 궁합이 좋습니다. for (const value of bst.inOrderGenerator())로 간결하게 순회할 수 있습니다.
💡 순회를 중단하고 재개해야 한다면 스택 상태를 객체로 저장하세요. 클로저나 클래스 속성으로 상태를 유지하면 됩니다.
💡 성능 비교 시 반복문이 재귀보다 약간 느릴 수 있습니다. 함수 호출 오버헤드는 없지만 배열 조작 비용이 있기 때문입니다. 하지만 안정성이 성능보다 중요합니다.
💡 디버깅할 때 각 반복 후 스택 내용을 로깅하면 순회 과정을 명확히 볼 수 있습니다. console.log(stack.map(n => n.value))로 현재 스택 상태를 확인하세요.
5. K번째_작은_값_찾기
시작하며
여러분이 게임 랭킹 시스템에서 "10위 유저는 누구인가?"를 찾아야 하는 상황을 생각해보세요. 전체를 정렬하면 O(n log n)이 걸리는데, 단지 하나의 값을 위해 너무 비효율적입니다.
실제로 많은 서비스에서 "상위 K개", "K번째 요소" 같은 쿼리가 빈번히 발생합니다. 리더보드, 추천 시스템, 통계 분석 등 다양한 곳에서 필요합니다.
매번 전체 정렬을 하면 성능 병목이 됩니다. 바로 이럴 때 필요한 것이 BST의 중위 순회를 활용한 K번째 값 찾기입니다.
이미 정렬된 구조를 가진 BST에서 중위 순회로 K번째까지만 진행하면 O(K) 시간에 답을 얻을 수 있습니다.
개요
간단히 말해서, K번째 작은 값 찾기는 중위 순회를 하면서 카운터를 증가시키다가 K에 도달하면 즉시 반환하는 최적화된 알고리즘입니다. 이 방법이 효율적인 이유는 필요한 만큼만 순회한다는 점입니다.
전체 n개 노드 중 앞의 K개만 보면 되므로, K가 작을 때 극적인 성능 향상을 얻습니다. 예를 들어 100만 개 중 10번째를 찾는다면 대부분의 노드를 건너뛸 수 있습니다.
기존에 전체를 배열로 변환하고 인덱스로 접근했다면, 이제는 순회 중에 바로 값을 찾아 조기 종료할 수 있습니다. 이는 시간과 공간 복잡도를 모두 줄이는 이중 이점을 제공합니다.
K번째 값 찾기의 핵심 특징은 세 가지입니다. 첫째, 조기 종료로 불필요한 순회를 방지합니다.
둘째, 추가 메모리를 거의 사용하지 않습니다. 셋째, 균형 잡힌 BST에서는 O(log n + K) 시간에 실행됩니다.
이러한 특징들이 이 알고리즘을 실시간 랭킹 시스템의 핵심으로 만듭니다.
코드 예제
// K번째 작은 값 찾기 구현
class BinarySearchTree {
// ... (이전 코드)
// 재귀 버전: 카운터를 객체로 전달하여 참조 유지
kthSmallest(k, node = this.root, counter = { count: 0 }) {
if (node === null) return null;
// 왼쪽 서브트리 탐색
const leftResult = this.kthSmallest(k, node.left, counter);
if (leftResult !== null) return leftResult;
// 현재 노드 처리: 카운터 증가
counter.count++;
if (counter.count === k) return node.value;
// 오른쪽 서브트리 탐색
return this.kthSmallest(k, node.right, counter);
}
// 반복문 버전: 더 효율적이고 안전
kthSmallestIterative(k) {
const stack = [];
let current = this.root;
let count = 0;
while (current !== null || stack.length > 0) {
// 왼쪽 끝까지 이동
while (current !== null) {
stack.push(current);
current = current.left;
}
// 노드 처리
current = stack.pop();
count++;
// K번째 발견
if (count === k) return current.value;
// 오른쪽으로 이동
current = current.right;
}
return null; // K가 트리 크기보다 큰 경우
}
// 범위 버전: K번째부터 M번째까지
kthToMthSmallest(k, m) {
const result = [];
const stack = [];
let current = this.root;
let count = 0;
while (current !== null || stack.length > 0) {
while (current !== null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
count++;
// K번째부터 M번째까지 수집
if (count >= k && count <= m) {
result.push(current.value);
}
// M번째 초과 시 조기 종료
if (count > m) break;
current = current.right;
}
return result;
}
}
// 사용 예시
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 65].forEach(val => bst.insert(val));
console.log(bst.kthSmallestIterative(1)); // 10 (최솟값)
console.log(bst.kthSmallestIterative(3)); // 25
console.log(bst.kthSmallestIterative(11)); // 80 (최댓값)
console.log(bst.kthToMthSmallest(3, 7)); // [25, 30, 35, 40, 50]
설명
이것이 하는 일: K번째 작은 값 찾기는 중위 순회의 정렬 속성을 활용하여, 필요한 만큼만 순회하고 조기 종료하는 최적화된 검색 알고리즘입니다. 첫 번째로, 재귀 버전에서는 counter를 객체로 전달하는 것이 핵심입니다.
JavaScript는 원시 타입을 값으로 전달하므로, 단순히 count 숫자를 전달하면 재귀 호출 간에 값이 공유되지 않습니다. { count: 0 } 같은 객체로 감싸면 참조로 전달되어 모든 재귀 호출이 같은 카운터를 공유합니다.
그 다음으로, 반복문 버전이 더 실용적입니다. 스택 오버플로우 위험이 없고 성능도 약간 더 좋습니다.
중위 순회의 일반 패턴을 따르되, K번째에 도달하면 즉시 return하여 나머지 노드를 건너뜁니다. 이 조기 종료가 성능의 핵심입니다.
세 번째로, kthToMthSmallest는 범위 쿼리를 보여줍니다. "3등부터 7등까지" 같은 요구사항에 유용합니다.
count가 k에 도달하면 수집을 시작하고, m을 초과하면 즉시 종료합니다. 이렇게 하면 O(M) 시간에 원하는 범위를 얻을 수 있습니다.
시간 복잡도를 분석하면, 최악의 경우(편향 트리) O(K)이고, 최선의 경우(균형 트리) O(log n + K)입니다. K가 작으면 매우 효율적이지만, K가 n에 가까우면 전체 순회와 비슷해집니다.
공간 복잡도는 스택 크기인 O(h)로 트리 높이에 비례합니다. 여러분이 이 코드를 사용하면 랭킹 시스템, 중앙값 찾기, 백분위수 계산 등을 효율적으로 구현할 수 있습니다.
특히 K가 n보다 훨씬 작을 때 전체 정렬 대비 극적인 성능 향상을 경험할 수 있습니다. 실무에서는 페이지네이션(예: 11-20위 유저 조회)이나 상위 N개 추천에 이 패턴을 활용합니다.
실전 팁
💡 K가 n/2보다 크면 역순(오른쪽→현재→왼쪽)으로 n-K+1번째를 찾는 것이 더 빠릅니다. 조건에 따라 순회 방향을 선택하세요.
💡 K의 유효성을 먼저 검증하세요. K가 0이거나 트리 크기보다 크면 에러를 던지거나 null을 반환하는 것이 좋습니다.
💡 빈번한 K번째 쿼리가 있다면 각 노드에 서브트리 크기를 저장하는 Augmented BST를 고려하세요. O(log n)에 K번째를 찾을 수 있습니다.
💡 중앙값이 필요하면 k = Math.ceil(n/2)로 설정하면 됩니다. 트리 크기를 미리 계산해두거나 size 속성을 유지하세요.
💡 제너레이터와 조합하면 더 유연합니다. 순회 제너레이터를 만들고 K번째까지만 next()를 호출하는 방식도 가능합니다.
6. 범위_검색_구현
시작하며
여러분이 전자상거래 사이트에서 "10,000원에서 50,000원 사이의 상품"을 검색하는 기능을 구현한다고 생각해보세요. 모든 상품을 순회하며 조건을 체크하는 것은 너무 느립니다.
실제로 범위 쿼리는 매우 흔한 요구사항입니다. 날짜 범위 검색, 점수 범위 필터링, 좌표 기반 검색 등 수많은 상황에서 "A와 B 사이의 값들"을 찾아야 합니다.
순차 검색으로는 대규모 데이터에서 성능을 보장할 수 없습니다. 바로 이럴 때 필요한 것이 BST의 범위 검색입니다.
트리의 정렬 속성을 활용하여 범위 밖의 서브트리를 건너뛰므로, 전체를 순회하지 않고도 결과를 빠르게 얻을 수 있습니다.
개요
간단히 말해서, 범위 검색은 중위 순회를 하되 현재 노드 값에 따라 왼쪽이나 오른쪽 서브트리를 가지치기(pruning)하여 필요한 부분만 탐색하는 최적화된 알고리즘입니다. 이 방법이 강력한 이유는 BST의 구조적 특성을 최대한 활용하기 때문입니다.
현재 노드가 범위보다 크면 오른쪽 서브트리는 볼 필요가 없고, 범위보다 작으면 왼쪽 서브트리를 건너뛸 수 있습니다. 이런 가지치기로 불필요한 순회를 대폭 줄입니다.
기존에 선형 탐색으로 O(n) 시간이 걸렸다면, 균형 잡힌 BST에서 범위 검색은 O(log n + k) 시간에 실행됩니다(k는 결과 개수). 100만 개 중 10개를 찾는다면 차이가 엄청납니다.
범위 검색의 핵심 특징은 세 가지입니다. 첫째, 가지치기로 불필요한 노드를 건너뜁니다.
둘째, 결과는 자동으로 정렬되어 나옵니다. 셋째, 여러 범위 조건을 조합할 수 있습니다.
이러한 특징들이 범위 검색을 데이터베이스 인덱스의 기초로 만듭니다.
코드 예제
// 다양한 범위 검색 패턴
class BinarySearchTree {
// ... (이전 코드)
// 기본 범위 검색: [start, end] 포함
rangeSearch(start, end, node = this.root, result = []) {
if (node === null) return result;
// 왼쪽 가지치기: node.value > start일 때만 왼쪽 탐색
if (node.value > start) {
this.rangeSearch(start, end, node.left, result);
}
// 현재 노드가 범위 내인지 확인
if (node.value >= start && node.value <= end) {
result.push(node.value);
}
// 오른쪽 가지치기: node.value < end일 때만 오른쪽 탐색
if (node.value < end) {
this.rangeSearch(start, end, node.right, result);
}
return result;
}
// 반복문 버전: 스택 안전
rangeSearchIterative(start, end) {
const result = [];
const stack = [];
let current = this.root;
while (current !== null || stack.length > 0) {
// 왼쪽으로 이동: start보다 큰 동안만
while (current !== null && current.value > start) {
stack.push(current);
current = current.left;
}
// start 이하의 노드 처리
if (current !== null && current.value >= start && current.value <= end) {
result.push(current.value);
if (current.value < end) {
current = current.right;
} else {
break; // end를 초과하면 종료
}
} else if (current !== null) {
// start 미만이면 오른쪽으로
current = current.right;
} else if (stack.length > 0) {
// 스택에서 꺼내기
current = stack.pop();
if (current.value > end) break; // 범위 초과 시 종료
result.push(current.value);
current = current.right;
}
}
return result;
}
// 범위 카운트: 개수만 세기 (결과 저장 안 함)
rangeCount(start, end, node = this.root) {
if (node === null) return 0;
let count = 0;
// 왼쪽 서브트리 카운트
if (node.value > start) {
count += this.rangeCount(start, end, node.left);
}
// 현재 노드 카운트
if (node.value >= start && node.value <= end) {
count++;
}
// 오른쪽 서브트리 카운트
if (node.value < end) {
count += this.rangeCount(start, end, node.right);
}
return count;
}
// 범위 조건 함수 버전: 더 유연한 조건
rangeWithCondition(start, end, condition, node = this.root, result = []) {
if (node === null) return result;
if (node.value > start) {
this.rangeWithCondition(start, end, condition, node.left, result);
}
// 범위 내이고 추가 조건도 만족하는 경우만 수집
if (node.value >= start && node.value <= end && condition(node.value)) {
result.push(node.value);
}
if (node.value < end) {
this.rangeWithCondition(start, end, condition, node.right, result);
}
return result;
}
}
// 사용 예시
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 65].forEach(val => bst.insert(val));
console.log(bst.rangeSearch(25, 60)); // [25, 30, 35, 40, 50, 60]
console.log(bst.rangeCount(25, 60)); // 6
console.log(bst.rangeWithCondition(20, 70, n => n % 10 === 0)); // [20, 30, 40, 50, 60, 70]
설명
이것이 하는 일: 범위 검색은 BST의 정렬 속성을 활용하여 범위 밖의 서브트리를 탐색하지 않고, 범위 내의 모든 값을 효율적으로 찾아내는 알고리즘입니다. 첫 번째로, 가지치기 로직을 이해해야 합니다.
if (node.value > start)는 "현재 노드가 시작값보다 크면 왼쪽에 더 작은 값들이 있을 수 있다"는 의미입니다. 반대로 현재 노드가 start 이하라면 왼쪽은 모두 start보다 작으므로 볼 필요가 없습니다.
오른쪽도 마찬가지 논리로 node.value < end일 때만 탐색합니다. 그 다음으로, rangeCount는 메모리를 절약하는 패턴입니다.
실제 값들을 저장하지 않고 개수만 세므로, 결과가 필요 없고 통계만 필요한 경우 유용합니다. 예를 들어 "조건을 만족하는 항목이 100개 이상인가?"를 확인할 때 사용합니다.
세 번째로, rangeWithCondition은 실전적인 확장입니다. 범위 조건 외에 추가 조건을 함수로 받아 더 복잡한 쿼리를 처리합니다.
예를 들어 "25와 60 사이이면서 10의 배수"같은 조건을 간단히 표현할 수 있습니다. 이는 SQL의 WHERE 절과 유사한 개념입니다.
시간 복잡도는 O(log n + k)입니다. log n은 첫 번째 결과를 찾는 시간이고, k는 결과 개수입니다.
가지치기가 효과적일수록 실제 방문 노드 수가 줄어듭니다. 최악의 경우(전체가 범위 내)는 O(n)이지만, 실무에서는 범위가 제한적이므로 훨씬 빠릅니다.
여러분이 이 코드를 사용하면 데이터베이스 스타일의 범위 쿼리를 메모리에서 빠르게 실행할 수 있습니다. 날짜 범위 검색, 가격 필터링, 점수 구간 분석 등 다양한 실무 시나리오에 적용할 수 있습니다.
특히 인덱싱이 필요한 대규모 인메모리 데이터 구조를 설계할 때 이 패턴이 핵심이 됩니다.
실전 팁
💡 범위가 매우 넓다면 가지치기 효과가 적습니다. 전체의 80% 이상이 범위에 포함되면 일반 중위 순회와 비슷한 성능을 보입니다.
💡 start > end 같은 잘못된 입력을 검증하세요. 빈 배열을 반환하거나 에러를 던지는 것이 좋습니다.
💡 범위 검색 결과를 자주 사용한다면 캐싱을 고려하세요. 트리가 변경되지 않는 동안 같은 범위 쿼리는 캐시된 결과를 반환할 수 있습니다.
💡 경계 값 처리를 명확히 하세요. 위 코드는 [start, end] 포함 범위이지만, 요구사항에 따라 (start, end), [start, end) 등으로 조정할 수 있습니다.
💡 다차원 범위 검색이 필요하면 BST를 중첩하거나 R-tree, K-d tree 같은 전문 자료구조를 사용하세요. 2D, 3D 범위 쿼리는 BST만으로 비효율적입니다.
7. BST를_배열로_변환
시작하며
여러분이 BST에 저장된 데이터를 API 응답으로 보내거나, 파일에 저장하거나, 다른 시스템과 공유해야 하는 상황이 있습니다. 트리 구조 그대로는 직렬화하거나 전송하기 어렵습니다.
실제로 데이터 교환 시 배열은 가장 범용적인 형식입니다. JSON으로 직렬화하기 쉽고, 다른 프로그래밍 언어에서도 쉽게 읽을 수 있으며, 순회나 필터링 같은 배열 메서드를 바로 사용할 수 있습니다.
바로 이럴 때 필요한 것이 BST를 정렬된 배열로 변환하는 기능입니다. 중위 순회를 사용하면 트리의 모든 값을 오름차순 배열로 간단히 추출할 수 있습니다.
개요
간단히 말해서, BST를 배열로 변환하는 것은 중위 순회를 수행하면서 각 노드의 값을 배열에 수집하는 과정입니다. 결과는 자동으로 정렬된 배열이 됩니다.
이 변환이 유용한 이유는 명확합니다. 배열은 인덱스 접근이 O(1)이고, 슬라이싱, 매핑, 필터링 같은 다양한 연산을 지원하며, 모든 JavaScript 환경에서 네이티브로 지원됩니다.
트리 구조를 유지할 필요가 없는 순간부터는 배열이 더 편리합니다. 기존에 트리를 순회하며 하나씩 처리했다면, 배열로 변환 후에는 map(), filter(), reduce() 같은 강력한 배열 메서드를 활용할 수 있습니다.
이는 코드의 가독성과 유지보수성을 크게 향상시킵니다. BST 배열 변환의 핵심 특징은 세 가지입니다.
첫째, 결과가 이미 정렬되어 있어 추가 정렬이 불필요합니다. 둘째, O(n) 시간과 O(n) 공간에 변환이 완료됩니다.
셋째, 변환 후 배열 연산을 자유롭게 사용할 수 있습니다. 이러한 특징들이 트리와 배열 간의 변환을 데이터 처리 파이프라인의 중요한 단계로 만듭니다.
코드 예제
// BST를 배열로 변환하는 다양한 방법
class BinarySearchTree {
// ... (이전 코드)
// 기본 변환: 오름차순 배열
toArray() {
return this.inOrderTraversal();
}
// 내림차순 배열
toArrayDescending(node = this.root, result = []) {
if (node !== null) {
// 오른쪽 → 현재 → 왼쪽 (역순)
this.toArrayDescending(node.right, result);
result.push(node.value);
this.toArrayDescending(node.left, result);
}
return result;
}
// 노드 객체 포함 배열 (값뿐 아니라 메타데이터도)
toArrayWithNodes(node = this.root, result = []) {
if (node !== null) {
this.toArrayWithNodes(node.left, result);
result.push({
value: node.value,
hasLeft: node.left !== null,
hasRight: node.right !== null
});
this.toArrayWithNodes(node.right, result);
}
return result;
}
// 변환 중 매핑: 각 값을 변환
toArrayMapped(mapper, node = this.root, result = []) {
if (node !== null) {
this.toArrayMapped(mapper, node.left, result);
result.push(mapper(node.value));
this.toArrayMapped(mapper, node.right, result);
}
return result;
}
// 변환 중 필터링: 조건 만족하는 값만
toArrayFiltered(predicate, node = this.root, result = []) {
if (node !== null) {
this.toArrayFiltered(predicate, node.left, result);
if (predicate(node.value)) {
result.push(node.value);
}
this.toArrayFiltered(predicate, node.right, result);
}
return result;
}
// 레벨별 배열 (중위 순회가 아님, 비교용)
toLevelArray() {
if (this.root === null) return [];
const result = [];
const queue = [this.root];
while (queue.length > 0) {
const node = queue.shift();
result.push(node.value);
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
return result;
}
}
// 사용 예시
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));
console.log(bst.toArray()); // [20, 30, 40, 50, 60, 70, 80]
console.log(bst.toArrayDescending()); // [80, 70, 60, 50, 40, 30, 20]
console.log(bst.toArrayMapped(x => x * 2)); // [40, 60, 80, 100, 120, 140, 160]
console.log(bst.toArrayFiltered(x => x > 40)); // [50, 60, 70, 80]
console.log(bst.toLevelArray()); // [50, 30, 70, 20, 40, 60, 80] (BFS)
설명
이것이 하는 일: BST를 배열로 변환하는 것은 트리 구조의 데이터를 선형 자료구조로 평탄화하여 다양한 용도로 활용할 수 있게 만드는 과정입니다. 첫 번째로, toArray()는 가장 기본적인 변환입니다.
앞서 배운 중위 순회를 그대로 사용하여 오름차순 배열을 만듭니다. 이 배열은 정렬이 보장되므로 이진 검색, 중앙값 계산, 백분위수 분석 등에 바로 사용할 수 있습니다.
그 다음으로, toArrayDescending()은 순서만 바꾼 버전입니다. 오른쪽 → 현재 → 왼쪽 순서로 방문하면 큰 값부터 작은 값 순으로 배열이 만들어집니다.
내림차순 정렬이 필요한 리더보드나 최신순 목록에 유용합니다. 세 번째로, toArrayMapped()와 toArrayFiltered()는 변환과 동시에 데이터를 가공합니다.
따로 배열을 만든 후 map()이나 filter()를 호출하는 것보다 한 번의 순회로 처리하므로 효율적입니다. 예를 들어 "점수를 퍼센트로 변환" 같은 작업을 순회 중에 바로 처리할 수 있습니다.
네 번째로, toLevelArray()는 비교를 위해 추가한 것으로 BFS(너비 우선 탐색) 순서입니다. 중위 순회와 달리 레벨별로 왼쪽에서 오른쪽으로 수집하므로 정렬되지 않습니다.
트리 구조를 시각화하거나 레벨별 처리가 필요할 때 사용합니다. 시간 복잡도는 모든 변환이 O(n)입니다.
각 노드를 정확히 한 번씩 방문하기 때문입니다. 공간 복잡도도 O(n)으로 결과 배열에 모든 값을 저장합니다.
추가로 재귀 스택이 O(h)를 사용하지만 결과 배열이 지배적입니다. 여러분이 이 코드를 사용하면 트리 데이터를 다양한 형태로 추출할 수 있습니다.
API 응답 생성, CSV/JSON 내보내기, 데이터 분석, 다른 자료구조로 변환 등 실무의 수많은 시나리오에서 활용됩니다. 특히 변환과 가공을 동시에 수행하는 패턴은 성능과 가독성을 모두 잡는 방법입니다.
실전 팁
💡 대규모 트리를 변환할 때는 메모리 사용량을 모니터링하세요. 배열이 n개 요소를 모두 담으므로 메모리 부족이 발생할 수 있습니다.
💡 변환 후 원본 트리를 더 이상 사용하지 않는다면 null로 설정하여 가비지 컬렉션을 돕세요. 메모리 사용이 반으로 줄어듭니다.
💡 페이지네이션이 필요하면 배열 변환 후 slice()를 사용하거나, 중위 순회 중에 오프셋과 리밋을 적용하는 것이 더 효율적입니다.
💡 JSON 직렬화가 목적이라면 JSON.stringify(bst.toArray())를 사용하세요. 트리 구조 자체를 직렬화하는 것보다 훨씬 간단하고 호환성이 좋습니다.
💡 toArrayWithNodes처럼 추가 메타데이터를 포함하면 나중에 트리를 재구성하거나 분석할 때 유용합니다. 어떤 정보가 필요한지 미리 계획하세요.
8. Morris_순회_알고리즘
시작하며
여러분이 메모리가 제한된 임베디드 시스템이나 엄격한 메모리 제약이 있는 환경에서 트리를 순회해야 한다면 어떻게 해야 할까요? 재귀는 스택을 사용하고, 반복문도 스택 자료구조가 필요합니다.
실제로 많은 시스템에서 메모리는 귀중한 자원입니다. 모바일 앱, IoT 디바이스, 대규모 데이터 처리 파이프라인에서 O(n) 추가 메모리는 감당하기 어려울 수 있습니다.
O(h) 스택조차 부담스러운 경우도 있습니다. 바로 이럴 때 필요한 것이 Morris 순회 알고리즘입니다.
추가 메모리를 전혀 사용하지 않고(O(1) 공간 복잡도) 트리를 순회할 수 있는 놀라운 방법입니다.
개요
간단히 말해서, Morris 순회는 트리의 구조를 임시로 수정하여 스레드(thread)를 만들고, 순회 후 원래대로 복원하는 방식으로 스택 없이 중위 순회를 구현하는 알고리즘입니다. 이 알고리즘이 혁신적인 이유는 상수 공간만 사용한다는 점입니다.
아무리 큰 트리라도 몇 개의 포인터 변수만으로 순회할 수 있습니다. 이는 메모리 효율이 중요한 환경에서 게임 체인저가 됩니다.
기존 방법들이 모두 O(h) 이상의 추가 메모리를 요구했다면, Morris 순회는 O(1)로 이 한계를 돌파합니다. 트리 자체를 임시 작업 공간으로 사용하는 영리한 아이디어입니다.
Morris 순회의 핵심 특징은 세 가지입니다. 첫째, O(1) 공간 복잡도로 메모리를 거의 사용하지 않습니다.
둘째, 트리를 임시 수정하지만 순회 후 완벽히 복원됩니다. 셋째, 시간 복잡도는 여전히 O(n)으로 효율적입니다.
이러한 특징들이 Morris 순회를 메모리 제약 환경의 해결책으로 만듭니다.
코드 예제
// Morris 순회 알고리즘 구현
class BinarySearchTree {
// ... (이전 코드)
// Morris 중위 순회: O(1) 공간 복잡도
morrisInOrder() {
const result = [];
let current = this.root;
while (current !== null) {
if (current.left === null) {
// 왼쪽이 없으면 현재 노드 처리하고 오른쪽으로
result.push(current.value);
current = current.right;
} else {
// 왼쪽이 있으면 중위 선행자(predecessor) 찾기
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;
result.push(current.value);
current = current.right;
}
}
}
return result;
}
// Morris 전위 순회
morrisPreOrder() {
const result = [];
let current = this.root;
while (current !== null) {
if (current.left === null) {
result.push(current.value);
current = current.right;
} else {
let predecessor = current.left;
while (predecessor.right !== null && predecessor.right !== current) {
predecessor = predecessor.right;
}
if (predecessor.right === null) {
// 전위는 스레드 생성 시 바로 처리
result.push(current.value);
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
current = current.right;
}
}
}
return result;
}
// Morris로 트리 검증 (BST 속성 확인)
validateBSTMorris() {
let prev = -Infinity;
let current = this.root;
while (current !== null) {
if (current.left === null) {
// 이전 값보다 커야 함 (BST 속성)
if (current.value <= prev) return false;
prev = current.value;
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 (current.value <= prev) return false;
prev = current.value;
current = current.right;
}
}
}
return true;
}
}
// 사용 예시
const bst = new BinarySearchTree();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));
console.log(bst.morrisInOrder()); // [20, 30, 40, 50, 60, 70, 80]
console.log(bst.morrisPreOrder()); // [50, 30, 20, 40, 70, 60, 80]
console.log(bst.validateBSTMorris()); // true
설명
이것이 하는 일: Morris 순회는 트리 구조를 임시로 수정하여 "다음에 어디로 가야 하는지"를 트리 자체에 기록함으로써 스택 없이도 순회할 수 있게 만드는 알고리즘입니다. 첫 번째로, 핵심 아이디어는 중위 선행자(in-order predecessor)를 활용하는 것입니다.
현재 노드의 선행자는 왼쪽 서브트리에서 가장 오른쪽 노드입니다. 이 노드는 중위 순회에서 현재 노드 직전에 방문되며, 원래는 오른쪽 자식이 null입니다.
그 다음으로, 이 null 오른쪽 포인터를 현재 노드로 연결하는 "스레드"를 만듭니다. 왼쪽 서브트리를 모두 순회한 후 어디로 돌아와야 하는지 알려주는 표시입니다.
이렇게 하면 스택에 "돌아갈 곳"을 저장하는 대신 트리 자체가 그 정보를 담습니다. 세 번째로, 순회 과정에서 스레드를 만났다면(predecessor.right === current) 이미 왼쪽 서브트리를 모두 방문했다는 뜻입니다.
이때 스레드를 제거하여 트리를 원래 상태로 복원하고, 현재 노드를 처리한 후 오른쪽으로 이동합니다. 이 복원 과정이 트리를 손상시키지 않습니다.
네 번째로, 왼쪽 자식이 없는 노드는 바로 처리합니다. 왼쪽이 없으면 현재 노드가 최소값이므로 즉시 결과에 추가하고 오른쪽으로 갑니다.
이 단순한 케이스가 알고리즘의 베이스 케이스 역할을 합니다. 시간 복잡도는 O(n)입니다.
각 노드를 최대 3번 방문하지만(스레드 생성, 스레드 발견, 실제 처리) 상수 배수이므로 여전히 선형입니다. 공간 복잡도는 O(1)로, current와 predecessor 같은 몇 개의 포인터 변수만 사용합니다.
여러분이 이 코드를 사용하면 메모리가 매우 제한된 환경에서도 트리 순회를 수행할 수 있습니다. 임베디드 시스템, 스트리밍 데이터 처리, 대규모 트리 분석 등에서 유용합니다.
다만 구현이 복잡하므로 일반적인 경우에는 재귀나 반복문을 사용하고, 정말 메모리 제약이 심할 때만 Morris 순회를 선택하는 것이 좋습니다.
실전 팁
💡 Morris 순회는 트리를 임시로 수정하므로 멀티스레드 환경에서는 주의하세요. 동시에 여러 스레드가 순회하면 경쟁 조건이 발생합니다.
💡 디버깅이 어려우므로 각 단계에서 트리 상태를 로깅하는 것이 도움이 됩니다. 스레드 생성/제거 시점을 명확히 추적하세요.
💡 후위 순회의 Morris 구현은 훨씬 복잡합니다. 실무에서 후위 순회가 필요하면 다른 방법을 사용하는 것이 현명합니다.
💡 성능 테스트 결과 작은 트리에서는 재귀가 더 빠를 수 있습니다. 캐시 지역성과 분기 예측 측면에서 재귀가 유리하기 때문입니다. Morris는 메모리가 진짜 문제일 때만 사용하세요.
💡 트리가 읽기 전용이 아니라 수정 가능한 상태라면 스레드를 완벽히 복원하는지 반드시 검증하세요. 복원 실패는 트리를 영구적으로 손상시킵니다.