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

216

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

6.8

자가 균형 트리 성능 분석하기

compute

_

height

()

헬퍼 함수와 노드 회전 메서드는 모두 상수 시간에 수행되며 함수 어디에

도 추가적인 재귀 호출이나 루프가 없다. 이러한 트리 유지 함수는 노드에서 불균형이 감지될

때만 실행된다.

AVL

트리에 값을 삽입할 때 노드 회전은 두 번 이상 필요하지 않다. 값을 삭제

할 때는 이론적으로 노드 회전이 여러 번 있을 수 있다 (이 장 마지막에 있는 연습 문제에서 이

러한 동작을 알아본다 ). 최악의 경우 노드 회전은

log

(

N

)회 이하이므로 탐색, 삽입 및 삭제의

런타임 성능은 모두

O

(

log

N

)이 된다.

이제 이 장에서 배운 내용을 활용해 재귀 자료구조를 추가로 조사할 준비가 되었다. 이 장을 마

무리하면서 심볼 테이블과 우선순위 큐 데이터 타입을 재고하며 이진 트리가 더 효율적인 구현

을 제공할 수 있는지 여부를 알아보자.

6.9

이진 탐색 트리를 (키, 값) 심볼 테이블로 사용하기

같은 이진 탐색 트리 구조를 사용해

3

장에서 소개한 심볼 테이블 데이터 타입을 구현할 수 있

다(그림

6

-

14

).

그림

6-14

이진 트리를 심볼 테이블로 사용하기(키는 고유 숫자이고 값은 요소 이름이다)

키

값

키

값

키

값

키

값

키

값

키

값

217

6

장

이진 트리

이진 트리를 심볼 테이블로 활용하기 위해, ...