똑똑한 코드 작성을 위한 실전 알고리즘

197

6

장

이진 트리

6.4

이진 탐색 트리에서 값 제거하기

연결 리스트에서 값을 제거하는 작업은

3

장에서 학습했듯 비교적 직관적인 반면, 이진 탐색 트

리에서 값을 제거하는 작업은 좀 더 까다롭다. 만약 루트 노드에 포함된 값을 제거한다면, ‘함

께 붙어 있던’ 고아가 된 왼쪽과 오른쪽 하위 트리는 어떻게 해야 할까? 또한 매번 작동하는 일

관되게 노력이 최소한으로 필요한 전략이 있어야 한다. 이진 탐색 트리의 루트 노드에 포함된

값을 제거하는 직관적인 해결책을 찾아보자. [그림

6

-

6

]은 값이

19

인 루트 노드를 제거한 후

에 가능한 이진 탐색 트리 두 가지를 보여준다.

그림

6-6

[그

림

6

-

4

]에서

19

를 제거한 후에 가능한 이진 탐색 트리 두 가지

두 옵션 모두 이진 탐색 트리를 유지한다. 각 왼쪽 하위 트리의 값은 여전히 루트 값보다 작거

나 같고, 각 오른쪽 하위 트리의 값은 여전히 루트 값보다 크거나 같다. 두 옵션 모두 이진 탐색

트리를 유지하기 위한 동작을 최소화하려고 노력한다.

●

옵션 #

1

: 왼쪽 하위 트리에서 최댓값을 찾아 제거해 루트 값으로 사용한다.

●

옵션 #

2

: 오른쪽 하위 트리에서 최솟값을 찾아 제거해 루트 값으로 사용한다.

두 옵션 모두 유효하며 필자는 두 번째를 선택한다. 새로운 루트 값

26

은 원래 오른쪽 하위 트

리에서 가장 ...