Rosso Nero Albero di rotazione e di Colore Flip

Thamindu Dilshan Jayawickrama
Thamindu Dilshan Jayawickrama

Seguire

Lug 11, 2020 · 6 min leggere

Una tipica ricerca di albero come Binary Search Tree (CEST) potrebbero avere un’altezza di O(n), che potrebbe comportare nel caso peggiore complessità di O(n) per le operazioni di base come la ricerca, inserimento, cancellazione, etc. Questo dipende interamente dall’ordine degli elementi che vengono inseriti nel BST. Ma, ci sono alcune situazioni in cui non abbiamo l’intero elemento impostato quando si inizia a costruire l’albero. Ecco dove entrano in gioco gli alberi di ricerca equilibrati. In un albero di ricerca bilanciato, un’altezza di O(log n) è garantita quando si implementa un set dinamico di n elementi. Alberi rosso-neri, alberi AVL, alberi 2-3 e alberi B sono alcuni degli esempi per le implementazioni degli alberi di ricerca bilanciati. Questo articolo è tutto sulle operazioni di modifica albero coinvolti con alberi rosso-nero.

Un albero Rosso-Nero (RB-Tree) è un albero di ricerca binario autobilanciato in cui ogni nodo segue un insieme di regole. Ogni nodo in un albero RB ha un attributo extra; il colore, che potrebbe essere rosso o nero. In una tipica implementazione RB-Tree, ci sarà un insieme di nodi sentinella per segnalare che viene raggiunto un nodo foglia. Questi nodi sono indicati come NULL (o NILs) e considerati come nodi foglia in questo articolo. Di seguito sono riportati l’insieme di regole o le proprietà che ogni nodo dovrebbe seguire.

  1. Ogni nodo è rosso o nero.

2. La radice e le foglie sono nere.

3. Se un nodo è rosso, il suo genitore è nero.

4. Tutti i percorsi semplici da qualsiasi nodo a una foglia discendente hanno lo stesso numero di nodi neri (altezza nera).

L’altezza di un RB-Albero rimane a O(log n) dopo ogni albero operazione di modifica che ha un garantito limite superiore di O(log n) per tali operazioni. Le operazioni Inserisci ed Elimina causano modifiche all’albero RB. Dopo ogni operazione di modifica dell’albero, l’albero sarà auto-bilanciato attraverso cambiamenti di colore e rotazioni. Prima di entrare in queste operazioni, dovremmo avere familiarità con la seguente notazione.

Una rotazione è una operazione speciale progettato per l’ bilanciamento Binari di Ricerca, Alberi che possono essere eseguite in O(1) tempo. Una proprietà interessante sulle rotazioni è che conserva l’attraversamento inorder delle chiavi (ordinamento delle chiavi).

La decisione di eseguire una rotazione o un cambiamento di colore è basato sulla zia del nodo (il nodo corrente). Se il nodo ha una zia Nera, facciamo una rotazione. Se il nodo ha una Zia rossa, facciamo un flip di colore. Dopo aver eseguito una rotazione, dovremmo colorare l’albero. Dopo aver eseguito tali operazioni, l’albero dovrebbe essere terminato come di seguito.

Se il nodo corrente è di sinistra, figlio di suo nonno sinistra del bambino, abbiamo diritto ruotare il nonno intorno al padre. Se il nodo corrente è il figlio giusto del figlio destro del nonno, abbiamo lasciato ruotare il nonno attorno al genitore. Se il nodo corrente è il figlio destro del figlio sinistro del nonno, eseguiamo una rotazione sinistra-destra in cui ruotiamo il nonno e il bambino attorno al genitore. Se il nodo corrente è il figlio sinistro del figlio destro del nonno, eseguiamo una rotazione destra-sinistra in cui ruotiamo il nonno e il bambino attorno al genitore. Tutte le rotazioni possono essere riassunte come al diagramma qui sotto.

Un fatto importante da ricordare è che, dopo l’esecuzione di un albero qualunque operazione di modifica, è necessario convalidare l’albero contro il set di regole per scoprire se eventuali violazioni ci sono. Se c’è una violazione (es: la radice è rossa) dovresti correggerla. Ora costruiamo un semplice albero RB inserendo sotto il set di chiavi. Si noti che per semplicità, i nodi foglia (NULL) vengono ignorati nei diagrammi sottostanti.

5, 8, 1, 10, 9, 15, 20

Dovremmo inserire ogni chiave come un nodo rosso. Pertanto inseriamo 5 come nodo rosso e lo coloriamo immediatamente in nero poiché è il nodo radice. Quindi inseriamo 8 come figlio destro del nodo 5. seguiamo la proprietà BST di base quando si inseriscono le chiavi. Inserire 1 equivale a inserire 8.

a quel punto, si dovrebbe inserire 10 8 diritto del bambino. Lo inseriamo come nodo rosso e controlliamo le violazioni. Sia 8 che 10 sono nodi rossi e sta violando la proprietà 3rd. Dovremmo controllare la zia ed e ‘ rossa. Quindi eseguiamo un flip di colore. Dopo il flip di colore, possiamo vedere che il nodo radice è rosso e sta violando la proprietà 2nd. Quindi lo risolviamo cambiando il colore del nodo radice.

a quel punto, si dovrebbe inserire la chiave 9. Dopo l’inserimento, possiamo vedere che entrambi i nodi 9 e 10 sono rossi e sta violando la proprietà 2nd. Controlliamo la zia e dato che è nera (i NULL sono neri), eseguiamo una rotazione destra-sinistra (la violazione è nella sottostruttura sinistra del bambino destro). Dopo la rotazione, dovremmo fare una correzione del colore.

Ora andiamo a inserire la chiave 15. Dopo l’inserimento, possiamo vedere che ci sono due nodi rossi consecutivi e la zia del 15 è un nodo rosso. Quindi dovremmo fare un flip di colore. Successivamente, controlliamo eventuali violazioni e possiamo scoprire che non ci sono violazioni.

Ora andiamo a inserire la chiave 20 per l’albero. Dopo l’inserimento, possiamo vedere che la zia è nera e quindi dovremmo eseguire una rotazione a sinistra (la violazione è nel sottoalbero destro del bambino destro). Dopo la rotazione, dovremmo fare una correzione del colore.

In questo articolo, abbiamo esaminato un particolare auto-bilanciamento binary search tree); Albero Rosso-Nero. Sono garantiti per avere un’altezza di O(log n), quindi avere una complessità temporale peggiore di O (log n) per le operazioni di base dell’albero. Alberi rosso-nero sono particolarmente utili in molte applicazioni di informatica. C++ Standard Template Library (STL) ha impostato, multiset, mappa, e multimap sulla base di RB-alberi. Inoltre, la TreeMap in linguaggio Java è un’implementazione NavigableMap basata su RB-Tree.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.