Conteo del número de elementos menores que X en un árbol de búsqueda binario (BST)

He implementado un BST para un multiconjunto utilizando el código C++ que se muestra a continuación, donde cada nodo contiene el número de ocurrencias “num” de cada número distinto “data”, y trato de encontrar el número de elementos menores que cierto valor x utilizando la función “order” que aparece a continuación.

Funciona, sin embargo es ineficiente en términos de tiempo de ejecución.
¿Existe algún método con una complejidad de tiempo mejor?

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

davy.ai

June 11, 2023 at 9:05 am

Sí, hay un método con una complejidad temporal mejor. Dado que el BST está implementado para un multiconjunto, podemos modificar cada nodo para que tenga un campo adicional llamado count que mantenga el conteo del número de ocurrencias de todos los elementos menores o iguales a data. Luego podemos modificar la función order usando el campo count para encontrar el número de elementos menores que un cierto valor x en una complejidad temporal de O(log n).

La implementación modificada para la estructura de nodo sería la siguiente:

struct Nodo {
    int data;
    int height;
    int num;
    int count;

    Nodo *izquierda;
    Nodo *derecha;
};

Y la nueva implementación para la función order se muestra a continuación:

int order(Nodo *n, int x) {
    if (n == NULL) {
        return 0;
    } else if (n->data == x) {
        return n->count;
    } else if (n->data < x) {
        return n->num + n->izquierda->count + order(n->derecha, x);
    } else {
        return order(n->izquierda, x);
    }
}

La complejidad temporal de la función order modificada es O(log n) ya que estamos recorriendo el BST de manera de búsqueda en profundidad y cada nodo almacena el conteo de todos los elementos menores o iguales a data.

Answer

davy.ai

June 11, 2023 at 9:05 am
Sí, hay un método con una complejidad temporal mejor. Dado que el BST está implementado para un multiconjunto, podemos modificar cada nodo para que tenga un campo adicional llamado count que mantenga el conteo del número de ocurrencias de todos los elementos menores o iguales a data. Luego podemos modificar la función order usando el campo count para encontrar el número de elementos menores que un cierto valor x en una complejidad temporal de O(log n).

La implementación modificada para la estructura de nodo sería la siguiente:
```
struct Nodo {
    int data;
    int height;
    int num;
    int count;

    Nodo *izquierda;
    Nodo *derecha;
};
```
Y la nueva implementación para la función order se muestra a continuación:
```
int order(Nodo *n, int x) {
    if (n == NULL) {
        return 0;
    } else if (n->data == x) {
        return n->count;
    } else if (n->data < x) {
        return n->num + n->izquierda->count + order(n->derecha, x);
    } else {
        return order(n->izquierda, x);
    }
}
```
La complejidad temporal de la función order modificada es O(log n) ya que estamos recorriendo el BST de manera de búsqueda en profundidad y cada nodo almacena el conteo de todos los elementos menores o iguales a data.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Conteo del número de elementos menores que X en un árbol de búsqueda binario (BST)

Answer

davy.ai