algorithm - possono - cancellazione nodo albero binario di ricerca



Scoprire se un albero binario è un albero di ricerca binario (5)

Questa domanda ha già una risposta qui:

Oggi ho avuto un'intervista in cui mi è stato chiesto di scrivere un programma che accetta un albero binario e restituisce vero se è anche un albero di ricerca binario altrimenti falso.

Il mio approccio1: eseguire un traversal in ordine e memorizzare gli elementi nel tempo O (n). Ora scansiona l'array / elenco di elementi e controlla se l'elemento di questo indice è maggiore dell'elemento a (i + 1) indice. Se si verifica una condizione di questo tipo, restituire false e uscire dal ciclo. (Questo richiede O (n) tempo). Alla fine ritorna vero.

Ma questo signore voleva che fornissi una soluzione efficiente. Ho provato ma non ho avuto successo, perché per trovare se è un BST devo controllare ogni nodo.

Inoltre mi stava indicando di pensare alla ricorsione. Il mio approccio 2: Un BT è un BST se per qualsiasi nodo N N-> sinistra è <N e N-> destra> N, e il successore in ordine del nodo sinistro di N è minore di N e il successore in ordine del nodo destro di N è maggiore di N e i sottoalberi sinistro e destro sono BST.

Ma questo sarà complicato e il tempo di esecuzione non sembra essere buono. Si prega di aiutare se si conosce una soluzione ottimale.

https://src-bin.com


Answer #1

È un problema abbastanza noto con la seguente risposta:

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 chiamata ricorsiva fa in modo che i nodi di sottostruttura si trovino all'interno del raggio d'azione dei suoi antenati, il che è importante. La complessità del tempo di esecuzione sarà O (n) poiché ogni nodo viene esaminato una volta.

L'altra soluzione consisterebbe nel fare un traversal inorder e controllare se la sequenza è ordinata, specialmente perché sai già che un albero binario è fornito come input.


Answer #2

Ci sono alcuni esempi sopra usando INTEGER.MAX E MIN. Non vedo un motivo per passarli e il significato di esso, correggimi se sbaglio in ogni caso o spiegami il motivo.

Più albero di ricerca binario può avere oggetti che vengono confrontati con il metodo compareTo o con Coperator .. (quindi Integer.MIN e Integer.MAX non si adattano a quel modello) Sto scrivendo un codice dove restituisce vero o falso che si deve chiamare (root_node , vero) e restituirà true se è un altro 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 #3

Ecco un'altra soluzione che utilizza 2 funzioni di supporto per calcolare per ciascun nodo il valore minimo e massimo nella sottostruttura utilizzando la funzione di supporto minValue e 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 #4

La risposta fornita da @Dhruv è buona. In aggiunta a ciò ecco un'altra soluzione che funziona nel tempo O (n).
Abbiamo bisogno di tenere traccia del nodo precedente in questo approccio. In ciascuna chiamata ricorsiva controlliamo i dati del nodo precedente con i dati del nodo corrente. Se i dati del nodo corrente sono inferiori al precedente, restituiamo false

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 #5
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);      
}

I commenti sono invitati Grazie.





binary-search-tree