연습문제 2.2

최악의 경우 member 함수는 약 2d번 비교를 수행한다.

여기서 d는 트리의 깊이다.

질의 대상 원소와 같을지도 모르는 후보 원소(말하자면 ＜가 false를 반환하거나, ≤가 true를 반환한 마지막 원소)들을 추적하고,

트리의 리프에서만 동등성을 체크하게 만듦으로써 최대 d + 1번만 비교를 수행하도록 member를 다시 작성하라.


연습문제 2.3

이진 검색 트리에 이미 존재하는 원소를 넣으면, 그 원소를 기존 원소와 구분할 방법이 없어도 비교 경로에 있는 모든 원소를 복사하게 된다.

이런 복사를 피하기 위해 예외를 사용하도록 insert를 재작성하라.

반복을 1회 할 때마다 예외 핸들러를 설정하지 말고, 삽입 1회에 대해 예외 핸들러를 1개만 설정하라.


연습문제 2.4

연습문제 2.2와 2.3의 아이디어를 합쳐서 불필요한 복사를 하지 않으면서도 비교도 d + 1번보다 많이 하지 않는 insert를 작성하라.


연습문제 2.5

여러 객체 사이뿐 아니라, 단일 객체 안에서 공유가 도움이 될 수 있다.

예를 들어, 어떤 노드의 두 하위 트리가 동일하다면 그들을 같은 트리로 표현할 수 있다.

a)

이 아이디어를 사용해 Elem * int → Tree 타입인 함수 complete를 만들어라.

complete(x, d)는 모든 노드에 x가 들어 있는 깊이 d인 트리를 만든다(물론 이 함수는 집합을 추상화한다는 관점에서는 전혀 의미가 없다).

이 함수는 O(d) 시간에 작동해야 한다.

b)

complete 함수를 확장해서 임의 크기의 균형 잡힌 트리를 만들게 하라.

이 complete가 만드는 트리는 완전한 이진 트리일 필요는 없지만 가능한 한 균형이 잡혀야 한다.

즉, 어떤 노드를 선택하더라도 그 노드의 두 하위 트리의 크기 차이가 최대 1이어야 한다.

이 함수는 O(log n) 시간에 실행돼야 한다(힌트: 주어진 크기 m에 대해 한 쪽은 크기가 m이고, 다른 쪽은 크기가 m + 1인 트리 쌍을 만들어내는 create2라는 도우미 함수를 사용하라).