[자료구조] 탐색(Search) 1 - 이진 탐색 트리의 조건 - 11-1 문제

앞서

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

• 이진 탐색 트리의 노드에 저장된 키는 유일하다.
• 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
• 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

을 설명했다
그리고

이진 탐색 트리가 항상 만족하는 조건

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

를 말했다!

그래서 여러분들은 아마
이진 탐색 트리가 되기 위한 조건 중 두번째와 세번째를 다음과 같이 바꾸는것이 더 명확하다고 생각할 수 있다.

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

하지만!!
이것은 불가능하다!!!

이는 모든 이진 탐색트리가 만족하는 조건이 맞긴하지만!!다른 이진 트리도 만족하기 때문이다!

그래서 !!!
어떤 다른 트리가 위 조건을 만족하는지 생각해봐라!!!

네..

이게 아닐까..?

답 을보장

오 ! 맞다!
오늘은 여기까지!
다음 포스트부터는 본격적으로 이진 탐색트리를 배워보자 !