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

218

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

표

6-5

3

장의 해시 테이블과

AVL

심볼 테이블 구현 비교(초)

타입 개방 주소법 분리 연쇄법

AVL

트리

구성 시간

0

.

54 0

.

38 5

.

00

접근 시간

0

.

13 0

.

13 0

.

58

6.10

이진 탐색 트리를 우선순위 큐로 사용하기

4

장에서 소개한 힙 자료구조가 이진 트리 구조에 기반한다는 점을 고려하면,

AVL

이진 탐색

트리를 사용해 구현된 우선순위 큐의 런타임 성능을 비교해보는 것은 자연스러운 일이다. 해당

이진 탐색 트리는

priority

를 이용해 구조를 탐색한다 (그림

6

-

15

).

그림

6-15

이진 트리를 우선순위 큐로 사용하기(우선순위는 숫자이고 값은 요소 심볼이다)

이진 탐색 트리로 우선순위 큐를 구현하면 두 가지 장점이 있다.

●

배열 기반 힙은 개수가 고정된 값을 위한 저장 공간을 미리 생성해야 한다. 반면에 이진 탐색 트리를 사

용하면 구조가 필요한 만큼 커질 수 있다.

219

6

장

이진 트리

●

힙 구조에서는 값을 꺼내지 않고 우선순위대로 우선순위 큐를 순회

6

할 수 있는 반복자를 제공할 방법이

없다. 반면에 이진 탐색 트리