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

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

Ниже приведен вопрос упражнения, заданный

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

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

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


recursion algorithm data-structures binary-tree divide-and-conquer
person Abhijith Madhav    schedule 23.04.2011    source источник
comment
Я бы не стал искать в этом какой-то глубокий смысл. Вероятно, автор просто хочет улучшить ваше понимание рекурсии, заставив вас проследить выполнение необычного шаблона рекурсии.   -  person abeln    schedule 23.04.2011
comment
@abeln, мне не казалось, что идеальное бинарное дерево будет редкостью. Но я склоняюсь к тому, что шаблон рекурсии, моделирующий идеальное бинарное дерево, является необычным/необычным.   -  person Abhijith Madhav    schedule 25.04.2011

Ответы (1)


arrow_upward
1
arrow_downward

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

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

person mitchus    schedule 05.05.2011
comment
Спасибо за указание на поведение общего случая любой бинарной рекурсии для такого типа k. Я пропустил это, хотя это очень очевидно. Также мое первоначальное ожидание, когда я задавал вопрос, заключалось в том, что алгоритм каким-то образом улучшается за счет такого разделения подмножеств. Из ваших замечаний и замечаний Абленса выше я думаю, что рассматривал проблему упражнений с неправильным объективом. - person Abhijith Madhav; 06.05.2011