寻找最近的一对

Question

我有一个 AVL 树，我必须在其中找到最接近的对，因为两个节点的值差异最小。没有重复值，必须在 O(log n) 下完成。

示例：插入(9),插入(2),插入(14),插入(10).

这棵树中最接近的对是 (9,10)。

但我不确定如何实现它。

我只知道，每个节点的最近对可以通过取左边和节点的最大值，或者右边的最小值来计算。但是，如果我要为每个节点计算它，它肯定会超过 logn。

有什么想法吗？

编辑：忘了说我正在自己设计插入函数，所以我可以对每个节点进行更改，以便它可以包含更多关于最近对函数的信息

Answer 1

Edit: forgot to mention that I am designing the insert function myself, so I can make changes to each node so it can contain more info, in regard of the closest pair function

这改变了一切。如果你对其他功能没有任何限制，那就很简单了。

有两棵AVL树，A和B。你原来的A存值作为值，第二棵B树有最接近的对作为数据。除了将最接近的对存储为B中的值外，它还存储了指向A中相应节点的指针。一些不完整的代码：

struct Anode {
    struct Anode *left, *right;
    int value;
};

struct Bnode {
    struct Bnode *left, *right;
    int value;
    struct Anode *anode;
}

所以找到scp只是找到B中的最小元素。那个操作在O(log n)中完成。然后通过指向 A 树的指针准备好数据。

struct Anode *getSmallestSCP(struct Bnode *btree) {
    if(!btree) return NULL;

    if(!(btree->left)) return btree->anode;

    struct Bnode *scp = getSmallestSCP(btree->left);

    return scp->anode;
}

这意味着每次插入和删除都进行两次。这不会影响最坏情况下的时间复杂度。可能平均情况会受到影响。但是，我不确定 B 的重新计算是否可以在 O(log n) 中完成。很有可能。我根本不知道。但是你说问题是找到 O(log n) 中满足的 scp。

它还将使用大约两倍的内存。这意味着 space 复杂度也不受影响。

Answer 2

一个重要的观察是形成“最佳”对的节点不能属于不同的子树——在任何级别。显然，他们每个人都更接近共同的祖先而不是彼此。这意味着最好的一对总是由某个节点和它的一些后代组成。

因此，新插入的节点只能沿着它的搜索路径提高记录。同样重要的是要记住，这个新人总是以叶子结束。

在伪代码中：

node * best[2];

node * insert(node * root, int value)
{
    node * n = new_node(value);
    root = normal_avl_insert(root, n);
    update_best(root, n);
    return root;
}

void update_best(node * root, node * n)
{
    int current_record = abs(best[0]->value - best[1]->value);
    while (root->value != n->value) {
        if (abs(root->value - n->value) < current_record) {
            best[0] = root;
            best[1] = node;
        }

        if (n->value < root->value) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
}

现在可以在固定时间内回答查询。插入仍然是对数的，尽管具有最差的渐近常数。也许，因为你只需要在对数时间回答查询，这个解决方案可以改进。

寻找最近的一对

Finding Closest Pair

c

algorithm

binary-search-tree

avl-tree