struttura dati che supporta in modo efficiente le operazioni di search, get maximum/minimum, predecessor/successor, inser, delete
Un albero è un grafo non orientato, connesso e aciclico. I vertici di un albero sono detti nodi.
Un albero radicato è un albero in cui si distingue un nodo, detto radice, dagli altri nodi. (La radice è infatti l'unico nodo che non ha un padre)
Sia x un nodo di un albero con radice R: qualunque nodo y sull'unico cammino da R a x è chiamato antenato di x e x si dice discendente di y.
Il sottoalbero radicato in x è l'albero indotto dai discentendi di x, radicato in x.
Se l'ultimo arco di un cammino dalla radice R ad un nodo x è l'arco (x, y) allora x è il padre di y e y è il figlio di x.
La radice è l'unico nodo che non ha padre.
Un nodo senza figli si dice foglia. Un nodo non foglia è detto nodo interno.
Un albero ordinato è un albero radicato in cui i figli di ciascun nodo sono ordinati, cioè si distingue il primo figlio, il secondo figlio etc.
Un albero posizionale è un albero radicato in cui i figli di ciascun nodo sono etichettati con interi positivi distinti. L'i-esimo figlio di un nodo è assente se nessun figlio è etichettato con l'intero i.
Un albero k-ario è un albero posizionale in cui in ogni nodo tutti i figli con etichetta più grande di k sono assenti.
Un albero k-ario completo è un albero k-ario in cui tutte le foglio hanno la stessa profondità e tutti i nodi interni hanno grado k.
Un albero binario è una struttura definita su un insieme finito di nodi che non contiene nessun nodo opporure è composto da 3 insiemi disgiunti di nodi un nodo radice, un albero binario chiamato sottoalbero sinistro e un albero binario chiamato sottoalbero destro.
Un albero binario è un albero posizionale con nodi con grado al più 2. (In un albero ordinato non si distingue tra figlio destro e figlio sinistro, ma si considera solo il numero di figli)
Un albero binario completo ha 2h-1 nodi e profondità h=log2n.
Un albero binario si dice bilanciato se per ogni suo nodo vale che il numero di nodi del sottoalbero di sinistra differisce al più di una quantità dal numero di nodi del sottoalbero di destra.
In un BST i nodi hanno un campo chiave key e sono ordinati in base ad esso. Per ciascun nodo x vale che:
I BST sono definiti in modo tale che le operazioni abbiano una complessità O( h )
Per un albero completo e bialnciato con n nodi la complessità è quindi O( log2n )
Per un albero totalmente sbilanciato si ricade nel caso peggiore O( n )
Per un albero casuale ci si aspetta O( log2n )
Dato un BST è possibile definire delle operazioni di visita di tutti i nodi secondo tre ordini diversi:
Tutti gli attraversamenti hanno complessità O( n ), in quanto ciascun nodo viene considerato esattamente una volta
Entrambe le operazioni hanno complessità O( h )
Possono presentarsi due casi:
if ( right[x] ) return Tree-Minimum( right[x] ) y <-- p[x] while( y and x = right[y] ) x <-- y y <-- p[x] return y |
Complessità: O( h )
Possono presentarsi due casi:
if ( left[x] ) return Tree-Maximum( left[x] ) y <-- p[x] while( y and x = left[y] ) x <-- y y <-- p[x] return y |
Complessità: O( h )
Queste operazioni richiedono di modificare la struttura dati, aggiungendo o togliendo nodi, mantenendo la proprietà di ordinamento propria del BST.
Il nuovo nodo è inserito come una nuova foglia, la posizione è ottenuta simulando l'operazione di ricerca
y <-- NULL x <-- root[T] while ( x ) y <-- x if ( key[z] < key[x] ) x <-- left[x] else x <-- right[x] p[z] <-- y if ( !y) root[T] <-- z else if ( key[z] < key[y] ) left[y] <-- z else right[y] <-- z |
Complessità: O( n )
La cancellazione è l'operazione più complessa in un BST, in quanto il nodo da cancellare potrebbe avere 0, 1 o 2 figli, e occorre ricollegare i nodi rimasti in assenza di quello cancellato. Nascono quindi 3 casi:
if ( !left[z] or !right[z] ) y <-- z else y <-- Tree-Successor[z] if ( left[y] ) x <-- left[y] else x <-- right[y] if ( x ) p[x] <-- p[y] if ( !p[y] ) root[T] <-- x else if ( y = left[ p[y] ] ) left[ p[y] ] <-- x else rigth[ p[y] ] <--x if ( y != z ) key[z] <-- key[y] fields[z] <-- fields[y] return y | 0 o 1 figlio 2 figli x unico figlio di y aggiorno padre di x elimino la radice collego x al padre di y ricopia le info del successore nel nodo da eliminare |
Complessità: O( n )