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

221

6

장

이진 트리

➎

재귀 조건 : 제거된

value

와 업데이트된 하위 트리의 루트를 받는다.

➏

node

가 균형이 맞지 않는다면(지금은 왼쪽으로 기운 경우) 회전으로 맞춰준다.

➐

삭제된 값을 가진 노드를 반환하기 전에

node

높이를 계산한다.

➑

dequeue()

메서드는 이진 탐색 트리에서 우선순위가 가장 높은 노드를 삭제하고 해당 값을 반환한다.

➒

N

의 값을 감소한 후에, 우선순위가 가장 높았던

value

를 반환한다.

이러한 우선순위 큐 구현의 런타임 성능은

4

장의 힙 기반 우선순위 큐 구현보다

2

배 느리지

만 여전히

O

(

log

N

)을 보인다.

AVL

이진 탐색 트리 구조를 유지하려면 우선순위 큐에 실

제 필요한 것보다 더 많은 작업이 필요하기 때문이다. 그럼에도 제거되는 순서대로

(

value

,

priority

)

쌍에 대해 순회하는 기능이 필요한 경우 이진 탐색 트리가 효율적인 대안이다.

6.11

요약

이진 트리는 동적인 재귀 자료구조로, 왼쪽과 오른쪽 하위 구조에 값을 구성한다. 왼쪽과 오른

쪽 하위 구조를 사용해 값이

N

개인 컬렉션을 각각

N

/

2

개로 고르게 분할할 수 있다. 이진 트리

는 효율적인 구현을 이끄는 수많은 재귀 자료구조의 기반이 된다. 그 예는 다음과 같다.

●

레드 -블랙 트리

red

-

black

tree

는 균형 이진 트리에 대한 더 효율적인 접근이지만 구현은

AVL

트리보다

복잡하다.

●

B

-트리 및

B

+ 트리는 데이터베이스나 파일 시스템에 사용한다.

●

R

-트리 및

R

* 트리는 공간 정보 처리에 사용한다.

●

k

-