자바로 배우는 핵심 자료구조와 알고리즘: 기술 면접에 필요한 실용주의 자료구조와 알고리즘

122

자바로 배우는 핵심 자료구조와 알고리즘

양측에

2

로 로그를 씌울 수 있습니다.

log

2

n

≈

h

이는 트리에 노드가 가득 차면 트리 높이는

log

n

에 비례함을 의미합니다

(즉, 각 수준이 노드를 최

대 개수만큼 포함할 때 )

따라서 이진 탐색 트리에서

log

n

에 비례하는 시간으로 키를 찾을 수 있다

고 기대합니다. 트리가 가득 차 있거나 부분적으로 가득 찼을 때도 그렇습니다. 하지만 앞으로

볼 것처럼 항상 그러한 것은 아닙니다.

log

n

에 비례하는 시간이 걸리는 알고리즘을 로그 시간

logarithmic

또는

log

time

이라고 합니다. 증가

차수는

O

(

log

n

)에 해당합니다.

12.3

실습

10

이번 실습에서는 이진 탐색 트리로

Map

인터페이스를 구현합니다. 다음은

MyTreeMap

클래스

구현의 시작 부분입니다

(파일명:

MyTreeMap.java

)

.

public class MyTreeMap

<

K

,

V

>

implements Map

<

K

,

V

>

{

private int size

=

0

;

private Node root

=

null

;

인스턴스 변수인

size

는 키의 개수를 추적하고

root

는 트리의 루트 노드를 참조합니다. 트리

가 비면

root

는

null

이 되고

size

는

0

이 됩니다.

MyTreeMap

클래스 내부에 정의된

Node

클래스는 ...