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

Question

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

下面是一个练习题

修改用于查找数组中最大元素的分治程序（程序 5.6），将大小为 N 的数组分成大小为 k = 2^(lg N – 1) 的部分和大小为 N – k 的另一部分（使得至少一个部分的大小是 2 的幂）。

绘制与您的程序在数组大小为 11 时进行的递归调用相对应的树，类似于程序 5.6 中所示的树。

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

Answer 1

我想这个练习的一个重点在于k。这表明，如果您在二叉递归中对k使用此公式，那么您的底层树是“漂亮的”，因为每个节点（不仅仅是根）的左子树都是完美的二叉树。

当然，在N是 2 的幂的“理想”情况下，它也表现良好；然后k只是N/2，并且每个子树（不仅是左侧）都是完美的二叉树。