완전히 균형 잡힌 이진 검색 트리가 될 요소 삽입 순서?

Question

나는 교과서에서이 문제를 해결하려고 노력 오전에 보일 수 없다 완전히 이해 :

• 이 가 완벽하게 균형 이진 검색 트리가 발생할 것으로 이러한 요소 삽입의 순서를 결정합니다.

• 요소가있다 : {10, 11, 15, 19, 23, 78, 42, 56, 18, 13, 12, 38, 47}

내가를 만들 수 있어요 BST와 올바르게 균형을 맞추지 만 균형 잡힌 트리를 보장하기 위해 트리를 구성하기 전에 요소를 정렬하는 방법을 모르겠습니다.

Answer 1

먼저 이러한 요소를 정렬 한 다음 균형 잡힌 BST를 구성하기 시작합니다. 트리의 균형을 보장하기 위해 하나의 요소를 트리의 루트로 선택해야하므로 정렬 된 요소에서 중간 요소를 선택합니다. 그러면 우리는 어느 것이 왼쪽 아이인지 선택해야합니다. 두 개의 정렬 된 하위 배열이 왼쪽에 있습니다. 하나는 왼쪽에 있고 다른 하나는 오른쪽에 있습니다. Divide-and-Conquer가 있습니다.이 두 배열은 원래 문제의 하위 문제입니다. 그런 다음 왼쪽 정렬 된 하위 배열에서 가운데 ​​자식 요소를 왼쪽 자식 노드로 선택하고 오른쪽 정렬 된 하위 배열에서 오른쪽 자식 노드로 중간 요소를 선택하는 방식으로 계속합니다.

그래서 균형 잡힌 트리를 보장하기 위해 트리를 구성하기 전에 요소의 순서는 다음과 같이 결정됩니다

• 종류의 요소.
• 첫 번째 요소는 정렬 된 요소의 가운데 요소입니다.
• 두 번째 요소는 왼쪽 정렬 된 배열의 중간 요소입니다.
• 세 번째 요소는 오른쪽 정렬 된 배열의 중간 요소입니다.
• 등등. 만약주는 요소

는 순서는 다음
19, 12, 42, 10, 15, 23, 56, 11, 13, 18, 38, 47, 78