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

Question

4

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

以下是一个练习问题：

修改用于查找数组中最大元素的分治程序（程序5.6），将大小为N的数组分成大小为k = 2 ^（lg N-1）和大小为N-k的另一部分（因此至少有一个部分的大小是2的幂次方）。

绘制相应的递归调用树形图，当数组大小为11时，类似于程序5.6所示的那个。

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

- Abhijith Madhav

1

我不会试图在这里找到任何“深层”的含义。作者可能只是想通过让你追踪“不寻常”的递归模式的执行来增强你对递归的理解。 - abeln

@abeln，我一开始并没有觉得完美的二叉树会很“罕见”。但是我现在开始意识到，递归模式建模出完美的二叉树是“罕见/不常见”的。 - Abhijith Madhav

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mitchus · Accepted Answer

我认为这个练习的一个要点在于k。它指出，如果您在二进制递归中使用此公式来计算k，那么您的底层树是“漂亮的”，因为每个节点（而不仅仅是根节点）的左子树都是完美的二叉树。

当然，在“理想”情况下，即N是2的幂时，它也表现良好；此时k简单地等于N/2，并且每个子树（不仅仅是左子树）都是完美的二叉树。