c++ - respuestas - estadística elemental johnson r

Para encontrar el elemento más grande más pequeño que K en un BST

Question

Dado un árbol de búsqueda binario y un entero K, me gustaría encontrar el elemento más grande menos que K.

En el árbol de abajo,

for K = 13, result = 12
for K = 10, result = 8
for K = 1 (or) 2, result = -1

      10

  5       12

2   8   11  14

Probé la lógica de abajo. Pero ¿hay alguna manera mejor de hacer esto?

int findNum(node* node, int K)
{
        if(node == NULL)
        {
                return -1;
        }
        else if(K <= node->data)
        {
                return findNum(node->left,K);
        }
        else if(K > node->data)
        {
                int t = findNum(node->right,K);
                return t > node->data ? t : node->data;
        }

        return -1;
}

Answer 1

Creo en el uso de las instalaciones de la biblioteca estándar. Por lo tanto, mi solución utiliza std::set . :-)

int largest_num_smaller_than(std::set<int> const& set, int num)
{
    std::set<int>::const_iterator lb(set.lower_bound(num));
    return lb == set.begin() ? -1 : *--lb;
}

Answer 2

Creo que la idea aquí es grabar el último nodo después del cual se mueve al subárbol correcto. Por lo tanto, el código será (ha sido actualizado).

int findNum (Node *node, int K)
{
    Node* last_right_move = NULL;

    while (node)
    {
        if (K<=node->data)
            node = node->left;
        else
        {
            last_right_move = node;
            node = node->right;
        }
    }

    if (last_right_move)
        return last_right_move->data;
    else
        return NOT_FOUND;  // defined previously. (-1 may conflict with negative number)
}

Answer 3

Eso es O (log n), que es el mínimo. Sin embargo, puede mejorar la eficiencia (lo que parece ser lo más importante para estos entrevistadores) y eliminar la posibilidad de desbordamiento de pila (¡tada!) Eliminando la recursión de la cola, convirtiendo esto en un bucle. Además, su código no funciona si el árbol contiene números negativos ... si quiere decir enteros no negativos , debe decirlo, pero si el entrevistador acaba de decir "enteros", entonces necesita un código ligeramente diferente y una API diferente. (Puede mantener la misma firma de función pero devolver K en lugar de -1 si falla).

Por cierto, ya que esta es una pregunta de entrevista, implementarla al llamar a una función de biblioteca le diría a la mayoría de los entrevistadores que eres un experto o que te estás perdiendo el punto o que no sabes cómo resolverlo. No ensucie ese tipo de cosas, solo trabaje en lo que sabe que el entrevistador quiere.

Aquí hay una implementación:

// Return the greatest int < K in tree, or K if none.
int findNum (Node* tree, int K)
{
    int val = K;

    while( tree )
        if( tree->data >= K )
            tree = tree->left;
        else{
            val = tree->data; 
            tree = tree->right;
        }

    return val;
}

Answer 4

Le sugiero que set::upper_bound el código en su implementación local de set::upper_bound para obtener orientación. Esta no es la solución a su problema exacto, pero está muy cerca.

En general, en la vida real, la mayoría de estos problemas no necesitan resolverse en su propio código. STL puede hacer muchas tareas comunes para usted. Es útil saber cómo resolverlos, por supuesto, de ahí la prueba.

Answer 5

Lo que dijo la primera respuesta, y aquí está la lógica detrás de por qué no puede mejorar que O (log n). Está buscando el número más grande menos que K. Esto está bastante cerca de llamar a BST-search / get.

Aunque su algoritmo original se ve bastante bien, creo que esto sería más rápido:

    int findNum (node root, int K) {
        if(root == null) return -1;

        if(K > root.val) { 
           if(root.right != null) return findNum(root.right, K);               
           else return root.val; 
        }

        return findNum(root.left, K); //look in left subtree

    }