algorithm - programar - construir arbol binario de busqueda

Encontrar si un árbol binario es un árbol de búsqueda binaria

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo se valida un árbol de búsqueda binario? 27 respuestas

Hoy tuve una entrevista donde me pidieron que escribiera un programa que toma un árbol binario y devuelve verdadero si también es un árbol de búsqueda binaria que de otro modo es falso.

Mi método1: realice un recorrido en orden y almacene los elementos en el tiempo O (n). Ahora escanee a través de la matriz / lista de elementos y verifique si el elemento en su índice es mayor que el elemento en el (i + 1) índice. Si se encuentra dicha condición, devuelva false y salga del ciclo. (Esto toma O (n) tiempo). Al final, vuelve verdadero.

Pero este caballero quería que brindara una solución eficiente. Intenté pero no tuve éxito, porque para encontrar si es una BST tengo que verificar cada nodo.

Además, él me estaba señalando a pensar en la recursividad. Mi enfoque 2: A BT es una BST si para cualquier nodo N N-> a la izquierda es <N y N-> derecha> N, y el sucesor en orden del nodo izquierdo de N es menor que N y el sucesor en orden del nodo derecho de N es mayor que N y los subárboles izquierdo y derecho son BST.

Pero esto va a ser complicado y el tiempo de ejecución no parece ser bueno. Por favor, ayuda si conoces alguna solución óptima.

Answer 1

Aquí hay otra solución que usa 2 funciones auxiliares para calcular para cada nodo el valor mínimo y máximo en el subárbol usando la función auxiliar minValue y maxValue

int isBST(struct node* node)
    {
      if (node == NULL)
        return(true); 

      /* false if the max of the left is > than us */
        if (node->left!=NULL && maxValue(node->left) > node->data)
            return(false); 

      /* false if the min of the right is <= than us */
        if (node->right!=NULL && minValue(node->right) < node->data)
            return(false); 

      /* false if, recursively, the left or right is not a BST */ 
         if (!isBST(node->left) || !isBST(node->right))
           return(false); 

      /* passing all that, it''s a BST */
          return(true);
    }

Answer 2

Creo que el segundo enfoque es correcto. El árbol se puede atravesar de forma recursiva. En cada iteración, se pueden almacenar los límites inferior y superior del subárbol actual. Si queremos verificar el subárbol con root x, y los límites para el subárbol son l y h, entonces todo lo que necesitamos es verificar que l <= x <= h y verificar el subárbol izquierdo con los límites ly x, y el derecho uno con límites x y h.

Esto tendrá O (n) complejidad, porque comenzamos desde la raíz y cada nodo se verifica solo una vez como raíz de algún subárbol. Además, necesitamos memoria O (h) para llamadas recursivas, donde h es la altura del árbol.

Answer 3

Eche un vistazo a esta solución: http://preparefortechinterview.blogspot.com/2013/09/am-i-bst.html

Explica diferentes formas y también te proporciona un método genérico y eficiente. Espero eso ayude.

Answer 4

Es un problema bastante conocido con la siguiente respuesta:

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
     if(node == null)
         return true;
     return node.value > l 
         && node.value < h
         && isValidBST(node.left, l, node.value)
         && isValidBST(node.right, node.value, h);
}

La llamada recursiva se asegura de que los nodos del subárbol estén dentro del rango de sus antepasados, lo cual es importante. La complejidad del tiempo de ejecución será O (n) ya que cada nodo se examina una vez.

La otra solución sería hacer un recorrido intermedio y verificar si la secuencia está ordenada, especialmente dado que ya sabe que se proporciona un árbol binario como entrada.

Answer 5

Hay algunos ejemplos más arriba que usan INTEGER.MAX Y MIN No puedo ver una razón para pasarlos y su significado, corregirme si me equivoco de todos modos o explicarme el motivo.

Más del árbol de búsqueda binaria puede tener objetos que se comparan por el método compareTo o Coperator .. (por lo tanto Integer.MIN e Integer.MAX no se ajustan a ese modelo) Estoy escribiendo un código donde devuelve verdadero o falso uno tiene que llamar (root_node , verdadero) y volverá verdadero si es un bst más falso

void boolean isBSt( node root_node, boolean passed_root)
{

  if ( node==null){
        if ( passed_root)
        return false;
        // you have passed null pointer as 
        //root of the tree , since there is no 
        // valid start point we can throw an exception or return false      
        return true;
   }

  if( node.right !=null ) 
     if ( node.right.data <= node.data)
   return false;

  if ( node.left !=null ) 
        if ! ( node.left.data <= node.data) 
    return false;

  return ( isBST( node.right , false) && isBST( node.left, false ) )

}

Answer 6

La respuesta proporcionada por @Dhruv es buena. Además de eso, aquí hay otra solución que funciona en O (n) tiempo.
Necesitamos hacer un seguimiento del nodo anterior en este enfoque. En cada llamada recursiva verificamos los datos del nodo anterior con los datos del nodo actual. Si los datos del nodo actual son menores que los anteriores, devolvemos los datos falsos

int isBST(node* root) {
  static node* prev  = NULL;

  if(root==NULL)
    return 1;

  if(!isBST(root->left))
    return 0;

  if(prev!=NULL && root->data<=prev->data)
    return 0;

  prev = root;
  return isBST(root->right);
}

Answer 7

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max){
  if(node == null){
    return true;
  }

  boolean left  = isBinarySearchTree(node.getLeft(), min, node.getValue());
  boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

  return left && right && (node.getValue()<max) && (node.getValue()>=min);      
}

Los comentarios están invitados. Gracias.