c - 寻找最近的一对

Question

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

例子:插入(9)、插入(2)、插入(14)、插入(10)。

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

但我不确定如何实现它。

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

有什么想法吗？

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

Answer 1

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

因此，新插入的节点只能沿着其搜索路径改进记录。同样重要的是要记住，这个新来者最终总是一片叶子。

在伪代码中:

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

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