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

Question

Dado un árbol binario de búsqueda y un entero K, me gustaría encontrar el elemento más grande menor 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 

Intenté la siguiente lógica. Pero, ¿hay alguna forma 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

Eso es O (log n), que es el mínimo. Sin embargo, puede mejorar la eficiencia (que parece ser lo principal que les importa a los entrevistadores) y eliminar la posibilidad de desbordamiento de pila (tada!) Al eliminar la recursividad de cola, convirtiendo esto en un bucle. Además, su código no funciona si el árbol contiene números negativos ... si se refiere a enteros no negativos enteros, debe decirlo, pero si el entrevistador acaba de decir "enteros", entonces necesita un código ligeramente diferente y un código diferente. API. (Podría mantener la misma firma de función pero devolver K en lugar de -1 al fallar.)

Por cierto, ya que esta es una pregunta de entrevista, implementarla llamando a una función de biblioteca le diría a la mayoría de los entrevistadores que usted es un listillo o falta el punto o no sabes cómo resolverlo. No juegues con ese tipo de cosas, solo ponte a trabajar en lo que sabes que el entrevistador quiere.

Aquí es 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 2

que sugieren que pases por el código de la implementación local de set::upper_bound de orientación. Esta no es la solución a su problema exacto, pero muy cerca.

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

Answer 3

Creo en el uso de las instalaciones de biblioteca estándar. Por lo tanto, mi solución usa 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 4

Creo que la idea aquí es para grabar el último nodo después de la cual se realiza el subárbol derecho. Por lo tanto, será (se ha actualizado) el código

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 5

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

Aunque el 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 

    }