트리에서 값의 계산 확률

Question

이것은 내 대학의 데이터 구조 코스의 질문이었습니다. 나는 그 질문이 무엇을 의미하는지 이해하지 못한다. 아무도 나를 질문에 대해 정교하게 대답 할 수는 없습니까?

처음에는 빈 이진 검색 트리에 1에서 15 사이의 모든 숫자를 삽입한다고 가정합니다. 이러한 키의 모든 순열은 동일하게 삽입 순서 일 수 있습니다. 결과 트리의 루트가 10, 루트의 하위 인 및 루트의 오른쪽 자식으로 15를 갖는 결과 트리의 확률을 계산합니다. 일어나는 "10 as its root, 7 as the left child of the root and 15 as the right child of the root."에 대한 위해

Answer 1

트리의 삽입 순서는 다음 중 하나 여야합니다

• 10 첫째, 다음 7, 다음 15 후 어떤 순서로 다른 12 개 번호.
• 10 먼저 15 다음에 7을 입력 한 다음 다른 순서로 12 개의 숫자를 입력하십시오.

몇 가지 방법이있을 수 있습니까?

• 첫 번째로 10을 선택한 다음 7을 선택한 다음 15를 선택하십시오. 12! 나머지 선택 방법.
• 먼저 10을 선택한 다음 15를 선택한 다음 7을 선택하는 방법은 1입니다. 그리고 다시 12! 나머지 선택 방법.

이렇게 특정 배열로 끝나는 방법은 (12! * 2)입니다.

이제 모든 가능한 게재 신청서 세트는 15 수의 순열이다 15! (계승) 문제는 말한다 "all permutations of these keys are equally likely to be the insertion order"때문에이 구성 할 수있는 방법의 수와 관련 있다는

주 다른 삽입 주문이 동일한 트리를 작성하게 될 수 있기 때문에 차이가 있습니다 (예 : 위의 2 가지 경우를 제외하고 다른 12 개의 숫자가 다른 삽입 주문에도 불구하고 동일한 트리를 작성 함)

확률 : (질문에 의해 지정된 배열을 만드는 방법의 수)를 (th 나무를 만들 수있는 총 방법 수) :

그래서 (12! * 2)/(15!)은 원하는 확률입니다.

Answer 2

자체 균형 조정 트리를 만들지 않으면 얻을 수있는 트리가 요소 삽입 순서에 따라 다릅니다. 루트가 10 인 경우, 10이 삽입 된 첫 번째 숫자 여야합니다. 이것은 15 또는 1/15의 확률을 가짐 확률이 2/14 * 1/13 일 때 7과 15가 확률 2/14 * 1/13

총계 : 1/15 * 2/14 * 2/13