在AVL树中查找两个数字之间的最小差距

Question

我有一份数据结构的作业，除了常规的AVL树函数之外，我还需要添加一个函数来返回AVL树中任意两个数字之间的最小差值（实际上是AVL中的节点表示数字）。

假设我们在AVL树中有数字（作为节点）1 5 12 20 23 21，该函数应返回任意两个数字之间的最小差值。在这种情况下，它应该返回“1”，即|20-21|或|21-20|。

这应该在O(1)内完成。

我想了很多，知道其中有一个技巧，但就是找不到它，我已经花了几个小时在这上面。

还有另一个任务，即查找最大差值，这很容易，它是最小和最大数字之间的差异。

- TheNotMe

---

为什么最小间隔不是|21-20|=1？ - Simeon Visser

非常抱歉！应该是|21-20|或|20-21|=1，函数应该返回1！非常抱歉犯了错误！ - TheNotMe

当我用这些数字绘制平衡二叉树时，20是根节点，21是根节点右子树中最深且最左侧的叶节点。我有一种感觉，你必须计算根节点和一个非常深的叶节点之间的差异。我需要再次阅读AVL树的相关资料，看看是否可以“滥用”这些树的特性。 - Simeon Visser

我相当确定有这样的技巧。让我惊讶的是，我应该在O(1)内完成它 - 我想不出任何算法来做到这一点！此外，我应该提到，AVL树的所有基本函数，如Init、Search、Insert、Delete，仍应为O(log(n)) - 所以我确定我不应该向基本函数中添加任何内容！这个问题让我挠头数小时！ - TheNotMe

看看这个链接：https://dev59.com/t3M_5IYBdhLWcg3wMgAF 似乎真的存在那个算法，但需要O(n)的预处理。 - raven1981

O(n)对我来说不是一个选择。我-必须-在O(1)内完成它。 也许在AVL的插入函数中需要添加一些东西，这将对我有所帮助，但不会改变logn的插入复杂度。 - TheNotMe

Answer 1

你需要扩展数据结构，否则无法获得由树组成的数字之间最小间隙的O(1)搜索。

你还有额外的限制，即不增加插入/删除/搜索函数的时间复杂度，并且我假设您也不想增加空间复杂度。

考虑一个通用节点r，它具有左子树r.L和右子树r.R；我们将在节点r中扩展信息，添加一个称为r.x的附加数字，其定义为以下值之间的最小值：

- （仅当r.L不为空时）r值和r.L上最右侧叶子的值 - （仅当r.L深度大于1时）r.L根节点的x值 - （仅当r.R不为空时）r值和r.R上最左侧叶子的值 - （仅当r.R深度大于1时）r.R根节点的x值

（如果没有一种先前的条件有效，则为未定义，在叶节点的情况下）

此外，为了快速插入/删除，我们需要在每个内部节点中添加其左侧和右侧叶节点的引用。

您可以看到，通过这些添加：

- 空间复杂度仅增加一个常量因子 - 插入/删除函数需要更新每个更改的子树的根的x值和最左侧和最右侧的叶子，但可以轻松实现，不超过O(log(n)) - 树根的x值是函数需要返回的值，因此您可以以O(1)实现它

树中的最小间隙是根节点的x值，更具体地说，对于每个子树，仅在子树元素中考虑的最小间隙是子树根部的x值。

这个陈述的证明可以通过递归来进行： 考虑一个以节点r为根的树，其具有左子树r.L和右子树r.R。 归纳假设是r.L和r.R x值的根是子树中节点值之间最小间隙的值。显然，只有按值排序列表中相邻的节点对才能找到最小间隙；由r.L节点存储的值组成的对的最小间隙在r.L根的x值中，考虑右子树时也是如此。鉴于（r.L中任何节点的值）< r.L根节点的值 <（r.R中任何节点的值），未考虑的唯一相邻值对是两个：

1. 由根节点值和较高r.L节点值组成的一对
2. 由根节点值和较低r.R节点值组成的一对

根据AVL树的性质，具有较高值的r.L节点是其最右侧的叶子节点，而具有较低值的r.R节点是其最左侧的叶子节点。 将r x值赋为四个值（r.L root x value、r.R root x value、（r-r.L root）gap、（r-r.R root）gap）之间的最小值，与分配整个树中相邻节点值之间较小的差距相同，相当于任何可能的节点值对之间更小的差距。 其中一个或两个子树为空的情况是微不足道的。 对于仅由一个或三个节点构成的树的基本情况，很容易看出树根的x值是最小差值。

- pangon

---

我不明白两件事情。 我们在插入时会分配这个字段(x)和它的值吗？ 另外，你所说的r值和r.L上最右边的叶子的值是什么意思？ 你的意思是最小间隙在“r值”和“r.L上最右边的叶子”的值之间吗？ - TheNotMe

是的，“x”字段需要额外的空间，但附加的空间复杂度为O(n)（每个n个节点中的一个int），考虑到标准AVL树已经需要O(n)，因此空间复杂度不会增加（是的，无疑它需要更多的空间，但复杂度的顺序是相同的，O(n+n)=O(n)）。对于插入/删除时间复杂度也是如此：如果您添加了最多O(log(n))的计算，则原始的O(log(n))时间复杂度将保持不变。实现肯定需要更长的执行时间，但只有一个常数因子：该结构不会失去可扩展性。 - pangon

当节点插入树中时，x值会被添加，并且在需要时会通过其他节点的插入/删除进行更新。是的，“节点值”是指您正在构建树的数字。 - pangon

非常棒的方法。谢谢。 但我很好奇，您是如何知道如果（在这个条件下）->（最小间隔在这两个值之间）？ 有证明吗？ - TheNotMe

不过，这个算法并没有给我两个数字之间的“最小差距”是多少 o.O - TheNotMe

Answer 2

这个函数可能对你有帮助：

int getMinGap(Node N)
    {
        int a = Integer.MAX_VALUE ,b = Integer.MAX_VALUE,c = Integer.MAX_VALUE,d = Integer.MAX_VALUE;
        if(N.left != null) {
            a = N.left.minGap;
            c = N.key - N.left.max;
        }

        if(N.right != null) {
            b = N.right.minGap;
            d = N.right.min - N.key;
        }

        int minGap = min(a,min(b,min(c,d)));

        return minGap;
    }

这里是 Node 数据结构：

class Node
{
    int key, height, num, sum, min, max, minGap;
    Node left, right;

    Node(int d)
    {
        key = d;
        height = 1;
        num = 1;
        sum = d;
        min = d;
        max = d;
        minGap = Integer.MAX_VALUE;
    }
}

- Parag Jain