5

你们能帮我解决一些我遇到的家庭作业问题吗？

完整二叉树中的局部最小值定义为小于其所有邻居（邻居=父，左孩子，右孩子）的节点。我需要在给定的完整二叉树中找到一个局部最小值，它的每个节点都有不同的数字，在 O(logn) 复杂度时间内。

好吧，因为要求是 O(logn)，所以我试图想出一种方法，只通过 1 条路径穿过树到达叶子。或者，也许我每次只能在递归中查看树的一半，这样它就会执行 logn。

所以说我在树上有这个：

    70
   /  \
 77    60

有3种情况：

1）根比左右孩子都小 //然后我就完成了

2）根只比左边小

3) 根只比右边小

上面的树是案例 2。所以让我们“扔掉”左子树，因为 77 不可能是“局部最小值”，因为它大于其父级。所以我们留下了右子树。以此类推，直到我们找到局部最小值。

这里的问题是，当我们抛出左子树时，我们可能会错过下面的另一个局部最小值。这是一个例子：

                70
              /    \
            77      60
          /   \    /   \
         1    8    9    14
        / \  / \  / \   / \
       3   4 5 6  2 7  15 13

所以在这种情况下，唯一的局部最小值是“1”，但我们错过了它，因为一开始我们决定搜索根的右子树。

4

3 回答 3

7

根据定义，局部最小值是一个节点，其值小于与其连接的任何其他节点的值。因此，在您的示例中，“1”、“5”、“6”、“2”、“7”、“13”都是局部最小值。

一旦清楚了，问题就很简单了。

首先我们检查根，看看它是否比两个孩子都小。如果是，那么我们就完成了。如果不是，那么我们拿起它的较小的孩子并递归地应用检查。

我们终止要么 1) 我们找到一个小于其两个子节点的节点，要么 2) 我们到达底层（即叶子）。

在案例 1) 中，我们停止的节点是本地 min，因为 i) 它比它的两个子节点都小，并且 ii) 它比它的父节点小，这是我们决定检查这个节点的前提条件。

在情况 2) 中，我们剩下两个叶子（即兄弟节点），其中至少有一个小于父节点（否则将返回父节点）。然后，它们中的任何一个（或两个）都是本地最小值，只要它小于其父级。

按照这种方法，每个级别最多查看 2 个节点，因此只需要 O(log n) 检查。

希望这是有帮助和足够清晰的。

于 2014-10-05T17:06:15.397 回答
0

如果您想在 O(logn) 内找到一个，则“2”如果没有孩子，则被视为局部最小值。在 O(logn) 中找不到“1”

于 2013-03-27T11:36:30.950 回答
0

我相信这可以在 O(N) 中完成。

从根开始。检查它是否有一个比它小的孩子。如果有，就去找那个孩子。如果它没有，我们就完成了。

然后，通过不断选择小于当前节点的子节点来重复此过程。检查它是否是本地最小值。如果没有，请重复。

通过这样做，我们保证当前节点的父节点总是大于自身。如果算法停止，可能只有两种情况：

  1. 当前节点是叶子。
  2. 当前节点的两个子节点都比它大。

在任何一种情况下，当前节点都是本地最小值。

编辑：

错过“完整”二叉树。应该是 log(n)。

于 2019-01-11T21:25:27.643 回答