Max-Heapify의 최악의 경우-어떻게 2n / 3을 얻습니까?

Max-Heapify의 최악의 경우-어떻게 2n / 3을 얻습니까?

---

CLRS, 제 3 판, 155 페이지에 MAX-HEAPIFY에서

자식의 하위 트리의 크기는 각각 최대 2n / 3입니다. 최악의 경우는 트리의 맨 아래 수준이 정확히 절반이 찼을 때 발생합니다.

나는 나무의 바닥이 정확히 절반이 찼을 때 그것이 왜 최악인지 이해합니다. 그리고이 질문 에서도 MAX-HEAPIFY의 최악의 경우에 대답됩니다 . "최악의 경우는 트리의 맨 아래 수준이 정확히 절반이 찼을 때 발생합니다."

내 질문은 2n / 3을 얻는 방법입니다.

하단 레벨이 반쯤 차면 자식 트리의 크기가 최대 2n / 3 인 이유는 무엇입니까?

그것을 계산하는 방법?

감사

---

각 노드에 정확히 0 개 또는 2 개의 자식이있는 트리에서 자식이 0 개인 노드의 수는 자식이 2 개인 노드의 수보다 하나 더 많습니다. {설명 : 높이 h에있는 노드의 수는 2 ^ h입니다. 기하학적 시리즈의 합산 공식은 (높이 0에서 h-1까지 노드의 합) + 1과 같습니다. 높이 0에서 h-1까지의 모든 노드는 정확히 2 개의 자식이있는 노드입니다.}

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

k를 R의 노드 수라고합니다. L의 노드 수는 k + (k + 1) = 2k + 1입니다. 총 노드 수는 n = 1 + (2k + 1) + k = 3k + 2입니다. (루트 + L + R). 비율은 (2k + 1) / (3k + 2)이며, 2/3 이상으로 제한됩니다. k가 무한대로가는 한계가 2/3이기 때문에 2/3보다 작은 상수는 작동하지 않습니다.

---

Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.

이것이 명확 해지면 2N / 3의 경계를 쉽게 얻을 수 있습니다.

트리의 총 노드 수가 N이라고 가정하겠습니다.

트리의 노드 수 = 1 + (왼쪽 하위 트리의 노드 수) + (오른쪽 하위 트리의 노드 수)

트리의 마지막 레벨이 절반으로 채워진 경우 iF는 오른쪽 하위 트리가 높이 h이고 왼쪽 하위 트리가 높이 (h + 1)이면 왼쪽 하위 트리라고 가정합니다.

왼쪽 하위 트리의 노드 수 = 1 + 2 + 4 + 8 .... 2 ^ (h + 1) = 2 ^ (h + 2) -1 ..... (i)

오른쪽 하위 트리의 노드 수 = 1 + 2 + 4 + 8 .... 2 ^ (h) = 2 ^ (h + 1) -1 ..... (ii)

따라서 다음을 연결합니다.

트리의 노드 수 = 1 + (왼쪽 하위 트리의 노드 수) + (오른쪽 하위 트리의 노드 수)

=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)

=> N = 1 + 3*(2^(h+1)) - 2

=> N = 3*(2^(h+1)) -1

=> 2^(h+1) = (N + 1)/3

이 값을 방정식 (i)에 대입하면 다음을 얻습니다.

Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)

따라서 N 노드가있는 트리에 대한 하위 트리의 최대 노드 수에 대한 상한은 2N / 3입니다.

---

높이의 완전한 이진 트리 h의 경우 노드 수는 f(h) = 2^h - 1입니다. 위의 경우 하반부가 가득 찬 거의 완전한 이진 트리가 있습니다. 우리는 이것을 root + left complete tree + right complete tree. 원래 나무의 높이가 h이면 왼쪽은 h - 1이고 오른쪽은 h - 2. 그래서 방정식은

n = 1 + f(h-1) + f(h-2) (1)

우리는 f(h-1)다음과 같이 표현 하기 위해 위에서 해결하고 싶습니다.n

f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2 (2)

위의 (1)을 사용하여

n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2

=> f(h-1) = 2*(n-1/2)/3

따라서 O (2n / 3)

---

-노드 수

• 레벨 0 즉 루트는 2 ^ 0입니다.
• 레벨 1은 2 ^ 1입니다.
• 레벨 2는 2 ^ 2입니다.
• ...
• 수준 n은 2 ^ n입니다.

레벨 0에서 레벨 n까지의 모든 노드의 합계,

• S = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ n

기하학적 시리즈 합산 규칙에서 우리는

• x ^ 0 + x ^ 1 + x ^ 2 + ... + x ^ (n) = (x ^ (n + 1)-1) / (x-1)

x = 2를 대체하면

• S = 2 ^ (n + 1)-1. 즉 2 ^ (n + 1) = S + 1

As 2^(n+1) is the total nodes at level n+1, we can say that the number of nodes with 0 children is one more than the number of nodes with 2 children.

Now lets calculate number of nodes in left subtree, right tree and total ..

• Assume that number of non-leaf nodes in the left subtree of root = k.

• By the above reasoning, number of leaf nodes in the left subtree or root = k + 1. Number of non-leaf nodes in the right subtree of root = k as the tree is said to be exactly half full.

• Total number of nodes in the left subtree of root = k + k + 1 = 2k +

• Total number of nodes in the tree, n = (2k + 1) + k + 1 = 3k + 2.
• Ratio of nodes in the left subtree and total nodes = (2k + 1) / (3k + 2) which is bounded above by 2/3.

That's the reason of saying that the children’s subtrees each have size at most 2n/3.

---

To add to swen's answer. How (2k + 1) / (3k + 2) tends to 2 / 3, when k tends to infinity,

Lim_(k -> inf) (2k + 1) / (3k + 2) = Lim_(k -> inf) k(2 + 1 / k) / k(3 + 2 / k) = Lim_(k -> inf) (2 + 1 / k) / (3 + 2 / k)

apply the limit, and you get 2/3

참고URL : https://stackoverflow.com/questions/9099110/worst-case-in-max-heapify-how-do-you-get-2n-3