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

222

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

이 작업을 효율적으로 하기 위해 각 이진 노드는 높이를 저장한다.

●

균형 이진 트리로 우선순위 큐를 구현해 (

value

,

priority

) 쌍을 저장할 수 있으며

priority

로 노드

간 비교가 가능하다. 해당 구조의 이점은 우선순위 큐의 구조에 아무런 영향 없이 우선순위 순으로 큐에

저장된 값의 쌍을 중위 순회로 가져올 수 있다는 점이다.

●

심볼 테이블은 이진 탐색 트리에서 각 키가 고유하도록 제한을 강제함으로써 균형 이진 탐색 트리를 사

용해 구현할 수 있다. 하지만 성능은

3

장에서 소개한 해시 테이블 구현보다 효율적이지 않을 것이다.

6.12

연습 문제

1.

재귀

count

(

n

,

target

)

함수를 작성하자. 첫 노드가

n

인 연결 리스트에서

target

이 나

타나는 횟수를 반환하도록 한다.

2.

노드가

N

개이고 가장 큰 두 수를 찾는 시간이

O

(

N

)인 이진 탐색 트리 구조를 구상하자.

그다음에는 노드가

N

개이고 가장 큰 두 수를 찾는 시간이

O

(

1

)인 이진 탐색 트리 구조를

구상하자.

3.

이진 탐색 트리에서

k

번째로 작은 키를 찾으려면 어떻게 해야 할까? 노드

k

개를 모두 방문

할 때까지 전체 트리를 순회하는 비효율적인 방법 대신에,

k

가

0

에서

N

-

1

사이일 때

k

번

째 작은 수를 반환하는

select

(

k

)

함수를

BinaryTree

에 추가하자. 효율적으로 구현하려

면

BinaryNode

클래스에 추가로 항목

N

을 저장하기 위한 인자가 필요하다. 이때

N

은 해

당 노드를 루트로 하는 ...