Più piccolo a sinistra, più grande a destra

Nell’immagine

1. 1La radice: la prima chiave con cui ogni ricerca si confronta
2. 2Figlio sinistro: minore della radice, quindi va a sinistra
3. 3Figlio destro: maggiore della radice, quindi va a destra
4. 4Una foglia del sottoalbero destro: maggiore della radice ma minore del suo genitore, quindi sta alla sinistra di quest'ultimo

Esempi

• Indovinare un numero da 1 a 100 quando ogni risposta è «più alto» o «più basso» elimina metà di ciò che resta
• Cercare una parola in un dizionario cartaceo aprendolo a metà e andando avanti o indietro

Quiz: Più piccolo a sinistra, più grande a destra (17 anni)

1. 1

   In un albero binario di ricerca, quali chiavi possono trovarsi in qualsiasi punto del sottoalbero sinistro di un nodo con chiave 50?

   • Chiavi minori di 50 subito sotto il nodo, ma qualsiasi chiave più in basso
   • Solo chiavi minori di 50
   • Qualsiasi chiave, purché il figlio sinistro diretto del nodo sia minore di 50
2. 2

   Un albero binario di ricerca ha radice 50, e il figlio destro della radice è 80. Dove va una nuova chiave 60?

   • Nel sottoalbero destro, a sinistra di 80
   • Nel sottoalbero destro, a destra di 80
   • Nel sottoalbero sinistro, perché 60 è minore di 80
3. 3

   Quando cerchi una chiave in un albero binario di ricerca ben bilanciato, circa quanti nodi controlli?

   • Tutti i nodi dell'albero
   • Tutti i nodi di un livello prima di scendere al successivo
   • Circa un nodo per livello

Le risposte, con la spiegazione, sono nell’app. Questa lezione è uscita dalla settimana ad accesso libero, quindi il suo quiz fa parte dell’abbonamento.