Задание: Требуется доказать, что для любого бинарного дерева с n вершинами и высотой h верно неравенство: $$\lfloor \log _{2} n\rfloor \leq h \leq n-1$$

Вопрос: Меня интересует, возможно ли доказать с помощью метода индукции?

задан 6 Май 18:00

10|600 символов нужно символов осталось
1

По индукции здесь делается всё -- в том числе даётся определение высоты дерева. Но основная суть должна быть ясна из картинки. Пусть высота задана, и мы хотим получить как можно больше вершин. Тогда мы делаем все возможные ветвления. Для h=0 получается одна вершина, для h=1 их 3. Доказываем, что в общем случае их не более 2^{h+1}-1. База индукции уже есть. Пусть для высот < h утверждение доказано. У корня дерева имеется ветвление на два направления, и при этом возникают два дерева высоты не более h-1. В каждом из них, по предположению, не больше 2^h-1 вершин. Тогда всего, с учётом корневой вершины, их не более 1+2(2^h-1)=2^{h+1}-1. Таким образом, n < 2^{h+1}, и h+1 > log_2(n). Следовательно, h >= [log_2(n)].

Теперь пусть для заданной высоты мы хотим получить как можно меньше вершин. Тогда на каждом уровне мы делаем только одно ветвление. Количество вершин увеличивается при этом на 2, откуда следует, что n>=2h+1. Это неравенство является усилением того, что требовалось получить.

ссылка

отвечен 6 Май 18:53

Сложно, буду разбираться:) Спасибо!

(6 Май 23:21) notanton25
1

@notanton25: это крайне просто, если всё представлять себе на уровне детских картинок. Уже от них надо идти к формальному изложению.

(6 Май 23:27) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×234
×133

задан
6 Май 18:00

показан
100 раз

обновлен
21 Май 12:09

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru