计算 BST 中小于 X 的元素数
counting number of elements less than X in a BST
我已经使用下面的 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;
}
您可以通过在每个节点中存储以它为根的子树中的元素数量,将算法缩短为 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
) .
如果您可以将大小添加到您的结构中,我强烈建议您使用 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
.
我已经使用下面的 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;
}
您可以通过在每个节点中存储以它为根的子树中的元素数量,将算法缩短为 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
) .
如果您可以将大小添加到您的结构中,我强烈建议您使用 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
.