정렬 된 정수 배열이 주어지면 이진 검색 트리를 어떻게 구성 할 수 있습니까?

Question

내가 배열 [3,18,15,25,26]을 가지고 있다고 가정하면 얼마나 많은 가능한 이진 검색 트리가 형성 될 수 있습니까?

Answer 1

MicSim이 링크 한 질문을 본 후에도 여전히 만족스럽지 않으므로 직접 살펴 보았습니다. 다음은 내가 생각해 낸 것입니다 ...

각 트리는 부모 루트 노드가있는 두 개의 트리로 생각할 수 있습니다. 두 개의 하위 분기가 가능한 조합의 수를 별도로 알고있는 경우 해당 루트 노드가있는 총 조합은 하위 조합의 결과입니다.

더 낮은 계산 인스턴스를 먼저 풀면 더 많은 계산 솔루션을 빌드 할 수 있습니다.

나는 가능한 모든 n 노드의 조합 인 카탈로니아 수를 나타 내기 위해 C(n)을 사용할 것입니다.

C(0) = 1 
C(1) = 1 

C (2) 또한 매우 분명 있지만 구축 할 수 있습니다, 그래서 그렇게하자

는 희망이 두 명백하다. 루트 노드를 선택하는 두 가지 방법이 있습니다. 하나는 자식 수 (왼쪽 : 오른쪽)는 1:0이고 다른 하나는 0:1입니다. 따라서 첫 번째 가능성은 C(1)*C(0) = 1*1 = 1입니다. 두 번째는 C(0)*C(1) = 1*1 = 1입니다. 함께 요약하면

아직 재미가 없습니다. 이제 3 개의 노드를 살펴 봅시다. 루트 노드를 선택할 수있는 3 가지 방법, 따라서 3 개의 하위 그룹을 선택할 수 있습니다. 가능한 그룹은 2:0, 1:1 및 0:2입니다.

이전의 정의에 따르면 C(3)은 C(2)*C(0) + C(1)*C(1) + C(0)*C(2) = 2*1 + 1*1 + 1*2 = 2+1+2 = 5으로 기록 할 수 있습니다.

C(3) = 5 

4 노드 3:0, 2:1, 1:2 및 0:3의 하위 그룹을 가지고있다. 따라서 C(4)은 C(3)*C(0) + C(2)*C(1) + C(1)*C(2) + C(0)*C(3) = 5*1 + 2*1 + 1*2 + 1*5 = 5+2+2+5 = 14으로 기록 할 수 있습니다.

C(4) = 14 

바라기를 두 가지가 분명해지기를 바랍니다. 첫째로, 이것은 꽤 조만간 성가 시게 될 것입니다. 둘째로, 내가 꽤 오랜 바람에 묘사 한 것은 위키 페이지에서의 반복 관계 표현입니다.

이것이 도움이 될지 모르겠지만 운동을 진행하는 데 도움이되므로 공유 할 것이라고 생각했습니다. 시작했을 때 재발 관계를 다시 만들려고하지 않았기 때문에 결과가 기존 방법 중 하나와 일치하는 것이 좋았습니다.

Answer 2

N 키를 사용하여 생성 할 수있는 이진 탐색 트리의 수는 N 번째 catalan number에 의해 제공됩니다.

또한이 질문을 참조하십시오 The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?이

Answer 3

배열의 노드의 모든는 BST의 루트가 될 수를, 각 루트에 대해 별개의 검색 나무의 수는 왼쪽의 조합 (제품)이며, 오른쪽 부분 배열 그래서,

BSTCount(0) = 1 
BSTCount(n) = sum_{i = 1}^{n} BSTCount(i-1) * BSTCount(n-i) 

당신은 처음 몇 N이 기능을 평가할 수 후 폐쇄 양식을 찾기 위해 On-Line Encyclopedia of Integer Sequences™ (OEIS)의 순서를 찾아보십시오.