9

我有一个数据结构作业，除了常规的 AVL 树函数外，我还必须添加一个函数，该函数返回 AVL 树中任意两个数字之间的最小间隙（AVL 中的节点实际上代表数字。）

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

它应该在 O(1) 中完成。

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

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

4

2 回答 2

7

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

您有额外的限制不增加插入/删除/搜索功能的时间复杂度，我假设您也不想增加空间复杂度。

让我们考虑一个通用节点r，具有左子树rL和右子树rR；我们将扩展节点r中的信息附加数rx定义为以下之间的最小值：

  • （仅当 rL 不为空时）r 值和 rL 上最右边的叶子的值
  • （仅当 rL 比 1 更深时）rL 根节点的 x 值
  • （仅当 rR 不为空时）r 值和 rR 上最左边的叶子的值
  • （仅当 rR 比 1 更深时）rR 根节点的 x 值

（或者如果前面的条件都不是有效的，则在叶节点的情况下未定义）

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

您可以通过以下添加看到：

  • 空间复杂度仅增加一个常数因子
  • 插入/删除函数需要更新 x 值以及每个更改的子树的根的最左边和最右边的叶子，但是以不超过 O(log(n)) 的方式实现是微不足道的
  • 树根的 x 值是函数需要返回的值，因此您可以在 O(1) 中实现它

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

可以通过递归来证明该陈述：让我们考虑一棵以节点r为根的树，具有左子树rL和右子树rR。归纳假设是rL和rR x值的根是子树的节点值之间的最小间隙值。很明显，仅考虑值排序列表中值相邻的节点对就可以找到最小间隙；由rL的节点存储的值形成的对在rL根x值中具有最小间隙，考虑右子树也是如此。鉴于（rL中的任何节点值) < L根节点的值 <（rR中的任何节点值），唯一不考虑的相邻值对是两个：

  1. 由根节点值和较高的rL节点值组成的对
  2. 由根节点值和下rR节点值组成的对

根据 AVL 树属性，具有较高值的​​ rL节点是其最右边的叶子，具有较低值的rR节点是其最左边的叶子。将四个值（rL 根 x 值、rR 根 x 值、（r - rL 根）间隙、（r - rR 根）间隙）之间的最小值分配给rx值与分配连续节点值之间的较小间隙相同在整个树中，这相当于任何可能的节点值对之间的较小差距。一个或两个子树为空的情况是微不足道的。仅由一个或三个节点组成的树的基本情况，很容易看出树根的 x 值是最小间隙值。

于 2012-09-08T13:35:20.467 回答
0

此功能可能对您有所帮助：

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;
    }

这是节点数据结构：

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;
    }
}
于 2017-11-07T14:04:27.457 回答