키 목록이 주어지면 그 목록의 거의 완전한 이진 검색 트리를 어떻게 찾을 수 있습니까?

Question

파이썬에서 구현 된 아이디어에 대한 답변을 보았습니다 (파이썬에 익숙하지 않은 경우) - 좀 더 일반적인 알고리즘을 찾고있었습니다.

EDIT : 설명을 위해

: 우리 정수 키의 목록이 주어진다 인사 : 23 44 88 12 74 32 7 39 10

그리스트가 임의로 선택되었다. 우리는이 목록에서 거의 완전한 (또는 완전한) 이진 탐색 트리를 생성해야합니다. 그런 나무 하나만 있으면 돼 ... 어떻게 찾 겠어?

Answer 1

binary search tree은 노드의 왼쪽 하위 트리의 모든 항목이 노드보다 작고 오른쪽 하위 트리의 모든 노드가 노드보다 커지도록 구성됩니다.

완전한 (또는 거의 완전한) 2 진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워지고 하단 레벨이 왼쪽으로 채워지는 트리입니다.

따라서, 예를 들어,이 거의 완성 이진 검색 트리입니다 :

 4 
/ \ 
    2  5 
/\ 
1 3 

이되지 않습니다 :

 3 
/ \ 
    2  4 
/  \ 
1   5 

트리의 하단 수준이 왼쪽에서 작성되지하기 때문에 .

항목 수가 2의 거듭 제곱 (즉, 3, 7, 15 등)보다 작은 경우 트리 만들기가 쉽습니다. 목록을 정렬하여 시작하십시오. 그런 다음 중간 요소를 루트로 가져옵니다. 따라서 [1,2,3,4,5,6,7]이 있고 루트 노드가 4 인 경우

배열의 오른쪽과 왼쪽 절반에 대해 동일한 작업을 반복적으로 수행합니다.

항목 수가 2의 거듭 제곱보다 작지 않으면 하단 행이 왼쪽으로 채워지도록 시작점 (루트 노드)을 조정해야합니다. 하위 트리 길이가 2의 제곱보다 작지 않을 때마다 재귀 적으로 조정을 적용해야 할 수도 있습니다.

숙제 임으로 숙제 할 수 있도록 남겨 두겠습니다.