연결된 숫자 목록이 주어진 BST의 수

연결된 숫자가 양수이고, 생성 할 수있는 BST의 수는 이고 모든 노드는이어야 트리를 구성 할 수 있습니까?연결된 숫자 목록이 주어진 BST의 수

반대로 생성 된 BST의 수는 이며 연결된 목록 노드 중 임의의 수이이 트리에 존재할 수 있습니까?

보너스 : 몇 개의 밸런스드 BST를 형성 할 수 있습니까? 어떤 도움이나지도도 크게 감사드립니다.

2012-02-11 OckhamsRazor

괜찮습니까? 그렇다면 BST의 inorder 순회가 정렬 된 목록을 올바르게 안내합니까? 그래서 나는 qn을 "얼마나 많은 방법으로 링크 된 목록을 정렬 할 수 있는가"로 분해 할 수 있다고 생각했습니다. 그것은 nCn + nC (n-1) + ... + nC1이 될 것입니다. 이것은 두 번째 질문에 대한 답이 될 것입니다. 첫 번째 qn에 대한 답은 n이됩니다. 세 번째 qn, 완전히 확실하지 않습니다. – OckhamsRazor

가능한 [주어진 노드에서 가능한 트리 수를 결정] (http://stackoverflow.com/questions/9238440/determine-number-of-possible-tree-from-given-nodes) –

동적 프로그래밍을 사용하여 계산할 수 있습니다.

숫자가 무엇인지, 몇 개가되는지는 중요하지 않습니다. 즉, n 개의 고유 정수에 대해 동일한 양의 다른 BST가 있습니다. 이 번호를 f (n)라고 부르 자. 그런 다음

당신은, 당신은 F (N)를 얻을 수 있습니다 K < N에 대한 F (k)를 알고있는 경우 :

f(n) = Sum (f(i) + f(n-1-i), i = 0,1,2,...,n-1)

각 피가수 나무의 수에 대한 (1 + i)를 번째 작은 나타냅니다 번호는 루트에 있습니다 (따라서 왼쪽 하위 트리에서 i는 숫자이고 오른쪽 하위 트리에서는 n-1-i입니다). 그래서 DP가이를 해결합니다. 당신이 Binomial(n,k) 방법으로 그 중 K를 선택할 수 있으며, 다음 f(k)을 있다는 것을 알고 있기 때문에

Sum (Binomial(n,k) * f(k), k=1,2,3,...,n)

이것은 :

지금 (목록에서 모든 노드) BST를의 총 수는 합이다 그들을위한 BST.

출처

2012-02-12 08:27:00

연결된 숫자 목록이 주어진 BST의 수

답변

관련 문제