algorithm - 递归调用对完美二叉树建模的含义是什么？

Question

我正在学习数据结构和算法。我引用的书(Sedgwick)使用“寻找最大元素”来说明分而治之的策略。该算法将一个数组中途分成两部分，(递归)找出两部分中的最大元素，返回两者中较大的作为整个数组的最大元素。

下面是一道练习题

Modify the divide-and-conquer program for finding the maximum element in an array (Program 5.6) to divide an array of size N into one part of size k = 2^(lg N – 1) and another of size, N – k (so that the size of at least one of the parts is a power of 2).

Draw the tree corresponding to the recursive calls that your program makes when the array size is 11, similar to the one shown for Program 5.6.

我看到这样一棵二叉树的左子树是一棵完美二叉树，因为第一个子集的大小是2的幂。作者希望我从中得到什么启示？

Answer 1

我想这个练习的一个要点在于 k。它指出，如果您在二元递归中将此公式用于 k，那么您的基础树是“漂亮的”，因为每个节点(不仅仅是根节点)的左子树是完美的二叉树。

当然，当 N 是 2 的幂时，它在“理想”情况下也表现良好； k 就是 N/2，每个子树(不仅是左边的子树)都是一棵完美的二叉树。