寻找最近的一对
Finding Closest Pair
我有一个 AVL 树,我必须在其中找到最接近的对,因为两个节点的值差异最小。没有重复值,必须在 O(log n) 下完成。
示例:
插入(9),插入(2),插入(14),插入(10).
这棵树中最接近的对是 (9,10)。
但我不确定如何实现它。
我只知道,每个节点的最近对可以通过取左边和节点的最大值,或者右边的最小值来计算。
但是,如果我要为每个节点计算它,它肯定会超过 logn。
有什么想法吗?
编辑:忘了说我正在自己设计插入函数,所以我可以对每个节点进行更改,以便它可以包含更多关于最近对函数的信息
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 复杂度也不受影响。
一个重要的观察是形成“最佳”对的节点不能属于不同的子树——在任何级别。显然,他们每个人都更接近共同的祖先而不是彼此。这意味着最好的一对总是由某个节点和它的一些后代组成。
因此,新插入的节点只能沿着它的搜索路径提高记录。同样重要的是要记住,这个新人总是以叶子结束。
在伪代码中:
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;
}
}
}
现在可以在固定时间内回答查询。插入仍然是对数的,尽管具有最差的渐近常数。也许,因为你只需要在对数时间回答查询,这个解决方案可以改进。
我有一个 AVL 树,我必须在其中找到最接近的对,因为两个节点的值差异最小。没有重复值,必须在 O(log n) 下完成。
示例: 插入(9),插入(2),插入(14),插入(10).
这棵树中最接近的对是 (9,10)。
但我不确定如何实现它。
我只知道,每个节点的最近对可以通过取左边和节点的最大值,或者右边的最小值来计算。 但是,如果我要为每个节点计算它,它肯定会超过 logn。
有什么想法吗?
编辑:忘了说我正在自己设计插入函数,所以我可以对每个节点进行更改,以便它可以包含更多关于最近对函数的信息
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 复杂度也不受影响。
一个重要的观察是形成“最佳”对的节点不能属于不同的子树——在任何级别。显然,他们每个人都更接近共同的祖先而不是彼此。这意味着最好的一对总是由某个节点和它的一些后代组成。
因此,新插入的节点只能沿着它的搜索路径提高记录。同样重要的是要记住,这个新人总是以叶子结束。
在伪代码中:
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;
}
}
}
现在可以在固定时间内回答查询。插入仍然是对数的,尽管具有最差的渐近常数。也许,因为你只需要在对数时间回答查询,这个解决方案可以改进。