고유 한 형태의 허프만 인코딩을 수행하고 있으며 전체 (모든 노드는 0 또는 k 개의 자식을 가짐)의 k-ary (이 특별한 경우, 3-ary) 트리를 구성하고 있으며, 얼마나 많은 잎이 있는지 알고 있습니다. 내가 그것을 만들기 전에 그것이있을 것이다. 트리의 총 노드 수를 리프 수의 관점에서 어떻게 계산합니까?전체 k 트리 트리의 리프 노드 개수는 얼마입니까?
전체 이진 트리 (2-ary)의 경우이 수식은 2L - 1이며, 여기서 L은 잎의 수임을 압니다. 이 원리를 k-ary tree의 경우까지 확장하고 싶습니다.
을하는 데 도움이
희망. 전체 이진 트리를 들어, 노드 N의 수는
N = 2^{h+1} - 1
왜 높이 h의 말을? 첫 번째 수준에는 2^0 개의 노드가 있으므로 두 번째 수준에는 2^1 개의 노드가 있고 일반적으로 k 수준의 노드는 2^{k-1}입니다. h+1 수준 (너무 높이 h)의 총이를 추가하면
N = 1 + 2 + 2^2 + 2^3 + ... + 2^h = (2^{h+1} - 1)/(2 - 1) = 2^{h+1} - 1
잎 L의 총 수는 지난 수준에서 노드의 단지 수 있으므로 L = 2^h입니다 제공합니다. 따라서, 치환, 우리는 k -ary 나무, 아무것도 변화하지만 2를 들어
N = 2*L - 1
얻을. 그래서
N = 1 + k + k^2 + k^3 + ... + k^h = (k^{h+1} - 1)/(k - 1)
L = k^h
및
그래서 당신이 마지막 단계를 취할 수 대수의 비트가있는 K 진 트리를 들어N = (k*L - 1)/(k-1)
큰 답, 감사합니다! – Andrew
언급 한 2L-1의 수식은 완전하고 완벽하며 균형 잡힌 이진 트리를 살펴 보는 것부터 시작됩니다. 마지막 레벨에서는 2^h 리프가 있고 다른 레벨은 1 + 2 + 4 +입니다. ... + 2^(h-1) = 2^h -1이된다. 트리에서 "레벨을"엉망으로 만들고 불균형 한 레벨을 만들면, 가지고있는 내부 노드의 수가 바뀌지 않습니다.
3-ary 트리에서 동일한 논리가 있습니다. 마지막 레벨에서는 3^h 리프가 있고 다른 레벨에서는 1 + 3 + 9 + ... + 3^(h-1) = (3^h -1)/2는 3-ary 트리에서 1.5 * L - 0.5 leafs를 갖는다는 것을 의미합니다 (그리고 그 정도는 더 크기 때문에 내부 노드가 덜 필요합니다). 나는 또한 여기에있는 트리의 레벨을 엉망으로 할 때 같은 수의 내부 노드가 필요합니다. 그것은 전체 이진 트리에 대한 결과를 증명하기 위해, 당신은 일반적으로 그것을 어떻게 볼 방법에 대해 생각하면
에게 노드의 총 수를 얻을 수있는 N = [(K^(H + 1)) - 1]/(h-1) 여기서 h는 k-ary 트리의 높이입니다.
예 : - 전체 이진 트리 (k = 2)의 경우 전체 수. 노드 = [(2^(h + 1)) - 1]/(h-1)이다.
그래서 높이 3에 대한 전체 번호. 노드의 수는 15가됩니다.
전체 3 진 트리 (k = 3) node = [(3^(h + 1)) - 1]/(h-1)이다.
그래서 높이 3에 대한 전체 번호. 노드 수는 40입니다.
[(k^(h + 1)) - 1]/(h-1)이 틀립니다. 그것은 [(k^(h + 1)) - 1]/(** k ** - 1)입니다. 게시하기 전에 답변을 확인하십시오. – BlackSwan
이 숙제가 있습니까? 그렇다면 그에 따라 태그하십시오. – PengOne
아니, 숙제가 아니야. -2 표를 가져 주셔서 감사합니다. – Andrew
비록 투표 한 사람들도 확실하게 알 수는 없지만, 아래 표는 당신이이 문제에 대한 연구 노력을하지 않았거나 코딩과 직접 관련이 없기 때문일 가능성이 큽니다. – PengOne