이진 검색 트리에서 중위순회를 했을 때 오름차순으로 나타나는 이유가 무엇인가요?

Question

이진 검색 트리 (BST) 에서 중위순회를 하였을 때 요소들이 오름차순으로 나타나는 이유가 궁금합니다.

왼쪽 서브 트리들의 키들은 그 서브 트리의 루트의 키보다 작다.

오른쪽 서브 트리들의 키들은 그 서브 트리의 루트의 키보다 크다.

왼쪽과 오른쪽 소버 트리도 이진 탐색 트리이다.

라는 정의 때문인가요? 만약 그렇다면 이 정의가 중위순회 후 오름차순으로 나오는 것과 어떤 관계가 있는건지 궁금합니다.

Answer 1

말씀하신 이진탐색트리의 조건때문에 중위순회 시 오름차순으로 정렬이 되는 것입니다.

트리의 left 는 root보다 작은 값, right 는 root보다 큰 값으로 구성이 됩니다.

당연하게도 이 규칙을 제귀적으로 적용해본다면 left 에는 root보다 큰 자식노드가 존재 하지 않을 것이고, 서브 트리들도 이진 탐색 트리로 구성이 됩니다.

결과적으로 이진탐색트리 완성 후 노드들을 보면 제일 왼쪽 노드는 최소값, 제일 오른쪽 노드는 최대값을 가지게 됩니다.

이상태에서 중위순회를 하게 되면 left - root - right 의 순서 각 노드들을 방문하게 됩니다.

이미 이진 검색 트리 구성 시 규칙에 의해 left - root - right 순으로 정렬이 되어있기 때문에

자연스럽게 최소값에서 최대값으로 오름차순으로 순회가 되게 됩니다.

Answer 2

이미 정확히 이해하고 계십니다.

우선 중위순회는 트리의 제일 왼쪽 아래에서 시작하는 것을 의미합니다.

그런데 BST의 왼쪽 제일 아래는 제일 작은 값이 BST의 정의에 의해서 존재하게 됩니다 .

따라서 제일 작은 값에서 시작해서 순서대로 올라오게 되므로 제일 작은값부터 제일 마지막에 제일 큰 값이 나오는 정렬의 형태가 됩니다.

이 특성을 이용하면 최대 최소를 찾거나 혹은 특정 값의 탐색을 빨리 하는 이진탐색을 할수도 있습니다.

Answer 3

https://www.quora.com/Why-is-it-that-Binary-Search-Trees-BST-in-order-traversal-prints-elements-in-increasing-order

첫번째 답변 참고하면 됩니다.

수학적 귀납법 통해 증명하면 됩니다.

먼저 원소 1개일때 중위순회가 오름차순인지 확인합니다.

다른 경우, 왼쪽 - 루트 - 오른쪽으로 순회하는데 이 때 왼쪽과 오른쪽 subtree가 전체 tree보다 작은것과 BST 정의를 이용하면

중위순회가 오름차순인것이 증명됩니다.