Un Binary Search Tree (albero binario di ricerca, BST) è un tipo particolare di albero binario che soddisfa due condizioni:
Tutti i nodi figli di sinistra hanno un valore più piccolo del nodo padre.
Tutti i nodi figli di destra hanno un valore più grande del nodo padre.
Perciò, per ogni nodo, o non c’è un figlio, oppure ce n’è uno più piccolo a sinistra e uno più grande a destra.
Un Binary Search Tree con 8 nodi
Questa caratteristica risulta particolarmente utile quando si devono cercare elementi in un albero binario. Se cerchiamo un valore x, sapere come sono organizzati i nodi ci dice sempre da che parte muoverci per trovare quel valore. Nell’esempio qui sopra, per trovare il nodo con valore 3, inizieremmo dal nodo radice che ha valore 5: dato che 5 è maggiore di 3, ci spostiamo a sinistra. Poi incontriamo il nodo con valore 2, e poiché 2 è minore di 3, andiamo a destra. Quindi ci imbattiamo nel nodo con valore 4, e siccome 4 è maggiore di 3, ci spostiamo nuovamente a sinistra. Infine troviamo il nodo con valore 3: poiché 3 è uguale a 3, significa che l’abbiamo trovato.
# Supponiamo che i nodi inesistenti siano None anziché avere valore 0
def search(node: Node | None, x: int):
""" Restituisce True se x è presente nell'albero e False altrimenti """
if node is None: # Se abbiamo raggiunto la fine dell'albero
return False # Non abbiamo trovato il valore x
if x == node.value: # Se x è uguale a node.value
return True # => abbiamo trovato x nell'albero
if x < node.value: # Se x è più piccolo => dobbiamo spostarci a sinistra
return search(node.left) # Proviamo a trovare x nel sottoalbero di sinistra
return search(node.right) # Altrimenti proviamo a trovarlo in quello di destra
Questo metodo di ricerca è molto efficiente se l’altezza dell’albero è sufficientemente piccola. A ogni passo si va o a sinistra o a destra, quindi, nel caso peggiore, il numero di operazioni sarà proporzionale all’altezza dell’albero.
Challenge: Check if the given tree is a BST
Data un albero binario, il tuo compito è verificare se si tratta di un Binary Search Tree.
Input
L’input contiene interi separati da spazi, che rappresentano i valori dei nodi dell’albero binario. L’ordine dei valori segue una visita in cui, a ogni nodo, si esplora prima il sottoalbero di sinistra e poi quello di destra. Un valore di 0 indica che il nodo non esiste. È garantito che l’albero binario fornito sia valido e che i valori siano unici.
Output
Il programma deve stampare Yes se l’albero binario è un Binary Search Tree, altrimenti No.
Examples
Input (Ingresso)
Output (Uscita)
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
Yes
Explanation
Esempio 1: Sebbene tutti i nodi figli di destra siano maggiori dei rispettivi padri, non tutti i figli di sinistra risultano più piccoli del nodo padre.
Esempio 2: È un albero binario di ricerca perché tutti i nodi figli di sinistra hanno un valore inferiore al padre, mentre tutti i nodi figli di destra hanno un valore superiore al padre.
.png?table=block&id=18a2c681-664d-8133-b9d9-cfc12e4acea7&cache=v2)
