최근 CLRS에서 모든 연습 문제를 해결하려고합니다. 하지만 내가 알아낼 수없는 몇 가지가 있습니다. 여기에 CLRS 운동 12.4-2의 그 중 하나가 있습니다 :노드의 평균 깊이가 Θ (lg n) 인 n- 노드 이진 탐색 트리의 높이에 점근선 상한값을 부여하십시오.
트리에있는 노드의 평균 깊이가 Θ (lg n)이지만 트리의 높이가되도록 n 노드에 이진 검색 트리를 기술하십시오 ω (lg n)이다. 노드의 평균 깊이가 Θ (lg n) 인 n- 노드 이진 탐색 트리의 높이에 점근선 상한을 준다.
누구든지이 문제를 해결하기 위해 아이디어 나 참고 자료를 공유 할 수 있습니까? 감사.
그래서 우리는 주어진 n 개의 노드, f (n) 개의 노드를 가져 와서 따로 설정한다고 가정합시다. 그런 다음 루트가 왼쪽 하위 트리가 n-f (n) - 1 노드의 완벽한 이진 트리이고 길이가 f (n) 인 체인 인 오른쪽 하위 트리가있는 완벽한 이진 트리를 작성하여 트리를 만듭니다. 나중에 f (n)을 선택합니다.
트리의 평균 깊이는 얼마입니까? 점근선이 필요하기 때문에, n - f (n) - 1이 2의 완전한 거듭 제곱보다 작은 것, 예를 들어 2^k - 1이되도록 n을 선택합시다.이 경우 높이의 합 트리의 일부는 1 2 + 2 * 3 + 4 * 4 + 8 * 5 + ... + 2^(k-1) * k이며, 약 (2^k) (n - f (n)) log (n - f (n))을 선택한다. 나무의 다른 부분에서 총 깊이는 약 f (n)^2입니다. 이는 평균 경로 길이가 대략 (n - f (n)) log (n - f (n)) + f (n)^2)/n임을 의미합니다. 또한 트리의 높이는 f (n)입니다. 따라서 평균 깊이 O (log n)를 유지하면서 f (n)을 최대화하려고합니다.
이 작업을 수행하려면, 우리는 그
f (n) = Θ (sqrt (n log n))을 선택하면 1과 2가 최대로 만족된다고 생각합니다. 그래서 나는 이것이 당신이 얻을 수있는만큼 좋은 것이라고 내기를했습니다. 평균 깊이가 Θ (Log n) 인 높이가 Θ (sqrt (n log n)) 인 트리가 있습니다.
희망이 도움이됩니다. 수학 문제가 해결되지 않으면 알려주세요. 지금 늦었고 평소에 이중 검사를하지 않았습니다. :-)
이것은 거의 끝나지 만 전체 오른쪽 트리가 체인 인 완전한 왼쪽 하위 트리가 아닌 리프 노드 중 하나에서 벗어난 꼬리가있는 완벽한 트리를 원한다고 생각합니다. 기본적으로 가능한 한 트리 위쪽에 많은 노드를 패킹 한 다음 하나의 긴 체인을 트리 밖으로 가져 오려고합니다. –
@ robertking- 음, 그게 좋은 지적이야. 수학을 다시 작성해도 체인에서 노드의 O (log n) 만 할인되므로이 점이 많이 점근 적으로 나타나는 것은 아닙니다. 하지만 네가 옳다고 생각해. – templatetypedef
@ robertking의 요점과는 달리, 이것이 답이되어야한다고 생각합니다. – meteorgan
처음으로 나무의 높이를 최대화하십시오. (각 노드에는 하나의 하위 노드 만있는 트리가 있으므로 긴 체인이 아래쪽으로 이동합니다).
평균 깊이를 확인하십시오. (분명히 평균 깊이가 너무 높을 것입니다).
평균 깊이가 너무 높지만 트리의 높이를 1 줄여야합니다. 나무의 높이를 하나씩 줄이는 데는 여러 가지 방법이 있습니다. 평균 높이를 최소화하는 방법을 선택하십시오. (유도로 평균 높이를 최소화 할 때마다 선택해야 함을 증명하십시오). 평균 높이 요구 사항에 부합 할 때까지 계속하십시오. (예 : 높이 및 평균 깊이에 대한 공식을 유도를 사용하여 계산).
구체적인 대답이 있습니까? 나는 당신의 추론을 아주 좋아하며, 당신이 무엇에 도착했는지 궁금합니다. – templatetypedef
전혀 대답이 없습니다. 솔직히 말해서 만약 내가 그것을 시험해보기 만했다면 당신의 테크닉을 사용할 것입니다. –
평균 트리의 모든 노드의 깊이를 최소화하면서 트리의 높이를 최대화하려는 경우 모호하지 않은 최상의 모양은 "우산"모양입니다. k 노드와 높이가 1g k 인 완전한 이진 트리. 여기서는 전체 경로의 잎 중 하나에서 나오는 n-k 노드의 단일 경로 또는 "꼬리"와 함께 0 < k < n이 사용됩니다. 이 나무의 높이는 대략 lg k + n - k입니다.
이제 모든 노드의 전체 깊이를 계산해 봅시다. 전체 파트의 노드 깊이의 합은 sum [j * 2^j]입니다. 여기서 합계는 j = 0에서 j = lg k까지입니다. 일부 대수학의 경우 결과의 지배적 인 용어는 2k lg k입니다.
다음으로, 꼬리 부분의 깊이의 합은 sum [i + lg k]에 의해 주어지며, 여기서 합은 i = 0에서 i = n-k로 취해진 다. 일부 대수학의 결과는 대략 (n-k) lg k + (1/2) (n-k)^2입니다.
위의 두 부분을 합친 다음 n으로 나누면 모든 노드의 평균 깊이는 (1 + k/n) lg k + (n-k)^2/(2n)이됩니다. 0 < k < n이기 때문에 첫 번째 항목은 어떤 k를 선택하든 O (lg n)입니다. 따라서 두 번째 항이 O (lg n)인지 확인하면됩니다. 그렇게하기 위해서는 (n-k)^2 = O (ng n) 또는 k = n-O (sqrt (ng n))이 필요하다. 이로서, 트리의 높이이다
엑스 K + N - = O (SQRT (N 엑스 N))
이 통상 O (엑스 N)보다 점근 크고, 점근 적이다 K 가장 큰 것은 평균 깊이를 유지하면서 나무를 만들 수 있습니다. (lg n)
'w'는'ω' (소문자 오메가)를 뜻합니다, 맞습니까? – Gumbo
@ 검보 그래, 고마워. – meteorgan