在二叉树中查找"局部最小值"

Question

你们可以帮我解决一些我被困住的功课问题吗？

完整二叉树中的局部最小值被定义为小于其所有邻居(邻居=父,左子,右子)的节点.我需要在给定的完整二叉树中找到局部最小值,其中每个节点具有不同的数字,在O(logn)complixity时间内.

好吧,既然要求是O(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",但是我们错过了它,因为在开始时我们决定搜索根的右子树.

Answer 1

根据定义,本地min是一个节点,其值小于连接到它的任何其他节点的值.因此,在您的示例中,"1","5","6","2","7","13"都是局部最小值.

一旦清楚,问题很简单.

首先,我们检查根,看它是否比两个孩子都小.如果是,那么我们就完成了.如果没有,那么我们拿起它的小孩并递归地应用支票.

我们终止1)我们发现一个小于其子节点的节点,或者2)我们到达底层(即叶子).

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

在情况2)中,我们留下两个叶子(即兄弟姐妹),并且它们中的至少一个小于父亲(否则将返回父亲).然后,它们中的任何一个(或两个)都是局部最小值,只要它小于它的父级.

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

希望这有用而且足够清楚.

Answer 2

如果“2”没有子级，并且您想在 O(logn) 内找到一个子级，则将其视为局部最小值。不可能在 O(logn) 内找到“1”