Хобрук: Ваш путь к мастерству в программировании

k-арные деревья индукционное доказательство

Я озадачен этой проблемой:

У вас есть дерево, в котором каждый внутренний узел имеет k потомков, причем k >= 2. Каково максимальное количество узлов, которое может иметь такое дерево, если его глубина равна d? Докажите свой ответ индукцией по d.

Итак, я понимаю, что если бы k было равно 2, геометрический ряд был бы равен 1 + 2 + 4 + 8...+2^n, но я не могу понять, как включить глубину и как доказать это индуктивно.

algorithm tree binary-tree
26.03.2014

  • Попробуйте записать ряд как 1 + 2 + 4 + ... + 2 ^ d. 26.03.2014

Ответы:


1

Количество элементов в полном k-арном дереве из n уровней равно (k^n - 1)/(k - 1).

Бинарное дерево из 5 уровней, например, имеет 31 узел (1 + 2 + 4 + 8 + 16). Или:

(2^5 - 1)/(2 - 1) = 31/1 = 31

4-арное дерево из 4 уровней имеет 85 узлов (1 + 4 + 16 + 64).

(4^4 - 1)/(4 - 1) = 256/3 = 85

Если вы выпишете несколько из них для разных значений k, вы сможете получить индуктивное доказательство.

26.03.2014
Новые материалы
Создание кнопочного меню с использованием HTML, CSS и JavaScript
Вы будете создавать кнопочное меню, которое имеет состояние наведения, а также позволяет вам выбирать кнопку при нажатии на нее. Финальный проект можно увидеть в этом Codepen . Шаг 1..
Внедрите OAuth в свои веб-приложения для повышения безопасности
OAuth — это широко распространенный стандарт авторизации, который позволяет приложениям получать доступ к ресурсам от имени пользователя, не раскрывая его пароль. Это позволяет пользователям..
Классы в JavaScript
class является образцом java Script Object. Конструкция «class» позволяет определять классы на основе прототипов с чистым, красивым синтаксисом. // define class Human class Human {..
Как свинг-трейдеры могут использовать ИИ для больших выигрышей
По мере того как все больше и больше профессиональных трейдеров и активных розничных трейдеров узнают о возможностях, которые предоставляет искусственный интеллект и машинное обучение для улучшения..
Как построить любой стол
Я разработчик программного обеспечения. Я люблю делать вещи и всегда любил. Для меня программирование всегда было способом создавать вещи, используя только компьютер и мое воображение...
Обзор: Машинное обучение: классификация
Только что закончил третий курс курса 4 часть специализации по машинному обучению . Как и второй курс, он был посвящен низкоуровневой работе алгоритмов машинного обучения. Что касается..
Разработка расширений Qlik Sense с qExt
Использование современных инструментов веб-разработки для разработки крутых расширений Вы когда-нибудь хотели кнопку для установки переменной в приложении Qlik Sense? Когда-нибудь просили..