노드가 'N'인 경우 가능한 이진 및 이진 검색 트리는 몇 개입니까?

노드가 'N'인 경우 가능한 이진 및 이진 검색 트리는 몇 개입니까?

---

바이너리 트리의 경우 : 트리 노드 값을 고려할 필요가 없습니다. 저는 'N'노드가있는 다른 트리 토폴로지에만 관심이 있습니다.

이진 검색 트리의 경우 : 트리 노드 값을 고려해야합니다.

---

저는 제 동료 Nick Parlante 가이 기사 를 추천 합니다 (그가 아직 스탠포드에있을 때부터). 구조적으로 다른 이진 트리의 개수 (문제 12)에는 간단한 재귀 솔루션이 있습니다 (닫힌 형식에서는 @codeka의 답변이 이미 언급 한 카탈루냐 공식이됩니다).

구조적으로 다른 이진 검색 트리 (줄여서 BST)의 수가 "일반"이진 트리 의 수와 어떻게 다른지 잘 모르겠습니다. 단, "트리 노드 값을 고려"하면 각 노드가 다음과 같을 수 있음을 의미합니다. BST 조건과 호환되는 임의의 숫자, 다른 BST의 수는 무한합니다 ( 구조적으로 모두 다르지는 않습니다 !-). 나는 당신이 의미하는 것이 의심 스럽기 때문에, 당신 이 의미하는 바를 예를 들어 설명하십시오!

---

1. 이진 트리의 총 개수는 =

2. i를 더하면 n 개의 노드가있는 이진 검색 트리의 총 수가 제공됩니다.

기본 케이스는 t (0) = 1 및 t (1) = 1입니다. 즉, 하나의 빈 BST가 있고 하나의 노드가있는 하나의 BST가 있습니다.

따라서 일반적으로 위의 공식을 사용하여 이진 검색 트리의 총 수를 계산할 수 있습니다. 이 공식과 관련된 Google 인터뷰 에서 질문을 받았습니다 . 질문은 6 개의 정점으로 가능한 이진 검색 트리의 총 개수입니다. 따라서 답은 t (6) = 132입니다.

당신에게 몇 가지 아이디어를 준 것 같아요 ...

---

이진 트리의 수는 카탈로니아 수를 사용하여 계산할 수 있습니다 .

이진 검색 트리의 수는 재귀 솔루션으로 볼 수 있습니다. ie, Number of binary search tree = (Number of Left binary search sub-trees) * (Number of right binary search sub-trees) * (Ways to choose the root)

BST에서는 요소 간의 상대적 순서 만 중요합니다. 따라서 일반성에 대한 손실없이 트리의 개별 요소가 1, 2, 3, 4, ...., n 이라고 가정 할 수 있습니다 . 또한, n 개의 요소에 대해 BST의 수를 f (n) 으로 표시 합니다 .

이제 우리는 루트를 선택하는 여러 사례가 있습니다.

1. 루트로 1을 선택 하면 왼쪽 하위 트리에 요소를 삽입 할 수 없습니다 . n-1 요소가 오른쪽 하위 트리에 삽입됩니다.
2. 루트로 2 개를 선택 하면 왼쪽 하위 트리에 1 개의 요소를 삽입 할 수 있습니다. n-2 개의 요소를 오른쪽 하위 트리에 삽입 할 수 있습니다.
3. 루트로 3 개를 선택 하면 왼쪽 하위 트리에 2 개의 요소를 삽입 할 수 있습니다. n-3 요소는 오른쪽 하위 트리에 삽입 할 수 있습니다.

...... 마찬가지로 i 번째 요소가 루트 인 경우 i-1 요소는 왼쪽에, ni 는 오른쪽에 있을 수 있습니다 .

이러한 하위 트리는 그 자체로 BST이므로 공식을 다음과 같이 요약 할 수 있습니다.

f (n) = f (0) f (n-1) + f (1) f (n-2) + .......... + f (n-1) f (0)

기본 경우 f (0) = 1입니다. 노드가 0 개인 BST를 만드는 방법은 정확히 1 개입니다. f (1) = 1, 노드 1 개로 BST를 만드는 방법은 정확히 1 가지입니다.

---

아니오가 주어지면. 노드의 수는 N입니다.

BST의 다른 수 = 카탈로니아 어 (N)
구조적으로 다른 이진 트리의 수는 = 카탈로니아 어 (N)

이진 트리의 다른 수는 = N! * 카탈로니아 어 (N)입니다.

---

Eric Lippert는 최근에 " 모든 이진 나무가 있습니다 "와 " 모든 나무가 있습니다 "(그 이후에 더 많은 것)에 대해 매우 심층적 인 블로그 게시물 을 작성했습니다.

구체적인 질문에 대한 대답으로 그는 다음과 같이 말합니다.

n 개의 노드가있는 이진 트리의 수 는 많은 흥미로운 속성을 가진 카탈로니아 숫자로 제공됩니다 . n 번째 카탈로니아 수는 공식 (2n)에 의해 결정됩니다! / (n + 1)! n !, 기하 급수적으로 증가합니다.

---

n 개의 노드가있는 다른 이진 트리 :

(1/(n+1))*(2nCn)

여기서 C = 조합 예.

n=6,
possible binary trees=(1/7)*(12C6)=132

---

(2n)!/n!*(n+1)!

---

The number of possible binary search tree with n nodes (elements,items) is

=(2n C n) / (n+1) = ( factorial (2n) / factorial (n) * factorial (2n - n) ) / ( n + 1 ) 

where 'n' is number of nodes  (elements,items ) 

Example :

for 
n=1 BST=1,
n=2 BST 2,
n=3 BST=5,
n=4 BST=14 etc

---

이진 트리 :

값을 고려할 필요가 없습니다. 구조를 살펴볼 필요가 있습니다.

(2 제곱 n)-n

예 : 3 개 노드의 경우 (2 승 3) -3 = 8-3 = 5 개의 다른 구조

이진 검색 트리 :

노드 값도 고려해야합니다. 우리는 그것을 카탈루냐 번호라고 부릅니다.

2n C n / n + 1로 주어짐

---

레이블이없는 노드 의 경우 정답은 2nCn / (n + 1) 이어야하며 노드에 레이블이 지정되면 (2nCn) * n! / (n + 1) .

참고 URL : https://stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib