Анализ несвязанных объединений

Question

В непересекающемся объединении предположим, что мы должны объединить два дерева, высота которых равна соответственно h1 и h2. Используя эту технику, высота полученного объединенного дерева будет max (h1, h2), если h1 не равен h2, или h1 + 1, если h1 == h2. Используя эту технику после произвольной последовательности операций слияния, начиная с начальной ситуации, дерево, содержащее узлы 'k', имеет высоту максимум (этаж логка). Это доказывается по индукции следующим образом.

База: когда k = 1, высота равна 0. 0 <= (этаж (журнал 1)) </p>

Шаг индукции: рассмотрим k >1, и по гипотезе теорема верна для всех m, таких что 1<=m<k. Дерево, содержащее k узлов, может быть получено путем объединения двух меньших поддеревьев. Предположим, что эти два меньших дерева содержат соответственно узлы 'a' и 'b', где мы можем предположить без потери общности a<=b. Теперь a>=1, поэтому нет способа получить дерево с ноль узлов, начиная с исходной ситуации, и k = a + b. Отсюда следует, что a<=k/2 и b<=k+1, , начиная с k>1, и k/2 < k, и (k-1) < k и, следовательно, a<k и b<k.

Мой вопрос выше

1. Как мы получили «Отсюда вышеприведенное утверждение a <= k / 2 и b <= k + 1». </li>

Спасибо!

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.

На английском: если мы разделим k на две части a и b, где b больше половины, чем a должно быть меньше половины k.