알고리즘 - 13. 이진 탐색 트리 (BST)
이진 탐색 트리를 언제 사용하는가
효율적인 연산으로 동적으로 변하는 정렬된 컬렉션을 유지해야 할 때 이진 탐색 트리를 사용합니다. 정렬된 데이터 검색에 가장 흔히 사용되지만, BST는 다음과 같은 용도로도 적용할 수 있습니다:
- 데이터베이스 인덱싱 (고전적인 사용 사례) - B-트리와 B+-트리는 BST의 변형
- 빈번한 업데이트가 있는 우선순위 큐 (힙 연산이 충분하지 않을 때)
- 값 범위 내의 모든 요소 찾기 - 예: 80-90점 사이의 모든 점수. BST는 범위 내의 실제 요소를 반환합니다 ("$50-$100 가격대의 모든 제품 표시" 등), 세그먼트 트리는 범위 집계 쿼리 ("인덱스 3부터 7까지 요소의 합" 등)에 탁월합니다
- 순서 통계 - k번째로 작은/큰 요소 찾기
- 구간 트리 - 겹치는 구간을 관리하는 BST 기반 구조 (오후 2-4시, 오후 3-5시의 캘린더 이벤트 등). "오후 3:30과 겹치는 이벤트는?" 또는 "오후 2-3시 슬롯과 충돌하는 모든 회의 찾기"를 효율적으로 대답
- 파일 시스템 - 디렉토리 구조와 파일 조직
- 빈번한 삽입/삭제로 정렬 순서를 유지해야 하는 모든 문제
예제 문제
음악 플레이리스트 매니저: 노래 제목으로 정렬된 플레이리스트를 유지하는 음악 플레이어를 만들고 있습니다. ["Bohemian Rhapsody", "Imagine", "Hey Jude", "Let It Be", "Yesterday", "Come Together"]와 같은 노래를 추가하는 연산을 효율적으로:
- 알파벳 순서를 유지하면서 새 노래 추가
- 특정 노래를 검색하여 재생
- 플레이리스트에서 노래 삭제
- 특정 문자나 접두사로 시작하는 모든 노래 찾기
모든 연산 처리 후:
- BST는 노래를 알파벳 순서로 유지
- "Hey Jude" 검색은 평균 O(log n) 시간 소요
- 중위 순회로 정렬된 순서로 모든 노래를 얻을 수 있음 (왼쪽 부분트리 → 현재 노드 → 오른쪽 부분트리 방문하여 알파벳 순서 획득)
- "H로 시작하는 모든 노래" 같은 범위 쿼리가 효율적 (알파벳 순서로 "H"와 "I" 사이의 모든 값 찾기)
답: BST는 자동으로 정렬 순서를 유지하므로, 수동 정렬 없이 이 모든 연산을 효율적으로 만듭니다.
이진 탐색 트리가 실제로 하는 일
이진 탐색 트리는 단순한 규칙을 통해 요소를 정렬된 순서로 유지하는 계층적 자료 구조입니다. 세 가지 핵심 연산을 제공합니다:
- SEARCH: 요소가 트리에 존재하는지 찾기
- INSERT: BST 속성을 유지하면서 새 요소 추가
- DELETE: 요소를 제거하고 트리를 재구성
(참고: UPDATE는 별도의 연산이 아닙니다. 값을 변경하려면 DELETE + INSERT가 필요합니다 - 새 값이 트리의 다른 위치에 속할 수 있기 때문입니다)
음악 플레이리스트를 알파벳 순으로 정리하는 것으로 생각해보세요:
- SEARCH: "이 노래가 내 플레이리스트에 있나?"
- INSERT: "이 새 노래를 올바른 알파벳 위치에 추가"
- DELETE: "이 노래를 제거하고 플레이리스트를 정렬된 상태로 유지"
연산 동작 방식
SEARCH 연산 - "이 값이 트리에 있나?"
search(root, 42)를 호출하면:
- 루트 노드에서 시작
- 42를 현재 노드의 값과 비교
- 42가 작으면 왼쪽으로, 크면 오른쪽으로
- 찾으면 true를 반환, null에 도달하면 false
- 핵심 효율성: 각 단계에서 남은 트리의 절반을 제거
INSERT 연산 - "순서를 유지하면서 이 값을 추가"
insert(root, 35)를 호출하면:
- 검색과 같은 비교 경로를 따름 (작으면 왼쪽, 크면 오른쪽)
- 빈 자리(null)에 반드시 도달 - 이유: 값이 이미 존재하면 (삽입 건너뛰기) 또는 잎 노드의 빈 자식에 도달할 때까지 계속 내려감
- 그 빈 자리에 값 35로 새 노드 생성
- BST 속성 유지: 왼쪽 부분트리의 모든 값 < 노드 < 오른쪽 부분트리의 모든 값
예제 - 35 삽입:
현재 트리: 35를 삽입하는 경로: 삽입 후:
50 1. 50에서: 35<50, 왼쪽으로 50
/ \ 2. 30에서: 35>30, 오른쪽으로 / \
30 70 3. 40에서: 35<40, 왼쪽으로 30 70
/ \ 4. NULL(비어있음)에 도달! / \
20 40 5. 여기에 노드 생성 20 40
/
35DELETE 연산 - "이 값을 제거하고 재구성"
delete(root, 50)을 호출하면 세 가지 경우를 처리:
-
잎 노드: 단순히 제거 (다른 노드에 영향 없음)
-
자식 하나: 노드를 자식으로 교체 (자식과 모든 후손들이 상대적 순서 유지)
-
자식 둘: 중위 후속자 (오른쪽 부분트리의 최소값) 찾기, 값 교체, 후속자 삭제
왜 "중위 후속자" = "오른쪽 부분트리의 최소값": 이 용어는 정렬 순서에서 유래합니다. 모든 값을 정렬 순서로 나열하면, "후속자"는 삭제하려는 값 다음의 값입니다. 두 자식을 가진 노드의 경우, 이 다음 값은 항상 오른쪽 부분트리의 최소값입니다. 예: [30, 40, 50, 60, 70]에서 50을 삭제하려면 60(다음 값)이 필요하며, 이는 오른쪽으로 한 번 이동(70의 부분트리로) 후 가능한 한 왼쪽으로 이동(60을 찾기)하여 찾습니다.
왜 "가능한 한 왼쪽으로 이동"이 최소값을 찾는가: BST에서 작은 값은 항상 왼쪽에 있습니다. 따라서 어떤 노드에서 시작하여 더 이상 갈 수 없을 때까지 왼쪽으로 계속 가면, 해당 부분트리의 최소값에 도달합니다. 이것이 바로 중위 순회가 다음 요소를 찾는 방법입니다 - 노드를 방문한 후 오른쪽 부분트리로 가서 즉시 가능한 한 왼쪽으로 갑니다.
따라서 중위 후속자는 오른쪽 부분트리의 가장 왼쪽 노드입니다.
이들이 BST 순서를 유지하는 이유:
자식 하나인 경우 - 30 삭제 (오른쪽 자식 40만 있음):
삭제 전: 삭제 후: 왜 작동하는가:
50 50 40의 부분트리의 모든 노드 (40, 35, 45)
/ \ / \ 는 30보다 크고 50보다 작았음
30 70 40 70 여전히 30의 위치보다 크고 50보다 작음!
\ / \ 순서가 보존됨!
40 35 45
/ \
35 45자식 둘인 경우 - 50 삭제:
삭제 전: 삭제 후: 왜 작동하는가:
50 60 60은 오른쪽 부분트리에서 가장 작았음
/ \ / \ 따라서: 60 > 왼쪽의 모든 것 (30,40)
30 70 30 70 그리고: 60 < 오른쪽의 나머지 (70,80)
/ \ \ 완벽한 교체!
60 80 80이러한 연산이 발생하는 시점
이러한 연산은 명시적으로 호출할 때만 발생합니다:
const bst = new BinarySearchTree();
// INSERT: 명시적으로 요소 추가
bst.insert(50); // 루트 생성
bst.insert(30); // 50의 왼쪽으로
bst.insert(70); // 50의 오른쪽으로
bst.insert(40); // 30의 오른쪽으로
// SEARCH: 요소 존재 확인
let found = bst.search(40); // true 반환
let notFound = bst.search(25); // false 반환
// DELETE: 요소 제거
bst.delete(30); // 30 제거, 트리 재구성BST의 아름다움은 정렬 순서를 자동으로 유지한다는 것입니다 - 데이터를 수동으로 정렬하거나 재구성할 필요가 없습니다!
가장 중요한 통찰
모든 노드에서 BST 속성(왼쪽 < 부모 < 오른쪽)이 검색을 위한 결정 트리를 생성합니다 - 그리고 "작으면 왼쪽, 크면 오른쪽"을 일관되게 따름으로써, 각 단계에서 검색 공간의 절반을 제거하여 균형 트리에서 O(log n) 검색을 달성합니다.
멘탈 노트: 알고리즘의 천재성은 정렬 순서를 트리 구조 자체에 인코딩하는 데 있습니다. 각 노드에서 비교를 기반으로 왼쪽 또는 오른쪽으로 가는 하나의 결정만 내리면 됩니다. 각 레벨에서의 이 간단한 이진 결정이 자동으로 정렬된 데이터를 유지하고 배열 없이 이진 검색을 가능하게 합니다.
결정 프레임워크
BST 연산에는 다음과 같은 핵심 결정이 포함됩니다:
검색 중:
- 현재 노드가 null인가? 찾지 못함 반환
- 대상이 현재 값과 같은가? 찾음 반환
- 대상이 현재보다 작은가? 왼쪽으로 이동
- 대상이 현재보다 큰가? 오른쪽으로 이동
삽입 중:
- 새 값을 현재 노드와 비교 (검색과 동일)
- 새 값이 작으면 왼쪽으로, 크면 오른쪽으로
- 빈 자리(null)를 찾을 때까지 계속 내려가기
- 그 빈 위치에 새 노드 생성
삭제 중 (가장 복잡):
- 자식 없음 (잎)? 단순히 제거
- 자식 하나? 그 자식으로 교체
- 자식 둘? 중위 후속자 찾기, 값 교환, 후속자 삭제
BST 속성이 중요한 이유
BST 속성은 모든 연산이 전체 부분트리를 무시할 수 있게 보장합니다:
BST 속성 없이 (정렬되지 않은 트리):
값 35를 찾으려면:
50
/ \
70 30
/ \ / \
20 40 60 10
모든 7개 노드를 확인해야 함 - O(n) 시간!BST 속성과 함께:
값 35를 찾으려면:
50
/ \
30 70 ← 오른쪽 부분트리 전체 무시!
/ \
20 40 ← 30의 왼쪽만 확인, 20 무시!
경로: 50 → 30 → 40 → 찾지 못함 (3번 확인만)BST 속성이 보장하는 것:
- 왼쪽 부분트리의 모든 값 < 노드 값
- 오른쪽 부분트리의 모든 값 > 노드 값
- 이는 모든 부분트리에 재귀적으로 적용됨
- 결과: 각 단계에서 남은 노드의 ~50%를 제거 가능
이것이 균형 BST가 O(log n) 연산을 달성하는 이유입니다 - 높이가 필요한 최대 비교 횟수를 결정합니다!
코드
// 트리의 노드 구조
class TreeNode {
constructor(value) {
this.value = value;
this.left = null; // 왼쪽 자식 (작은 값)
this.right = null; // 오른쪽 자식 (큰 값)
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
// SEARCH: 값이 트리에 존재하는지 찾기
search(targetValue) {
return this.searchFromNode(this.root, targetValue);
}
searchFromNode(currentNode, targetValue) {
// 베이스 케이스: 경로의 끝에 도달
const reachedEndOfPath = currentNode === null;
if (reachedEndOfPath) {
return false; // 값을 찾지 못함
}
// 비교를 위해 현재 노드의 값 추출
const currentValue = currentNode.value;
// 결정 프레임워크: 3방향 비교
const foundTarget = targetValue === currentValue;
const shouldSearchLeft = targetValue < currentValue;
const shouldSearchRight = targetValue > currentValue;
if (foundTarget) {
return true; // 대상을 성공적으로 찾음!
}
if (shouldSearchLeft) {
// 대상이 더 작음 - 왼쪽 부분트리만 검색
const leftSubtree = currentNode.left;
return this.searchFromNode(leftSubtree, targetValue);
}
if (shouldSearchRight) {
// 대상이 더 큼 - 오른쪽 부분트리만 검색
const rightSubtree = currentNode.right;
return this.searchFromNode(rightSubtree, targetValue);
}
}
// INSERT: BST 속성을 유지하면서 새 값 추가
insert(newValue) {
// 루트에서 삽입 시작, 필요시 루트 업데이트
this.root = this.insertIntoSubtree(this.root, newValue);
}
insertIntoSubtree(currentNode, newValue) {
// 베이스 케이스: 새 노드를 위한 빈 자리 발견
const foundEmptySpot = currentNode === null;
if (foundEmptySpot) {
const newNode = new TreeNode(newValue);
return newNode;
}
// 비교를 위해 현재 값 추출
const currentValue = currentNode.value;
// 베이스 케이스: 중복 발견 - 삽입 불필요
const isDuplicate = newValue === currentValue;
if (isDuplicate) {
return currentNode; // 변경되지 않은 노드 반환
}
// 결정 프레임워크: 삽입 방향 결정
const insertToLeft = newValue < currentValue;
if (insertToLeft) {
// 새 값이 더 작음 - 왼쪽 부분트리에 삽입
const updatedLeftSubtree = this.insertIntoSubtree(
currentNode.left,
newValue
);
currentNode.left = updatedLeftSubtree;
} else {
// 새 값이 더 큼 - 오른쪽 부분트리에 삽입
const updatedRightSubtree = this.insertIntoSubtree(
currentNode.right,
newValue
);
currentNode.right = updatedRightSubtree;
}
return currentNode;
}
// DELETE: 값을 제거하고 BST 속성 유지
delete(valueToDelete) {
// 루트에서 삭제 시작, 필요시 루트 업데이트
this.root = this.deleteFromSubtree(this.root, valueToDelete);
}
deleteFromSubtree(currentNode, valueToDelete) {
// 베이스 케이스: 트리에서 값을 찾지 못함
const nodeNotFound = currentNode === null;
if (nodeNotFound) {
return null;
}
// 비교를 위해 현재 값 추출
const currentValue = currentNode.value;
// 결정 프레임워크: 삭제할 노드 찾기
const searchLeft = valueToDelete < currentValue;
const searchRight = valueToDelete > currentValue;
const foundNodeToDelete = valueToDelete === currentValue;
if (searchLeft) {
// 삭제할 값이 왼쪽 부분트리에 있음
const updatedLeftSubtree = this.deleteFromSubtree(
currentNode.left,
valueToDelete
);
currentNode.left = updatedLeftSubtree;
return currentNode;
}
if (searchRight) {
// 삭제할 값이 오른쪽 부분트리에 있음
const updatedRightSubtree = this.deleteFromSubtree(
currentNode.right,
valueToDelete
);
currentNode.right = updatedRightSubtree;
return currentNode;
}
if (foundNodeToDelete) {
// 삭제할 노드를 찾음 - 세 가지 경우 처리
// 결정 프레임워크: 자식 수에 따른 삭제 경우
const hasNoChildren =
currentNode.left === null && currentNode.right === null;
const hasOnlyRightChild =
currentNode.left === null && currentNode.right !== null;
const hasOnlyLeftChild =
currentNode.right === null && currentNode.left !== null;
const hasBothChildren =
currentNode.left !== null && currentNode.right !== null;
if (hasNoChildren) {
// 경우 1: 잎 노드 - 단순히 제거
return null;
}
if (hasOnlyRightChild) {
// 경우 2a: 오른쪽 자식만 존재 - 그것으로 교체
const rightChild = currentNode.right;
return rightChild;
}
if (hasOnlyLeftChild) {
// 경우 2b: 왼쪽 자식만 존재 - 그것으로 교체
const leftChild = currentNode.left;
return leftChild;
}
if (hasBothChildren) {
// 경우 3: 두 자식 모두 존재 - 후속자 전략 사용
// 중위 후속자 찾기 (오른쪽 부분트리의 최소값)
const rightSubtree = currentNode.right;
const successorNode = this.findMinimumNode(rightSubtree);
const successorValue = successorNode.value;
// 현재 노드의 값을 후속자의 값으로 교체
currentNode.value = successorValue;
// 오른쪽 부분트리에서 후속자 제거 (최대 한 자식을 가짐)
const updatedRightSubtree = this.deleteFromSubtree(
rightSubtree,
successorValue
);
currentNode.right = updatedRightSubtree;
return currentNode;
}
}
}
// 헬퍼: 부분트리에서 최소값을 가진 노드 찾기
findMinimumNode(startNode) {
// 최소값은 항상 가장 왼쪽 노드
let currentNode = startNode;
// 더 이상 갈 수 없을 때까지 왼쪽으로 계속 이동
while (currentNode.left !== null) {
currentNode = currentNode.left;
}
// 이것이 가장 왼쪽 (최소) 노드
return currentNode;
}
// 보너스: 중위 순회 (정렬된 배열 반환)
getSortedValues() {
const sortedArray = [];
this.collectInOrder(this.root, sortedArray);
return sortedArray;
}
collectInOrder(currentNode, resultArray) {
// 베이스 케이스: null 노드는 아무것도 기여하지 않음
const isNullNode = currentNode === null;
if (isNullNode) {
return;
}
// 중위 순회: 왼쪽 -> 현재 -> 오른쪽
const leftSubtree = currentNode.left;
const currentValue = currentNode.value;
const rightSubtree = currentNode.right;
// 단계 1: 왼쪽 부분트리의 모든 값 처리 (작은 값)
this.collectInOrder(leftSubtree, resultArray);
// 단계 2: 현재 노드의 값 처리
resultArray.push(currentValue);
// 단계 3: 오른쪽 부분트리의 모든 값 처리 (큰 값)
this.collectInOrder(rightSubtree, resultArray);
}
}
// === 사용 예제: 음악 플레이리스트 매니저 ===
function demonstrateMusicPlaylist() {
const playlist = new BinarySearchTree();
// 플레이리스트에 추가할 노래
const songsToAdd = [
"Bohemian Rhapsody",
"Imagine",
"Hey Jude",
"Let It Be",
"Yesterday",
"Come Together",
];
// 각 노래를 플레이리스트에 추가
console.log("=== 플레이리스트에 노래 추가 ===");
for (const songTitle of songsToAdd) {
playlist.insert(songTitle);
console.log(`✓ 추가됨: "${songTitle}"`);
}
// 검색 기능 테스트
console.log("\n=== 노래 검색 테스트 ===");
const songToFind = "Hey Jude";
const songExists = playlist.search(songToFind);
console.log(`"${songToFind}"가 존재하는가? ${songExists}`); // true
const missingSong = "Stairway to Heaven";
const notInPlaylist = playlist.search(missingSong);
console.log(`"${missingSong}"가 존재하는가? ${notInPlaylist}`); // false
// 정렬된 순서로 모든 노래 표시
console.log("\n=== 모든 노래 (알파벳 순) ===");
const allSongsInOrder = playlist.getSortedValues();
console.log(allSongsInOrder);
// 출력: ["Bohemian Rhapsody", "Come Together", "Hey Jude", "Imagine", "Let It Be", "Yesterday"]
// 플레이리스트에서 노래 제거
console.log("\n=== 노래 제거 ===");
const songToRemove = "Hey Jude";
console.log(`"${songToRemove}"를 플레이리스트에서 제거 중...`);
playlist.delete(songToRemove);
// 업데이트된 플레이리스트 표시
const updatedPlaylist = playlist.getSortedValues();
console.log("업데이트된 플레이리스트:", updatedPlaylist);
// 출력: ["Bohemian Rhapsody", "Come Together", "Imagine", "Let It Be", "Yesterday"]
// 최종 트리 구조 시각화
console.log("\n=== 최종 트리 구조 ===");
console.log(`
"Imagine"
/ \\
"Come Together" "Let It Be"
/ \\
"Bohemian Rhapsody" "Yesterday"
`);
}
// 데모 실행
demonstrateMusicPlaylist();의심 버스터
일반적인 의심: "두 자식을 가진 노드를 삭제할 때, 왜 특별히 중위 후속자(오른쪽 부분트리의 최소값)를 선택하는가? 왜 중위 전임자(왼쪽 부분트리의 최대값)나 다른 노드가 아닌가?"
이것은 임의적으로 보입니다 - 알고리즘이 전임자로도 작동하는 것 같은데, 왜 모든 교과서가 후속자를 고집하는 걸까요? 이 선택이 왜 중요한지 살펴보겠습니다.
왜 이것이 임의적으로 보이는가
두 자식을 가진 노드 50 삭제를 고려해봅시다:
50 (이것을 삭제)
/ \
30 70
/ \ / \
20 40 60 80
옵션:
1. 전임자(40)로 교체 - 왼쪽 부분트리의 최대값
2. 후속자(60)로 교체 - 오른쪽 부분트리의 최소값
3. 70으로 교체? 30은? 왜 안 되는가?전임자와 후속자 모두 작동하는 것 같습니다 - 둘 다 BST 속성을 유지합니다!
핵심 통찰: BST 속성 유지
여기가 중요한 요구사항입니다: 교체 값은 반드시:
- 왼쪽 부분트리의 모든 값보다 커야 함
- 오른쪽 부분트리의 모든 값보다 작아야 함
- 현재 위치에서 삭제하기 쉬워야 함
각 옵션을 확인해봅시다:
옵션 1: 중위 전임자 (40)
삭제 전: 50을 40으로 교체 후:
50 40
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 - 60 80
✓ 40 > 왼쪽 부분트리의 모든 것 (20, 30)
✓ 40 < 오른쪽 부분트리의 모든 것 (60, 70, 80)
✓ 왼쪽 부분트리에서 40을 삭제하기 쉬움 (잎이거나 자식 하나)옵션 2: 중위 후속자 (60)
삭제 전: 50을 60으로 교체 후:
50 60
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 40 - 80
✓ 60 > 왼쪽 부분트리의 모든 것 (20, 30, 40)
✓ 60 < 오른쪽 부분트리의 모든 것 (70, 80)
✓ 오른쪽 부분트리에서 60을 삭제하기 쉬움 (잎이거나 자식 하나)옵션 3: 70 같은 임의의 노드
50을 70으로 교체 후:
70
/ \
30 70 (중복?!)
/ \ / \
20 40 60 80
✗ 70은 오른쪽 부분트리의 모든 것보다 작지 않음 (70과 같고, 60보다 큼)
✗ 중복을 만들거나 BST 속성을 위반함왜 특별히 후속자 (또는 전임자)인가?
수학적 보장: 중위 후속자와 전임자는 모든 요구사항을 만족하는 유일한 두 값입니다:
-
중위 후속자 = 삭제된 노드보다 큰 최소값
- 왼쪽 부분트리의 모든 것보다 큼이 보장됨
- 오른쪽 부분트리의 모든 것보다 작음이 보장됨 (자신 제외)
- 항상 최대 한 자식만 가짐 (정의상 왼쪽 자식 없음)
-
중위 전임자 = 삭제된 노드보다 작은 최대값
- 오른쪽 부분트리의 모든 것보다 작음이 보장됨
- 왼쪽 부분트리의 모든 것보다 큼이 보장됨 (자신 제외)
- 항상 최대 한 자식만 가짐 (정의상 오른쪽 자식 없음)
-
다른 값 = 최소 하나의 부분트리에 대해 BST 속성 위반
왜 후속자가 약간 선호되는가
둘 다 올바르게 작동하지만, 후속자가 일관성을 위해 자주 선택됩니다:
- 표준 관습: 대부분의 교과서가 균일성을 위해 후속자 사용
- 균형 고려: 무작위 삭제에서 교대로 사용하면 더 나은 균형 가능
- 구현 간단성: 최소값(가장 왼쪽) 찾기가 최대값 찾기보다 깔끔한 경우가 많음
- 역사적 선례: 초기 BST 논문이 후속자 사용
아름다운 속성: 왜 후속자/전임자가 최대 한 자식만 갖는가
이것이 삭제를 효율적으로 만드는 우아한 부분입니다:
중위 후속자 (오른쪽 부분트리의 최소값):
노드
\
오른쪽 부분트리
/
후속자 (왼쪽 자식 없음!)
\
오른쪽 자식이 있을 수도- 만약 후속자가 왼쪽 자식을 가지면, 그 자식이 더 작을 것
- 하지만 그러면 그 자식이 후속자가 되어야 함
- 모순! 따라서 후속자는 오른쪽 자식만 가질 수 있음
중위 전임자 (왼쪽 부분트리의 최대값):
노드
/
왼쪽 부분트리
\
전임자 (오른쪽 자식 없음!)
/
왼쪽 자식이 있을 수도- 만약 전임자가 오른쪽 자식을 가지면, 그 자식이 더 클 것
- 하지만 그러면 그 자식이 전임자가 되어야 함
- 모순! 따라서 전임자는 왼쪽 자식만 가질 수 있음
이 속성은 후속자/전임자를 그 위치에서 삭제할 때, 경우 1(잎) 또는 경우 2(자식 하나)만 마주치게 됨을 보장합니다 - 복잡한 경우 3을 다시 만나지 않습니다!
구체적인 예: 알고리즘이 최적인 이유
삭제를 추적하여 이 접근법이 왜 우아한지 봅시다:
// 이 트리에서 50 삭제:
// 50
// / \
// 30 70
// / \ / \
// 20 40 60 80
// \
// 65
//
deleteNode(root, 50):
// 노드 50 찾음 - 두 자식 있음
// 후속자 찾기: 오른쪽으로 한 번, 그 다음 null까지 왼쪽으로
successor = findMin(70의 부분트리) = 60
// 50의 값을 60으로 교체
node.value = 60
// 이제 오른쪽 부분트리에서 60 삭제
// 60은 자식 하나(65)를 가짐, 따라서 경우 2 - 간단!
// 최종 트리:
// 60
// / \
// 30 70
// / \ / \
// 20 40 65 80알고리즘은 우아하게 복잡한 두 자식 경우를 더 간단한 한 자식 경우로 줄입니다!
결론: 중위 후속자(또는 전임자)를 사용하는 것은 임의적이지 않습니다 - 그들은 삭제된 노드를 교체할 때 BST 속성을 유지하는 유일한 값입니다. 그들 사이의 선택은 작은 구현 세부사항이지만, 그들 중 하나를 사용하기 위한 수학적 요구사항은 절대적입니다.