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

123

12

장

TreeMap 클래스

}

}

각 노드는 키-값 쌍을 포함하며, 두 자식 노드인

left

와

right

변수를 참조합니다. 자식 노드

는 둘 중 하나 또는 둘 다

null

이 될 수 있습니다.

Map

인터페이스의 일부 메서드는

size

와

clear

처럼 구현하기 쉽습니다

(파일명:

MyTreeMap.

java

)

.

public int size

()

{

return size

;

}

public void clear

()

{

size

=

0

;

root

=

null

;

}

size

메서드는 확실히 상수 시간입니다.

clear

메서드는 상수 시간으로 보지만, 고려해야 할 점이 있습니다.

root

변수가

null

이 되면

가비지 컬렉터는 트리에 있는 노드 객체의 수거를 요청하며, 이는 선형 시간이 걸립니다. 가비

지 컬렉터가 수행하는 작업 시간을 세야 할까요? 필자는 그렇다고 생각합니다.

다음 절에서는

get

과

put

메서드와 같이 가장 중요한 몇 개 메서드를 채우겠습니다.

12.4

TreeMap

구현하기

이 책의 코드 저장소에는 다음과 같은 소스 파일이 있습니다.

●

MyTreeMap

.

java

앞 절의 코드와 빠진 메서드의 개요가 담겨 있습니다.

●

MyTreeMapTest

.

java

MyTreeMap

클래스의 유닛 테스트 파일입니다.

124

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