2017-12-12 2 views
1

파이썬에서 구현 된 아이디어에 대한 답변을 보았습니다 (파이썬에 익숙하지 않은 경우) - 좀 더 일반적인 알고리즘을 찾고있었습니다.키 목록이 주어지면 그 목록의 거의 완전한 이진 검색 트리를 어떻게 찾을 수 있습니까?

EDIT : 설명을 위해

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

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

+0

당신이 무엇을 요구하고 있는지 불분명합니다. 질문을 수정하고 세부 정보를 추가하십시오. 우리에게 모범을 보일 수 있습니다. –

+0

@JimMischel 질문을 편집했습니다. 희망이 지금은 분명. –

답변

0

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의 제곱보다 작지 않을 때마다 재귀 적으로 조정을 적용해야 할 수도 있습니다.

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

+0

사실, 결승전을 위해 공부하고 있습니다 ... 불행히도 본문에서 설명하지 않았습니다. 하지만 대답 해줘서 고마워. 설명해. –

관련 문제