lundi 29 novembre 2021

counting number of elements less than X in a BST

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