Informatica · Strutture dati
Range di altezza di un BST su tutti gli ordini di inserimento
Si considera l'INSIEME di chiavi $\{30, 12, 48, 5, 20, 60\}$ (ogni chiave, inserita in un albero binario di ricerca (BST) inizialmente vuoto, scende dalla radice verso sinistra se è minore del nodo corrente, verso destra altrimenti, finché non trova un posto libero; l'altezza è il numero di archi sul cammino più lungo dalla radice a una foglia, e un albero con la sola radice ha altezza $0$). Tra tutti i $6! = 720$ possibili ordini di inserimento di queste $6$ chiavi, qual è la differenza tra l'altezza massima e l'altezza minima che l'albero risultante può assumere?