ALBERI E ALBERI BINARI DI RICERCA (BST)

Indice

ALBERI

Definizione

Esempio

Terminologia

Alberi binari

Numero massimo di nodi per livello

Numero massimo di nodi per albero

Albero pieno

Rappresentazione collegata di un albero binario

Attraversamento degli alberi

BST

Esempio di BST

Rappresentazione collegata di un albero binario di ricerca

BST: operazioni specifiche

Inserimento in foglia

Complessità della ricerca

Inserimento in radice

Rotazioni

Inserimento in radice: esempio

Inserimento in radice: crescita

Selezione di un nodo

Partizione di un albero

Cancellazione di un nodo

Albero degenere

Inserimento casuale

Bilanciamento

Alberi AVL

Inserimento in alberi AVL

Alberi 2-3-4

Alberi 2-3-4: esempio

Alberi rosso-neri

Complessità delle operazioni sugli alberi

Miglioramenti

Autore: Massimo Bertozzi

eMail: bertozzi@ce.unipr.it

Homepage: http://www.ce.unipr.it/bertozzi

Migliore rappresentazione con