Dato un insieme di dati in un albero di ricerca binario, come i numeri da 1 a 10, è possibile che esistano più alberi di ricerca binari bilanciati?È possibile avere più BST validi per un determinato set di dati?
Oppure c'è solo una BST bilanciata unica per quel set di dati?
Grazie
Tutto dipende dalla specifica struttura di dati ad albero binario in uso, l'algoritmo di inserimento, i criteri di bilanciamento e l'ordine di inserimento, ma sì - è possibile avere equivalente multipla e BST equilibrate valide per un data sequenza di valori.
Ad esempio, questo è un valido Red/Black Tree dove i numeri 1-10 sono stati inseriti in ordine crescente:
D'altra parte, questo è un valido AVL Tree, dove i numeri 1-10 sono stati inseriti esattamente nello stesso ordine come nel Albero Rosso/nero:
Chiaramente, gli alberi non sono esattamente gli stessi - ma il un ordinamento Le proprietà di bilanciamento tengono per entrambi.
Quindi, diciamo che stavo usando l'albero AVL, ci sarebbero più alberi AVL per lo stesso insieme di numeri? In tal caso, l'ordine di inserimento è l'azione che causa l'esistenza di questi alberi diversi? – user2305684
@ user2305684 se limitiamo la struttura ad una particolare implementazione, sì possiamo ancora ottenere risultati diversi a seconda dell'ordine degli inserimenti. Ma possiamo essere sicuri che se gli elementi sono inseriti nello stesso ordine per la stessa struttura dati e algoritmo, l'albero risultante sarà lo stesso –