寻找最近的一对

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

现在查询会在恒定时间内得到答复。尽管渐近常数最差，但插入仍然是对数的。也许，由于你只需要在对数时间内回答查询，这个解决方案可以改进。