我已經使用下面的 C 代碼為多集實作了 BST，而每個節點都包含num每個不同 number的出現次數data，我嘗試使用order下面的函式找到小于某個值 x 的元素數。
然而，它在執行時間方面效率低下。有沒有時間復雜度更好的方法？
struct Node {
int data;
int height;
int num;
Node *left;
Node *right;
};
int order(Node *n, int x) {
int sum = 0;
if (n != NULL) {
if (n->data < x) {
sum = n->num;
sum = order(n->right, x);
}
sum = order(n->left, x);
}
return sum;
}
uj5u.com熱心網友回復：
您可以通過在每個節點中存盤它作為根的子樹中元素的數量，將演算法降低到 O(logN) 時間。然后你只需要對每個節點的兩個子節點之一進行遞回（向左 if x < node->data，向右 if x > node->data），如果樹是平衡的，則只需要對數時間。
struct Node {
int data;
int height;
int num;
int size; // numer of elements in the subtree starting at this node
Node *left;
Node *right;
};
int order(Node *n, int x) {
if(n == NULL) return 0;
// elements less than n->data make up the whole left subtree
if (x == n->data) {
return n->left ? n->left->size : 0;
}
// even smaller? just recurse left
else if (x < n->data) {
return order(n->left, x);
}
// bigger? take the whole left subtree and part of the right one
else {
return (n->left ? n->left->size : 0) order(n->right, x);
}
}
當然，現在您必須跟蹤大小，但這在更新樹時可以非常有效地完成：只需n->left->size n->right->size 1在插入或洗掉時重新計算每個修改節點的大小 ( )。
uj5u.com熱心網友回復：
如果您可以將大小添加到您的結構中，我強烈建議您使用 Dario Petrillo 的答案。
如果你必須堅持你的結構，你可以減少指令和遞回的數量。
int count_all(Node* n) {
int acc = n->num;
if (n->left != NULL) acc = count_all(n->left);
if (n->right != NULL) acc = count_all(n->right);
return acc;
}
int order(Node *n, int x) {
if (n == NULL) return 0;
// Find the first left node which is < x
while (n->data >= x) {
n = n->left;
if (n == NULL) return 0;
}
assert(n != NULL && n->data < x);
int sum = n->num;
// Grab everything left because all of them are < x
if (n->left != NULL) sum = count_all(n->left);
// Some of the right nodes may be < x, some may not
// Repeat the algorithm to find out
if (n->right != NULL) sum = order(n->right, x);
return sum;
}
當根大于x并且您想快速找到下一個滿足 的左節點時，這會減少遞回次數n->data < x。它還洗掉了與x樹的左側的大量不必要的比較，在那里您已經知道一切都是< x。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/371375.html
下一篇：變數未在__attribute__((constructor))內設定或在__attribute__((constructor))呼叫后重置全域靜態變數