Каково значение рекурсивных вызовов, моделирующих идеальное двоичное дерево?

Question

Я изучаю структуры данных и алгоритмы. Книга, на которую я ссылаюсь (Седжвик), использует «поиск максимального элемента», чтобы проиллюстрировать стратегию «разделяй и властвуй». Этот алгоритм делит массив посередине на две части, находит максимальные элементы в двух частях (рекурсивно) и возвращает большее из двух в качестве максимального элемента всего массива.

Ниже задается вопрос для упражнения

Изменить программу «разделяй и властвуй» для поиска максимального элемента в массиве (Программа 5.6), чтобы разделить массив размера N на одну часть размера k = 2 ^ (lg N - 1) и другую часть размера N - k (так, чтобы размер хотя бы одной из частей был степенью 2).

Нарисуйте дерево, соответствующее рекурсивным вызовам, которые ваша программа выполняет, когда размер массива равен 11, аналогично показанному для Программы 5.6.

Я вижу, что левое поддерево такого двоичного дерева является идеальным двоичным деревом, потому что размер первого подмножества является степенью двойки. Какой смысл автор надеется получить от этого?

Answer 1

Полагаю, что один слепок этого упражнения лежит в k . Это говорит о том, что если вы используете эту формулу для k в бинарной рекурсии, то ваше базовое дерево будет «симпатичным», в том смысле, что левое поддерево каждого узла (не только корня) является совершенное двоичное дерево.

Конечно, это также хорошо ведет себя в «идеальном» случае, когда N является степенью 2; k - это просто N / 2 , и каждое поддерево (не только левое) является идеальным двоичным деревом.