CH11-2 이진탐색트리(3) 이어서

11-2. 이진 탐색 트리 ③

어제 삽입함수에서 키가 중복되면 안된다는 것 까지 이야기했다.

그 전에 책에 문제 11-1이 흥미로워서 살펴보고 가자.

어제 나는 이진탐색트리의 조건을 다음과 같이 적었다.

그런데 사실 이건 강의안의 설명과 조금 다르다. 강의안에서는

1. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
2. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

이는 곧

왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

를 모든 위치에서 만족함을 의미한다.

내가 필기한건 내용이 조금 다르다. 내가 나름 편하게 이해하려고 해석한 것임.

그런데 문제 11-1을 보면 바로 이런 점을 지적하고 있다.

나처럼 대체하는것은 불가능하다고 한다… 이는 모든 이진탐색트리의 필요조건이지만 이진탐색 트리의 충분조건은 아니기 때문!

예를 한번 생각해보자.