universityin-classsubject-2101
2023-10-26
Algoritmi
BST: Binary Search Trees
Il BST è posizionale. Consideriamo 4 configurazioni:
- Nodo senza figli
- Nodo con figlio destro
- Nodo con figlio sinistro
- Nodo con entrambi i figli.
Se non fosse posizionale non faremo distinzione tra figlio destro e figlio sinistro (il figlio non avrebbe una posizione rispetto al padre).
Ricordando la definizione di BST. Ogni nodo deve essere più grande di tutti i nodi del sotto albero sinistro e più piccolo di tutti i nodi del sotto albero di destra (l’ordinamento è totale, non parziale).
Tutte le operazioni richiedono tempo logaritmico, ma nel caso peggiore il tempo diventa lineare. Questo si può evitare realizzando una struttura dati che sia in grado di “eliminare” il caso pessimo autobilanciandosi. Queste strutture si dicono alberi autobilancianti (tra i più famosi, AVL, Zig-Zag Trees, RB Trees).
Gli alberi rosso neri effettuano un ribilanciamento in tempo logaritmico (a volte anche costante).
Red-Black Trees
Ogni nodo ha un’informazione aggiuntiva: un bit che indica il colore (rosso o nero).
Le regole di un albero rosso-nero sono 5:
- Ogni nodo dell’albero dev’essere colorato nero o rosso
- La radice dev’essere nera
- Tutte le foglie devono essere nere. Spesso questa regola viene rilassata:
- Si assume che i figli di ogni foglia (null) siano neri.
- Oppure, si crea un nodo nero e si collegano tutti i puntatori dei figli delle foglie a questo nodo unico.
- Un nodo rosso deve avere necessariamente figli neri.
- Tutti i cammini da ogni nodo verso ogni foglia devono avere lo stesso numero di nodi neri.
Un ramo con tutti i nodi neri si dice compatto.
Identifichiamo con
Identifichiamo con
Grazie alle proprietà dell’albero rosso nero, vale la seguente disuguaglianza:
Il ribilanciamento avviene attraverso delle operazioni di rotazione.
La operazioni di rotazione mantengono l’ordinamento totale, ma non garantiscono la permanenza delle 5 regole dei RBT.
Inserimento di un nodo
Padre nero
Se il padre del nodo da inserire è nero, posso aggiungere il nuovo nodo come rosso, e ho risolto.
Padre rosso
Il nonno è sicuramente nero (non possono esistere due nodi rossi consecutivi).
Si aggiunge il nodo come rosso e si effettuano delle operazioni.
Caso 1: zio rosso
Il nonno diventa rosso
Il padre e lo zio diventano neri
Si richiama ricorsivamente la funzione Fixup sul nonno.
Caso 2: figlio esterno (sinistro), zio nero
Si effettua una rotazione destra sul padre.
Il (vecchio) nonno diventa rosso, il (vecchio) padre nero (si scambiano il colore)
Caso 3: figlio interno (destro), zio nero
Si effettua la rotazione sinistra sul nodo e ci si ritrova nel caso 2.
I tre casi precedenti valgono in maniera speculare.