I had implemented a BST for a multiset using the C++ code below, whereas each node contains the number of occurrence num
of each distinct number data
, and I try to find the number of elements less than certain value x, using the order
function below.
It works, however, inefficient in terms of execution time. Is there any method with better time complexity?
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;
}
Aucun commentaire:
Enregistrer un commentaire