计算 BST 中小于 X 的元素数

Question

我已经使用下面的 C++ 代码为多重集实现了 BST，而每个节点包含每个不同数字 data 的出现次数 num，我试图找到小于特定值 x 的元素，使用下面的 order 函数。

它可以工作，但是在执行时间方面效率低下。有没有时间复杂度更好的方法？

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;
}

Answer 1

您可以通过在每个节点中存储以它为根的子树中的元素数量，将算法缩短为 O(logN) 时间。然后你只需要递归每个节点的两个子节点之一（如果 x < node->data 则向左，如果 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) .

Answer 2

如果您可以将大小添加到您的结构中，我强烈建议您使用 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.

计算 BST 中小于 X 的元素数

counting number of elements less than X in a BST

c++

c++11

search

binary-search-tree