logo

TechCodeview

Introduzione all'albero rosso-nero

Alberi di ricerca binaria sono fondamentali struttura dati, ma le loro prestazioni possono risentirne se l'albero si sbilancia. Alberi rossi neri sono un tipo di albero di ricerca binario bilanciato che utilizzano una serie di regole per mantenere l'equilibrio, garantendo complessità temporale logaritmica per operazioni come inserimento, cancellazione e ricerca , indipendentemente dalla forma iniziale dell'albero. Alberi rossi neri sono autobilancianti e utilizzano un semplice schema di codifica a colori per regolare l'albero dopo ogni modifica.

Albero Rosso-Nero



Tabella dei contenuti

Cos'è un albero rosso-nero?

UN Albero Rosso-Nero è un autobilanciamento albero di ricerca binario dove ogni nodo ha un attributo aggiuntivo: un colore, che può essere l'uno o l'altro rosso O nero . L'obiettivo principale di questi alberi è mantenere l'equilibrio durante gli inserimenti e le eliminazioni, garantendo un recupero e una manipolazione efficienti dei dati.

Proprietà degli alberi rosso-neri

UN Albero Rosso-Nero hanno le seguenti proprietà:



bloccare gli annunci su YouTube Android
  1. Colore del nodo : Ogni nodo è rosso o nero .
  2. Proprietà della radice : La radice dell'albero è sempre nero .
  3. Proprietà Rossa : I nodi rossi non possono avere figli rossi (non ci sono due nodi rossi consecutivi su nessun percorso).
  4. Proprietà nera : Ogni percorso da un nodo ai suoi nodi nulli discendenti (foglie) ha lo stesso numero di nero nodi.
  5. Proprietà fogliare : Tutte le foglie (nodi NIL) lo sono nero .

Queste proprietà assicurano che il percorso più lungo dalla radice a qualsiasi foglia non sia più lungo del doppio del percorso più breve, mantenendo l’equilibrio dell’albero e le prestazioni efficienti.

Esempio di albero rosso-nero

pulsante nel css centrale

IL Albero rosso-nero corretto nell'immagine sopra garantisce che ogni percorso dalla radice a un nodo foglia abbia lo stesso numero di nodi neri. In questo caso, ce n'è uno (escluso il nodo radice).



IL Albero rosso nero errato non segue le proprietà rosso-nero come due nodi rossi sono adiacenti tra loro. Un altro problema è che uno dei percorsi verso un nodo foglia ha zero nodi neri, mentre gli altri due contengono un nodo nero.

Perché alberi rosso-neri?

La maggior parte delle operazioni BST (ad esempio ricerca, max, min, inserimento, eliminazione, ecc.) richiedono OH) tempo dove h è l'altezza del BST . Il costo di queste operazioni potrebbe diventare SU) per uno sbilanciato Albero binario. Se ci assicuriamo che l'altezza dell'albero rimanga O(log n) dopo ogni inserimento ed eliminazione, possiamo garantire un limite superiore di O(log n) per tutte queste operazioni. L'altezza di un albero Rosso-Nero è sempre O(log n) dove n è il numero di nodi dell'albero.

Signor No.AlgoritmoComplessità temporale
1.RicercaO(log n)
2.InserireO(log n)
3.EliminareO(log n)

Confronto con Albero AVL :

Gli alberi AVL sono più bilanciati rispetto agli alberi Rosso-Nero, ma possono causare più rotazioni durante l'inserimento e la cancellazione. Quindi, se la tua applicazione prevede inserimenti ed eliminazioni frequenti, allora dovrebbero essere preferiti gli alberi Rosso-Neri. E se gli inserimenti e le cancellazioni sono meno frequenti e la ricerca è un'operazione più frequente, allora Albero AVL dovrebbe essere preferito all'albero rosso-nero.

In che modo un albero rosso-nero garantisce l'equilibrio?

Un semplice esempio per comprendere il bilanciamento è che una catena di 3 nodi non è possibile nell'albero Rosso-Nero. Possiamo provare qualsiasi combinazione di colori e vedere se tutti violano la proprietà dell'albero Rosso-Nero.

Struttura corretta di un albero rosso-nero a tre nodi

Punti interessanti sull'albero rosso-nero:

  • IL nero L'altezza dell'albero rosso-nero è il numero di nodi neri su un percorso dal nodo radice al nodo foglia. Vengono conteggiati anche i nodi foglia nero nodi. Quindi, un albero rosso-nero di altezza H ha altezza nero>= h/2 .
  • Altezza di un albero rosso-nero con N nodi è h<= 2 log 2 (n+1) .
  • Tutte le foglie (NIL) lo sono nero .
  • IL nero la profondità di un nodo è definita come il numero di nodi neri dalla radice a quel nodo, ovvero il numero di antenati neri.

Operazioni di base sull'albero rosso-nero:

Le operazioni di base su un albero rosso-nero includono:

RJ12 contro RJ11
  1. Inserimento
  2. Ricerca
  3. Cancellazione
  4. Rotazione

1. Inserimento

L'inserimento di un nuovo nodo in un albero rosso-nero prevede un processo in due fasi: l'esecuzione di uno standard Inserimento dell'albero di ricerca binario (BST). , seguito dalla correzione di eventuali violazioni delle proprietà Rosso-Nero.

Passaggi di inserimento

  1. Inserto BST : Inserisci il nuovo nodo come in un BST standard.
  2. Correggi le violazioni :
    • Se il genitore del nuovo nodo è nero , nessuna proprietà viene violata.
    • Se il genitore lo è rosso , l'albero potrebbe violare la Proprietà Rossa, richiedendo correzioni.

Correzione delle violazioni durante l'inserimento

Dopo aver inserito il nuovo nodo come a rosso nodo, potremmo incontrare diversi casi a seconda dei colori del genitore e dello zio del nodo (il fratello del genitore):

  • Caso 1: Lo zio è rosso : Ricolora il genitore e lo zio nero , e il nonno a rosso . Quindi spostati sull'albero per verificare ulteriori violazioni.
  • Caso 2: Lo zio è nero :
    • Sottocaso 2.1: Il nodo è un figlio destro : esegue una rotazione a sinistra sul genitore.
    • Sottocaso 2.2: Il nodo è un figlio sinistro : Esegui una rotazione a destra sul nonno e ricoloralo in modo appropriato.

2. Ricerca

La ricerca di un nodo in un albero rosso-nero è simile alla ricerca in uno standard Albero di ricerca binario (BST) . L'operazione di ricerca segue un percorso diretto dal file radice ad a foglia , confrontando il valore target con il valore del nodo corrente e spostandosi a sinistra o a destra di conseguenza.

Passaggi di ricerca

  1. Inizia dalla radice : Inizia la ricerca dal nodo radice.
  2. Attraversa l'albero :
    • Se il valore di destinazione è uguale al valore del nodo corrente, il nodo viene trovato.
    • Se il valore target è inferiore al valore del nodo corrente, spostati sul figlio sinistro.
    • Se il valore target è maggiore del valore del nodo corrente, spostati sul figlio destro.
  3. Ripetere : Continuare questo processo finché non viene trovato il valore target o viene raggiunto un nodo NIL (che indica che il valore non è presente nell'albero).

3. Cancellazione

Anche l'eliminazione di un nodo da un albero rosso-nero prevede un processo in due fasi: l'esecuzione della cancellazione del BST, seguita dalla correzione di eventuali violazioni che si verificano.

Passaggi di eliminazione

  1. Cancellazione BST : rimuovere il nodo utilizzando le regole BST standard.
  2. Correggi il doppio nero :
    • Se un nodo nero viene eliminato, potrebbe verificarsi una condizione di doppio nero, che richiede correzioni specifiche.

Correzione delle violazioni durante l'eliminazione

Quando un nodo nero viene eliminato, gestiamo la questione del doppio nero in base al colore del fratello e ai colori dei suoi figli:

  • Caso 1: Il fratello è rosso : ruota il genitore e ricolora il fratello e il genitore.
  • Caso 2: il fratello è nero :
    • Sottocaso 2.1: i figli del fratello sono neri : Ricolora il fratello e propaga il doppio nero verso l'alto.
    • Sottocaso 2.2: Almeno uno dei figli del fratello è rosso :
      • Se il figlio lontano del fratello è rosso : esegue una rotazione sul genitore e sul fratello e ricolora in modo appropriato.
      • Se il figlio vicino del fratello è rosso : Ruotare il fratellino e il bambino, quindi maneggiarlo come sopra.

4. Rotazione

Le rotazioni sono operazioni fondamentali per mantenere la struttura equilibrata di un Albero Rosso-Nero (RBT). Aiutano a preservare le proprietà dell'albero, garantendo che il percorso più lungo dalla radice a qualsiasi foglia non sia più del doppio della lunghezza del percorso più breve. Le rotazioni sono di due tipi: rotazioni a sinistra E rotazioni giuste.

1. Rotazione a sinistra

Una rotazione a sinistra nel nodo 𝑥 X si muove 𝑥 X in basso a sinistra e il suo bambino a destra 𝑦 E fino a prendere 𝑥 X è il posto.

Visualizzazione della rotazione sinistra 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Passaggi di rotazione a sinistra:

  1. Impostato E essere il figlio giusto di X .
  2. Mossa E è il sottoalbero sinistro di X è il sottoalbero destro.
  3. Aggiorna il genitore di X E E .
  4. Aggiornamento X il genitore da indicare E invece di X .
  5. Impostato E ha lasciato il figlio a X .
  6. Aggiornamento X il genitore di E .

Pseudocodice di rotazione a sinistra:

Rotazione a sinistra 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->Giusto;  x->destra = y->sinistra;  if (y->sinistra != NIL) { y->sinistra->genitore = x;  } y->genitore = x->genitore;  if (x->parent == nullptr) { root = y;  } else if (x == x->genitore->sinistra) { x->genitore->sinistra = y;  } else { x->genitore->destra = y;  } y->sinistra = x;  x->genitore = y; }>

2. Rotazione a destra

Una rotazione destra al nodo 𝑥 X si muove 𝑥 X in basso a destra e il suo bambino a sinistra 𝑦 E fino a prendere 𝑥 X è il posto.

algoritmo minimax
Visualizzazione della rotazione destra: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Passaggi di rotazione a destra:

  1. Impostato E essere il figlio sinistro di X .
  2. Mossa E è il sottoalbero giusto per X il sottoalbero sinistro.
  3. Aggiorna il genitore di X E E .
  4. Aggiornamento X il genitore da indicare E invece di X .
  5. Impostato E è il figlio giusto X .
  6. Aggiornamento X il genitore di E .

Pseudocodice di rotazione destra:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->Sinistra;  x->sinistra = y->destra;  if (y->destra != NIL) { y->destra->genitore = x;  } y->genitore = x->genitore;  if (x->parent == nullptr) { root = y;  } else if (x == x->genitore->destra) { x->genitore->destra = y;  } else { x->genitore->sinistra = y;  } y->destra = x;  x->genitore = y; }>

Quando eseguire le rotazioni?

Le rotazioni negli alberi rosso-neri vengono generalmente eseguite durante gli inserimenti e le eliminazioni per mantenere le proprietà dell'albero. Di seguito sono riportati gli scenari per le rotazioni:

1. Correzione delle violazioni dopo l'inserimento

Quando viene inserito un nuovo nodo, viene sempre colorato di rosso. Ciò può creare violazioni delle proprietà dell'albero rosso-nero, in particolare:

  • La radice deve essere nero .
  • Rosso i nodi non possono avere rosso bambini.

Analisi del caso per il fissaggio degli inserimenti:

  • Caso 1: Ricolorazione e propagazione verso l'alto
    • Se il genitore e lo zio del nuovo nodo sono entrambi rosso , ricolora il genitore e lo zio nero , e il nonno a rosso . Quindi, applicare in modo ricorsivo la correzione al nonno.
  • Caso 2: rotazione e ricolorazione
    • Se lo zio del nuovo nodo lo è nero e il nuovo nodo è il figlio destro di un figlio sinistro (o viceversa), esegui una rotazione per spostare il nuovo nodo verso l'alto e allinearlo.
    • Se lo zio del nuovo nodo lo è nero e il nuovo nodo è il figlio sinistro di un figlio sinistro (o destro di un figlio destro), esegui una rotazione e ricolora il genitore e il nonno per correggere la violazione.

2. Correzione delle violazioni dopo la cancellazione

Dopo l'eliminazione, potrebbe essere necessario correggere l'albero per ripristinare le proprietà:

  • Quando un nodo nero viene rimosso, o un nodo rosso viene sostituito da un nodo nero, può verificarsi una situazione di doppio nero.

Analisi del caso per correggere le eliminazioni:

quante città negli Stati Uniti
  • Caso 1: Il fratello è rosso
    • Ricolora il fratello e il genitore ed esegui una rotazione.
  • Caso 2: il fratello è nero con figli neri
    • Ricolora il fratello in rosso e sposta il problema al genitore.
  • Caso 3: Il fratello è nero con almeno un figlio rosso
    • Ruota e ricolora per risolvere il problema del doppio nero.

Implementazione dell'albero rosso-nero:

Ecco un'implementazione dettagliata di un albero rosso-nero che include funzioni di inserimento, ricerca e rotazione:

C++ 
#include  using namespace std; // Node structure for the Red-Black Tree struct Node {  int data;  string color;  Node *left, *right, *parent;  Node(int data)  : data(data)  , color('RED')  , left(nullptr)  , right(nullptr)  , parent(nullptr)  {  } }; // Red-Black Tree class class RedBlackTree { private:  Node* root;  Node* NIL;  // Utility function to perform left rotation  void leftRotate(Node* x)  {  Node* y = x->Giusto;  x->destra = y->sinistra;  if (y->sinistra != NIL) { y->sinistra->genitore = x;  } y->genitore = x->genitore;  if (x->parent == nullptr) { root = y;  } else if (x == x->genitore->sinistra) { x->genitore->sinistra = y;  } else { x->genitore->destra = y;  } y->sinistra = x;  x->genitore = y;  } // Funzione di utilità per eseguire la rotazione a destra void rightRotate(Node* x) { Node* y = x->left;  x->sinistra = y->destra;  if (y->destra != NIL) { y->destra->genitore = x;  } y->genitore = x->genitore;  if (x->parent == nullptr) { root = y;  } else if (x == x->genitore->destra) { x->genitore->destra = y;  } else { x->genitore->sinistra = y;  } y->destra = x;  x->genitore = y;  } // Funzione per correggere le proprietà dell'albero Rosso-Nero dopo // l'inserimento void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->genitore == k->genitore->genitore->sinistra) { Nodo* u = k->genitore->genitore->destra; // zio if (u->color == 'ROSSO') { k->parent->color = 'NERO';  u->colore = 'NERO';  k->genitore->genitore->colore = 'ROSSO';  k = k->genitore->genitore;  } else { if (k == k->genitore->destra) { k = k->genitore;  sinistraRuota(k);  } k->genitore->colore = 'NERO';  k->genitore->genitore->colore = 'ROSSO';  rightRutate(k->genitore->genitore);  } } else { Nodo* u = k->genitore->genitore->sinistra; // zio if (u->color == 'ROSSO') { k->parent->color = 'NERO';  u->colore = 'NERO';  k->genitore->genitore->colore = 'ROSSO';  k = k->genitore->genitore;  } else { if (k == k->genitore->sinistra) { k = k->genitore;  destraRuota(k);  } k->genitore->colore = 'NERO';  k->genitore->genitore->colore = 'ROSSO';  leftRutate(k->genitore->genitore);  } } } radice->colore = 'NERO';  } // Funzione di supporto per l'attraversamento in ordine void inorderHelper(Nodo* nodo) { if (nodo!= NIL) { inorderHelper(nodo->sinistra);  cout<< node->dati<< ' ';  inorderHelper(node->Giusto);  } } // Funzione di supporto alla ricerca Node* searchHelper(Node* node, int data) { if (node ​​== NIL || data == node->data) { return node;  } se (dati< node->dati) { return searchHelper(node->left, data);  } return searchHelper(nodo->destra, dati);  } public: // Costruttore RedBlackTree() { NIL = new Node(0);  NIL->colore = 'NERO';  NIL->sinistra = NIL->destra = NIL;  radice = NIL;  } // Inserisci la funzione void insert(int data) { Node* new_node = new Node(data);  nuovo_nodo->sinistra = NIL;  nuovo_nodo->destra = NIL;  Nodo* genitore = nullptr;  Nodo* corrente = radice;  // Inserimento BST while (corrente!= NIL) { genitore = corrente;  if (nuovo_nodo->data< current->dati) { corrente = corrente->sinistra;  } else { corrente = corrente->destra;  } } nuovo_nodo->genitore = genitore;  if (genitore == nullptr) { root = nuovo_nodo;  } altrimenti se (new_node->data< parent->dati) { genitore->sinistra = nuovo_nodo;  } else { genitore->destra = nuovo_nodo;  } if (nuovo_nodo->parent == nullptr) { nuovo_nodo->color = 'NERO';  ritorno;  } if (nuovo_nodo->parent->parent == nullptr) { return;  } fixInsert(nuovo_nodo);  } // Attraversamento in ordine void inorder() { inorderHelper(root); } // Funzione di ricerca Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Inserimento di elementi rbt.insert(10);  rbt.insert(20);  rbt.insert(30);  rbt.insert(15);  // Cout attraversamento in ordine<< 'Inorder traversal:' << endl;  rbt.inorder(); // Output: 10 15 20 30  // Search for a node  cout << '
Search for 15: '  << (rbt.search(15) != rbt.search(0))  << endl; // Output: 1 (true)  cout << 'Search for 25: '  << (rbt.search(25) != rbt.search(0))  << endl; // Output: 0 (false)  return 0; }>

Vantaggi degli alberi rosso-neri:

  • Equilibrato: Gli alberi rosso-neri sono autobilancianti, nel senso che mantengono automaticamente un equilibrio tra le altezze dei sottoalberi sinistro e destro. Ciò garantisce che le operazioni di ricerca, inserimento ed eliminazione richiedano tempo O (log n) nel caso peggiore.
  • Ricerca, inserimento ed eliminazione efficienti: Grazie alla loro struttura equilibrata, gli alberi rosso-neri offrono operazioni efficienti. La ricerca, l'inserimento e la cancellazione richiedono tutti il ​​tempo O (log n) nel caso peggiore.
  • Semplice da implementare: Le regole per il mantenimento delle proprietà dell'albero rosso-nero sono relativamente semplici e immediate da implementare.
  • Ampiamente usato: Gli alberi rosso-neri sono una scelta popolare per implementare varie strutture dati, come mappe, set e code di priorità.

Svantaggi degli alberi rosso-neri:

  • Più complesso di altri alberi equilibrati: Rispetto agli alberi bilanciati più semplici come gli alberi AVL, gli alberi rosso-neri hanno regole di inserimento ed eliminazione più complesse.
  • Spese generali costanti: Il mantenimento delle proprietà dell'albero rosso-nero aggiunge un piccolo sovraccarico a ogni operazione di inserimento ed eliminazione.
  • Non ottimale per tutti i casi d'uso: Sebbene efficienti per la maggior parte delle operazioni, gli alberi rosso-nero potrebbero non essere la scelta migliore per le applicazioni in cui sono richiesti inserimenti ed eliminazioni frequenti, poiché il sovraccarico costante può diventare significativo.

Applicazioni degli alberi rosso-neri:

  • Implementazione di mappe e set: Gli alberi rosso-neri vengono spesso utilizzati per implementare mappe e set, dove la ricerca, l'inserimento e l'eliminazione efficienti sono cruciali.
  • Code prioritarie: Gli alberi rosso-neri possono essere utilizzati per implementare code di priorità, in cui gli elementi sono ordinati in base alla loro priorità.
  • Sistemi di file: Gli alberi rosso-neri vengono utilizzati in alcuni file system per gestire strutture di file e directory.
  • Database in memoria: Gli alberi rosso-neri vengono talvolta utilizzati nei database in memoria per archiviare e recuperare i dati in modo efficiente.
  • Grafica e sviluppo del gioco: Gli alberi rosso-neri possono essere utilizzati nella grafica e nel gioco sviluppo per attività come il rilevamento delle collisioni e l'individuazione del percorso.

Domande frequenti (FAQ) sull'albero rosso-nero:

1. Cos'è un albero rosso-nero?

Un albero rosso-nero è un albero di ricerca binario autobilanciante che mantiene un equilibrio tra le altezze dei suoi sottoalberi sinistro e destro. Ciò garantisce che le operazioni di ricerca, inserimento ed eliminazione richiedano tempo O (log n) nel caso peggiore. Gli alberi rosso-neri sono ampiamente utilizzati in varie applicazioni in cui sono richieste strutture dati efficienti.

2. Come fa un albero rosso-nero a mantenere il suo equilibrio?

Gli alberi Rosso-Neri mantengono il loro equilibrio applicando regole specifiche sui colori dei nodi (ROSSO o NERO) e sulle relazioni tra loro. Queste regole assicurano che l'albero rimanga equilibrato e che la differenza di altezza tra i sottoalberi sinistro e destro sia al massimo 1.

3. Quali sono i vantaggi dell'utilizzo di un albero rosso-nero?

  • Equilibrato: Gli alberi Rosso-Nero sono autobilancianti, garantendo operazioni efficienti di ricerca, inserimento ed eliminazione.
  • Efficiente: Offrono una complessità temporale O(log n) per la maggior parte delle operazioni.
  • Semplice da implementare: Le regole per mantenere le proprietà dell'albero rosso-nero sono relativamente semplici.
  • Ampiamente usato: Sono una scelta popolare per implementare varie strutture dati e algoritmi.

4. Quali sono gli svantaggi dell'utilizzo di un albero rosso-nero?

  • Rispetto agli alberi bilanciati più semplici come gli alberi AVL, gli alberi rosso-neri hanno regole di inserimento ed eliminazione più complesse.
  • Il mantenimento delle proprietà dell'albero rosso-nero aggiunge un piccolo sovraccarico a ogni operazione di inserimento ed eliminazione.
  • Per applicazioni con inserimenti ed eliminazioni frequenti, altre strutture ad albero bilanciate potrebbero essere più adatte.

5. Quali sono alcune applicazioni comuni degli alberi rosso-neri?

  • Implementazione di mappe e set
  • Code prioritarie
  • File system
  • Database in memoria
  • Sviluppo grafica e giochi (rilevamento collisioni, pathfinding)
  • Definizione e significato dell'albero rosso-nero in DSA
  • Alberi di ricerca binari autobilancianti
  • Albero Rosso Nero vs Albero AVL
  • Qual è la differenza tra Heap e Albero rosso-nero?
  • Inserimento in albero rosso-nero
  • Cancellazione nell'albero rosso-nero
  • Alberi rosso-neri | Inserimento dall'alto verso il basso