我有一個 AVL 樹，我必須在其中找到最接近的對，就像差異最小的兩個節點的值一樣。沒有重復值，并且必須在 O(log n) 下完成。
示例：插入 (9)、插入 (2)、插入 (14)、插入 (10)。
這棵樹中最接近的對是 (9,10)。
但我不確定如何實作這一點。
我只知道，每個節點的最近對可以通過取左邊的最大值和節點的最小值，或者右邊的最小值來計算。但是如果我要為每個節點計算這個，它肯定會超過登錄。
有任何想法嗎？
編輯：忘了提到我自己設計了插入函式，所以我可以對每個節點進行更改，以便它可以包含更多關于最近對函式的資訊
uj5u.com熱心網友回復：
一個重要的觀察是，形成“最佳”對的節點不能屬于不同的子樹——在任何級別。顯然，他們每個人都比彼此更接近共同的祖先。這意味著最好的對總是由某個節點和它的一些后代組成。
因此，新插入的節點只能沿著其搜索路徑改進記錄。同樣重要的是要記住，這個新來者總是以葉子的形式結束。
在偽代碼中：
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;
}
}
}
現在查詢在恒定時間內得到答復。插入仍然是對數的，盡管具有最差的漸近常數。也許，由于您只需要在對數時間內回答查詢，因此可以改進此解決方案。
uj5u.com熱心網友回復：
編輯：忘了提到我自己設計了插入函式，所以我可以對每個節點進行更改，以便它可以包含更多關于最近對函式的資訊
這改變了一切。如果你對其他功能沒有限制，那就很容易了。
有兩棵 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。
它還將使用大約兩倍的記憶體。這意味著空間復雜度也不受影響。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424324.html
上一篇：了解排序平方演算法
下一篇：如何解決段樹上的問題