문제 11-1 이진 탐색 트리의 조건

이진 탐색 트리가 되기 위한 조건 정리

1. 이진 탐색 트리의 노드에 저장된 키는 유일하다

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

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

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

2와 3의 조건을 다음과 같이 바꾼다면

부모 노드의 키가 왼쪽 자식 노드의 키보다 크다.

부모 노드의 키가 오른쪽 자식 노드의 키보다 작다.

이는 모든 이진 탐색 트리가 만족하는 조건이긴 하지만, 이진 탐색 트리만 만족하는 조건은 아니기에 이렇게 대채하는 것은 불가능하다.

위의 두가지 조건을 만족하지만 이진 탐색 트리가 아닌 '이진 트리의 예'는 ?

루트 노드인 10보다 큰 값이 왼쪽 서브 트리에 존재한다. 때문에 이는 이진 탐색 트리가 될 수 없다. 즉 2 와 3의 조건을 바꿔서는 안된다.