분리 노조 찾기 분석

Question

분리 노조에서는 높이가 각각 h1과 h2 인 두 개의 트리를 병합해야한다고 가정합니다. 이 기법을 사용하면 h1이 h2와 같지 않으면 max (h1, h2), h1 == h2이면 h1 + 1이 합병 된 트리의 높이가됩니다. 초기 상황에서 시작하는 병합 작업의 임의의 순서 후에이 기술을 사용하면 'k'노드를 포함하는 트리의 높이는 최대로 (logk의 바닥) 입니다. 이것은 유도에 의해 다음과 같이 입증됩니다.

자료 : K = 1 개 높이 0.0 < = 때

유도 단계 (층 (1)을 기록) k >1을 고려 가설 therorm 모든 m되도록 1<=m<k 마찬가지이다. 두 개의 작은 하위 트리를 병합하여 k 노드를 포함하는 트리를 얻을 수 있습니다. 이 두 개의 더 작은 나무가 각각 'a'와 'b'노드를 포함한다고 가정하면 일반성을 잃지 않고 가정합니다. a<=b. 이제 a>=1이므로 초기 상태에서 시작하여 제로 노드 인 트리를 얻는 방법이없고 k = a + b입니다. 그것은 그와 a<=k/2b<=k+1, k>1 보낸 두 k/2 < k 및 (k-1) < k 따라서 a<k 및 b<k 따른다. 위의

내 질문은 우리가 가진 문 위의 "그것은하는 < = K/2와 b < = K + 1 다음"어떻게

1. 입니다.

고마워요!

Answer 1

a > k/2 다음에 b > k/2이라고 가정 해보십시오. 왜냐하면 b>=a입니다. 그 다음 a + b > k/2 + k/2. 따라서, a + b > k. 하지만 우리는 k = a + b! 따라서 a > k/2이라는 가정은 모순으로 이어지고 따라서 거짓입니다. 이것은 a <= k/2이라는 '증명'입니다.

영어

: 우리는 b가 a보다 더 큰 절반 두 부분 a 및 b에 k을 분할하는 경우 k의 절반보다 작아야합니다.