[Algoritmi] Bilanciamento albero binario di ricerca

[matitti]

Ciao a tutti. Devo bilanciare un albero binario di ricerca sbilanciato in python ma trovo delle difficoltà nella formulazione dell'algoritmo.
La mia idea era di prendere tutti gli elementi dell'albero e di riutilizzarli per costruire un nuovo albero binario di ricerca, quindi in questo caso ho già dei vincoli per quanto riguarda la ricostruizione in questione ( se nodo_da_inserire < root, inserisci nel nodo di sinistra). Avendo questa regola da seguire mi riesce difficile pensare ad un modo per controllare anche il bilanciamento dell''albero in questione.
Potreste darmi qualche consiglio?

[apatriarca]

Se hai una lista ordinata di valori allora puoi costruire il tuo albero bilanciato semplicemente dividendo ad ogni passo l'albero "a metà". Scegli cioè il nodo centrale come radice e poi applichi in modo ricorsivo la procedura alla parte della lista che precede il valore e a quella che segue.

In alternativa puoi implementare le operazioni di bilanciamento di un albero binario. Se cerchi su internet o su un manuale gli alberi bilanciati dovresti trovare facilmente pseudocodici su come implementarli. Si tratta di un esercizio o di qualcosa che devi fare per qualche altra ragione?

[matitti]

Grazie per la risposta. Si tratta semplicemente di un esercizio che devo implementare in Python.

[matitti]

Scusate riapro questa conversazione ma ho un dubbio sugli alberi binari diricerca e vorrei una risposta. La mia domanda riguarda l'ordinamento dei nodi (so che alla sinistra della radice ho dei nodi di valore più basso della stessa e a destra di valore più alto), ma, guardando la foto allegata, sarebbe possibile avere al posto del 18 (la foglia in basso) un 46 ad esempio?

[apatriarca]

No, perché sarebbe maggiore di 21 e quindi non può stare alla sua sinistra.