logo

TechCodeview

Johdatus Red-Black Treeen

Binäärihakupuut ovat perustavanlaatuisia tietorakenne, mutta niiden suorituskyky voi kärsiä, jos puu muuttuu epätasapainoiseksi. Punaiset mustat puut ovat eräänlainen tasapainoinen binäärihakupuu jotka käyttävät sääntöjä tasapainon ylläpitämiseen ja varmistavat logaritmisen aikamonimutkaisuuden sellaisille toimille kuin lisääminen, poistaminen ja etsiminen , riippumatta puun alkuperäisestä muodosta. Punaiset mustat puut ovat itsetasapainottavia ja käyttävät yksinkertaista värikoodausta säätämään puuta jokaisen muokkauksen jälkeen.

Puna-musta puu



Sisällysluettelo

java värikoodit

Mikä on punamusta puu?

A Puna-musta puu on itsetasapainotus binäärihakupuu jossa jokaisella solmulla on lisäattribuutti: väri, joka voi olla jompikumpi punainen tai musta . Näiden puiden ensisijainen tavoite on säilyttää tasapaino lisäyksen ja poiston aikana, mikä varmistaa tehokkaan tiedonhaun ja käsittelyn.

Punamustien puiden ominaisuudet

A Puna-musta puu on seuraavat ominaisuudet:



  1. Solmun väri : Jokainen solmu on joko punainen tai musta .
  2. Pääomaisuus : Puun juuri on aina musta .
  3. Punainen omaisuus : Punaisilla solmuilla ei voi olla punaisia ​​lapsia (millään polulla ei ole kahta peräkkäistä punaista solmua).
  4. Musta omaisuus : Jokaisella polulla solmusta sen jälkeläisiin nollasolmuihin (lehtiin) on sama määrä musta solmut.
  5. Lehtiomaisuus : Kaikki lehdet (NIL-solmut) ovat musta .

Nämä ominaisuudet varmistavat, että pisin polku juuresta mihin tahansa lehtiin on enintään kaksi kertaa lyhin reitti, mikä säilyttää puun tasapainon ja tehokkaan suorituskyvyn.

Esimerkki punamusta puusta

The Oikea puna-musta puu yllä olevassa kuvassa varmistaa, että jokaisella polulla juuresta lehtisolmuun on sama määrä mustia solmuja. Tässä tapauksessa on yksi (pois lukien juurisolmu).



The Väärä punainen musta puu ei noudata puna-mustan ominaisuuksia kuin kaksi punaista solmua ovat vierekkäin. Toinen ongelma on, että yhdessä poluista lehtisolmuun ei ole mustaa solmua, kun taas kahdessa muussa on musta solmu.

Miksi puna-mustat puut?

Suurin osa BST-operaatioista (esim. haku, maksimi, min, lisää, poista jne.) kestää Vai niin) aika, jossa h on korkeus BST . Näiden toimintojen kustannukset voivat nousta Päällä) vinoon Binäärinen puu. Jos varmistamme, että puun korkeus säilyy O(log n) jokaisen lisäyksen ja poiston jälkeen voimme taata ylärajan O(log n) kaikkia näitä operaatioita varten. Punamustan puun korkeus on aina O(log n) missä n on puun solmujen lukumäärä.

Herra Ei.AlgoritmiAika monimutkaisuus
1.HaeO(log n)
2.LisääO(log n)
3.PoistaaO(log n)

Vertailu kanssa AVL puu :

AVL-puut ovat tasapainoisempia kuin puna-mustat puut, mutta ne voivat aiheuttaa enemmän kiertoja lisäyksen ja poistamisen aikana. Joten jos sovelluksesi sisältää toistuvia lisäyksiä ja poistoja, kannattaa suosia punamustaisia ​​puita. Ja jos lisäyksiä ja poistoja tehdään harvemmin ja haku on yleisempää, niin AVL puu tulisi olla parempana kuin punainen-musta puu.

Kuinka puna-musta puu varmistaa tasapainon?

Yksinkertainen esimerkki tasapainotuksen ymmärtämiseksi on, että 3 solmun ketju ei ole mahdollista puna-mustassa puussa. Voimme kokeilla mitä tahansa väriyhdistelmää ja katsoa, ​​rikkovatko ne kaikki puna-mustan puun ominaisuutta.

Kolmisolmuisen punamustan puun oikea rakenne

kevät s

Mielenkiintoisia kohtia Red-Black Tree -puusta:

  • The musta punamustan puun korkeus on mustien solmujen lukumäärä polulla juurisolmusta lehtisolmuun. Lehtisolmut lasketaan myös musta solmut. Eli punamusta korkea puu h on musta korkeus>= h/2 .
  • Punaisen mustan puun korkeus n solmut on h<= 2 log 2 (n + 1) .
  • Kaikki lehdet (NIL) ovat musta .
  • The musta solmun syvyys määritellään mustien solmujen lukumääränä juuresta kyseiseen solmuun eli mustien esi-isien lukumääräksi.

Puna-mustan puun perustoiminnot:

Punamustan puun perustoiminnot sisältävät:

  1. Lisäys
  2. Hae
  3. Poistaminen
  4. Kierto

1. Lisäys

Uuden solmun lisääminen punamustapuuhun sisältää kaksivaiheisen prosessin: standardin suorittamisen binäärihakupuun (BST) lisäys , minkä jälkeen korjataan mahdolliset puna-mustan ominaisuuksien rikkomukset.

Asennusvaiheet

  1. BST-lisäosa : Lisää uusi solmu kuten tavallisessa BST:ssä.
  2. Korjaa rikkomukset :
    • Jos uuden solmun emo on musta , mitään ominaisuuksia ei rikota.
    • Jos vanhempi on punainen , puu saattaa rikkoa punaista ominaisuutta, mikä vaatii korjauksia.

Rikkomusten korjaaminen lisäyksen aikana

Kun olet lisännyt uuden solmun a punainen solmu, voimme kohdata useita tapauksia solmun vanhemman ja sedän (vanhemman sisaruksen) väreistä riippuen:

  • Tapaus 1: Setä on punainen : Väritä vanhempi ja setä uudelleen musta , ja isovanhempi punainen . Siirry sitten ylös puuhun tarkistaaksesi lisärikkomukset.
  • Tapaus 2: Setä on musta :
    • Alatapaus 2.1: Node on oikea lapsi : Suorita vanhemman kierto vasemmalle.
    • Alatapaus 2.2: Node on vasen lapsi : Kierrä isovanhempaa oikealle ja värjätä uudelleen asianmukaisesti.

2. Haku

Solmun etsiminen punamustasta puusta on samanlaista kuin standardista etsiminen Binäärihakupuu (BST) . Hakutoiminto seuraa suoraa polkua kohteesta juuri kohtaan a puun lehti , vertaamalla tavoitearvoa nykyisen solmun arvoon ja siirtymällä vasemmalle tai oikealle vastaavasti.

Hakuvaiheet

  1. Aloita juuresta : Aloita haku juurisolmusta.
  2. Kulje puun läpi :
    • Jos tavoitearvo on yhtä suuri kuin nykyisen solmun arvo, solmu löytyy.
    • Jos tavoitearvo on pienempi kuin nykyisen solmun arvo, siirry vasempaan alatasoon.
    • Jos tavoitearvo on suurempi kuin nykyisen solmun arvo, siirry oikean alatason kohdalle.
  3. Toistaa : Jatka tätä prosessia, kunnes tavoitearvo löytyy tai NIL-solmu saavutetaan (osoittaa, että arvoa ei ole puussa).

3. Poistaminen

Solmun poistaminen punamustapuusta sisältää myös kaksivaiheisen prosessin: BST-poiston suorittamisen, minkä jälkeen mahdolliset rikkomukset korjataan.

Poistovaiheet

  1. BST-poisto : Poista solmu käyttämällä tavallisia BST-sääntöjä.
  2. Korjaa Double Black :
    • Jos musta solmu poistetaan, voi syntyä kaksoismusta tila, joka vaatii erityisiä korjauksia.

Rikkomusten korjaaminen poistamisen aikana

Kun musta solmu poistetaan, käsittelemme kaksoismustan ongelman sisaruksen värin ja sen lasten värien perusteella:

  • Tapaus 1: Sisarus on punainen : Pyöritä vanhempia ja väritä sisarus ja vanhempi uudelleen.
  • Tapaus 2: Sisarus on musta :
    • Alatapaus 2.1: Sisarusten lapset ovat mustia : Väritä sisarus uudelleen ja levitä kaksoismusta ylöspäin.
    • Alatapaus 2.2: Ainakin yksi sisaruksen lapsista on punainen :
      • Jos sisaruksen kaukainen lapsi on punainen : Pyöritä vanhempaa ja sisarusta ja väritä uudelleen asianmukaisesti.
      • Jos sisaruksen lähellä oleva lapsi on punainen : Pyöritä sisarusta ja sen lasta ja käsittele sitten kuten yllä.

4. Kierto

Rotaatiot ovat perustavanlaatuisia toimintoja punamustan puun (RBT) tasapainoisen rakenteen ylläpitämisessä. Ne auttavat säilyttämään puun ominaisuudet varmistaen, että pisin polku juuresta mihin tahansa lehtiin on enintään kaksi kertaa lyhimmän polun pituus. Pyörityksiä on kahta tyyppiä: kierrokset vasemmalle ja oikeat kierrokset.

1. Kierto vasemmalle

Kierto vasemmalle solmussa 𝑥 x liikkuu 𝑥 x alas vasemmalle ja sen oikealle lapselle 𝑦 ja ottamaan 𝑥 x paikan.

Vasemman kierron visualisointi 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Kierto vasemmalle:

  1. Aseta ja olla oikea lapsi x .
  2. Liikkua ja 's vasemmalle alipuulle x oikea alipuu.
  3. Päivitä käyttäjän vanhempi x ja ja .
  4. Päivittää x vanhempi, johon osoitat ja sijasta x .
  5. Aseta ja on jättänyt lapsen x .
  6. Päivittää x vanhemmalle ja .

Vasemman kierron pseudokoodi:

Kierto vasemmalle 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->oikea;  x->oikea = y->vasen;  if (y->vasen != NIL) { y->vasen->emo = x;  } y->vanhempi = x->vanhempi;  if (x->parent == nullptr) { juuri = y;  } else if (x == x->vanhempi->vasen) { x->vanhempi->vasen = y;  } else { x->vanhempi->oikea = y;  } y->vasen = x;  x->vanhempi = y; }>

2. Oikea kierto

Oikea kierto solmupisteessä 𝑥 x liikkuu 𝑥 x alas oikealle ja sen vasen lapsi 𝑦 ja ottamaan 𝑥 x paikan.

Oikean kierron visualisointi: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Oikean pyörityksen vaiheet:

  1. Aseta ja olla vasen lapsi x .
  2. Liikkua ja oikea alipuu x vasen alipuu.
  3. Päivitä käyttäjän vanhempi x ja ja .
  4. Päivittää x vanhempi, johon osoitat ja sijasta x .
  5. Aseta ja oikea lapsi x .
  6. Päivittää x vanhemmalle ja .

Oikean kierron pseudokoodi:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->vasemmalle;  x->vasen = y->oikea;  if (y->oikea != NIL) { y->oikea->emo = x;  } y->vanhempi = x->vanhempi;  if (x->parent == nullptr) { juuri = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->vanhempi->vasen = y;  } y->oikea = x;  x->vanhempi = y; }>

Milloin kierrokset suoritetaan?

Rotaatiot puna-mustissa puissa suoritetaan tyypillisesti lisäysten ja poistojen aikana puun ominaisuuksien säilyttämiseksi. Alla on kiertojen skenaariot:

1. Rikkomusten korjaaminen lisäyksen jälkeen

Kun uusi solmu lisätään, se väritetään aina punaiseksi. Tämä voi aiheuttaa Red-Black Tree -ominaisuuksien rikkomuksia, erityisesti:

  • Juuren tulee olla musta .
  • Punainen solmuilla ei voi olla punainen lapset.

Tapausanalyysi lisäysten korjaamiseksi:

  • Tapaus 1: Uudelleenvärjäys ja leviäminen ylöspäin
    • Jos uuden solmun vanhempi ja setä ovat molemmat punainen , väritä vanhempi ja setä uudelleen musta , ja isovanhempi punainen . Käytä sitten korjausta rekursiivisesti isovanhempiin.
  • Tapaus 2: Kierto ja väritys
    • Jos uuden solmun setä on musta ja uusi solmu on vasemman lapsen oikea lapsi (tai päinvastoin), suorita kierto siirtääksesi uutta solmua ylöspäin ja kohdistaaksesi sen.
    • Jos uuden solmun setä on musta ja uusi solmu on vasemman lapsen vasen lapsi (tai oikeanpuoleinen), suorita kierto ja väritä uudelleen vanhempi ja isovanhempi rikkomuksen korjaamiseksi.

2. Rikkomusten korjaaminen poistamisen jälkeen

Poistamisen jälkeen puu saattaa joutua korjaamaan ominaisuuksien palauttamiseksi:

  • Kun musta solmu poistetaan tai punainen solmu korvataan mustalla solmulla, voi syntyä kaksoismusta -tilanne.

Tapausanalyysi poistojen korjaamiseksi:

  • Tapaus 1: Sisarus on punainen
    • Väritä sisarus ja vanhempi uudelleen ja suorita kierto.
  • Tapaus 2: Sisarus on musta ja hänellä on mustia lapsia
    • Väritä sisarus uudelleen punaiseksi ja siirrä ongelma vanhemmalle.
  • Tapaus 3: Sisarus on musta, ja hänellä on vähintään yksi punainen lapsi
    • Korjaa kaksoismustan ongelma kiertämällä ja värjäämällä.

Red-Black Treen toteutus:

Tässä on punamustapuun yksityiskohtainen toteutus, mukaan lukien lisäys-, haku- ja kiertotoiminnot:

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->oikea;  x->oikea = y->vasen;  if (y->vasen != NIL) { y->vasen->emo = x;  } y->vanhempi = x->vanhempi;  if (x->parent == nullptr) { juuri = y;  } else if (x == x->vanhempi->vasen) { x->vanhempi->vasen = y;  } else { x->vanhempi->oikea = y;  } y->vasen = x;  x->vanhempi = y;  } // Aputoiminto oikealle kiertoon void rightRotate(Solmu* x) { Solmu* y = x->vasen;  x->vasen = y->oikea;  if (y->oikea != NIL) { y->oikea->emo = x;  } y->vanhempi = x->vanhempi;  if (x->parent == nullptr) { juuri = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->vanhempi->vasen = y;  } y->oikea = x;  x->vanhempi = y;  } // Funktio, joka korjaa puna-mustan puun ominaisuudet // lisäyksen jälkeen void fixInsert(Node* k) { while (k != juuri && k->parent->color == 'RED') { if (k->vanhempi == k->vanhempi->vanhempi->vasen) { Solmu* u = k->vanhempi->vanhempi->oikea; // setä if (u->väri == 'PUNAINEN') { k->vanhempi->väri = 'MUSTA';  u->väri = 'MUSTA';  k->vanhempi->vanhempi->väri = 'PUNAINEN';  k = k->vanhempi->vanhempi;  } else { if (k == k->vanhempi->oikea) { k = k->vanhempi;  vasemmalleKierrä(k);  } k->parent->color = 'MUSTA';  k->vanhempi->vanhempi->väri = 'PUNAINEN';  rightRotate(k->vanhempi->vanhempi);  } } else { Solmu* u = k->vanhempi->vanhempi->vasen; // setä if (u->väri == 'PUNAINEN') { k->vanhempi->väri = 'MUSTA';  u->väri = 'MUSTA';  k->vanhempi->vanhempi->väri = 'PUNAINEN';  k = k->vanhempi->vanhempi;  } else { if (k == k->vanhempi->vasen) { k = k->vanhempi;  oikealleKierrä(k);  } k->parent->color = 'MUSTA';  k->vanhempi->parent->väri = 'PUNAINEN';  leftRotate(k->vanhempi->vanhempi);  } } } juuri->väri = 'MUSTA';  } // Inorder traversal helper function void inorderHelper(Solmu* solmu) { if (solmu != NIL) { inorderHelper(solmu->vasen);  cout<< node->tiedot<< ' ';  inorderHelper(node->oikea);  } } // Etsi aputoiminto Node* searchHelper(Solmu* solmu, int data) { if (solmu == NIL || data == solmu->data) { return node;  } jos (data< node->data) { return searchHelper(solmu->vasen, data);  } return searchHelper(solmu->oikea, data);  } public: // Rakentaja RedBlackTree() { NIL = uusi solmu(0);  NIL->väri = 'MUSTA';  NIL->vasen = NIL->oikea = NIL;  juuri = NIL;  } // Lisää funktio void insert(int data) { Node* new_node = new Node(data);  uusi_solmu->vasen = NIL;  uusi_solmu->oikea = NIL;  Solmu* vanhempi = nullptr;  Solmu* virta = juuri;  // BST lisää while (nykyinen != NIL) { vanhempi = nykyinen;  if (uusi_solmu->data< current->data) { nykyinen = nykyinen->vasen;  } else { nykyinen = nykyinen->oikea;  } } new_node->parent = vanhempi;  if (emo == nullptr) { juuri = uusi_solmu;  } else if (uusi_solmu->tiedot< parent->data) { vanhempi->vasen = uusi_solmu;  } else { vanhempi->oikea = uusi_solmu;  } if (uusi_solmu->parent == nullptr) { uusi_solmu->väri = 'MUSTA';  palata;  } if (uusi_solmu->parent->parent == nullptr) { return;  } fixInsert(uusi_solmu);  } // Inorder traversal void inorder() { inorderHelper(root); } // Hakutoiminto Solmu* haku(int data) { return searchHelper(juuri, data);  } }; int main() { RedBlackTree rbt;  // Elementtien lisääminen rbt.insert(10);  rbt.insert(20);  rbt.insert(30);  rbt.insert(15);  // Inorder traversal cout<< '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; }>

Punamustien puiden edut:

  • Tasapainotettu: Red-Black Trees ovat itsetasapainoittavia, mikä tarkoittaa, että ne ylläpitävät automaattisesti tasapainoa vasemman ja oikean alipuiden korkeuksien välillä. Tämä varmistaa, että haku-, lisäys- ja poistotoiminnot vievät O(log n) aikaa pahimmassa tapauksessa.
  • Tehokas haku, lisääminen ja poistaminen: Tasapainoisen rakenteensa ansiosta Red-Black Trees tarjoaa tehokkaan toiminnan. Haku, lisääminen ja poistaminen vie O(log n) aikaa pahimmassa tapauksessa.
  • Yksinkertainen toteuttaa: Red-Black Tree -kiinteistöjen ylläpitosäännöt ovat suhteellisen yksinkertaisia ​​ja yksinkertaisia ​​toteuttaa.
  • Laajasti käytetty: Punamustat puut ovat suosittu valinta erilaisten tietorakenteiden, kuten karttojen, joukkojen ja prioriteettijonojen, toteuttamiseen.

Punamustien puiden haitat:

  • Monimutkaisempi kuin muut tasapainoiset puut: Verrattuna yksinkertaisempiin tasapainotettuihin puihin, kuten AVL-puihin, punamustilla puilla on monimutkaisemmat lisäys- ja poistosäännöt.
  • Jatkuvat yleiskulut: Puna-mustan puun ominaisuuksien ylläpitäminen lisää pienen lisäkulun jokaiseen lisäys- ja poistotoimintoon.
  • Ei optimaalinen kaikkiin käyttötapauksiin: Vaikka Red-Black Trees on tehokas useimpiin toimintoihin, se ei ehkä ole paras valinta sovelluksiin, joissa vaaditaan toistuvia lisäyksiä ja poistoja, koska jatkuvasta ylikuormituksesta voi tulla merkittävää.

Punamustien puiden sovellukset:

  • Karttojen ja sarjojen toteutus: Punamustia puita käytetään usein karttojen ja sarjojen toteuttamiseen, missä tehokas haku, lisääminen ja poistaminen ovat ratkaisevan tärkeitä.
  • Prioriteettijonot: Red-Black Trees -puiden avulla voidaan toteuttaa prioriteettijonoja, joissa elementit järjestetään niiden prioriteetin mukaan.
  • Tiedostojärjestelmät: Punamustia puita käytetään joissakin tiedostojärjestelmissä tiedosto- ja hakemistorakenteiden hallintaan.
  • Muistissa olevat tietokannat: Red-Black Trees -puita käytetään joskus muistin sisäisissä tietokannoissa tietojen tallentamiseen ja hakemiseen tehokkaasti.
  • Grafiikka ja pelien kehitys: Red-Black Trees -puita voidaan käyttää grafiikassa ja peleissä kehitystä tehtäviin, kuten törmäysten havaitsemiseen ja polunhakuun.

Usein kysytyt kysymykset (FAQ) Red-Black Tree:ssä:

1. Mikä on punamusta puu?

Punamusta puu on itsetasapainottava binäärihakupuu, joka ylläpitää tasapainoa vasemman ja oikean alipuun korkeuksien välillä. Tämä varmistaa, että haku-, lisäys- ja poistotoiminnot vievät O(log n) aikaa pahimmassa tapauksessa. Red-Black Trees -puita käytetään laajalti erilaisissa sovelluksissa, joissa tarvitaan tehokkaita tietorakenteita.

2. Miten puna-musta puu säilyttää tasapainonsa?

Puna-mustat puut säilyttävät tasapainonsa noudattamalla erityisiä sääntöjä solmujen väreistä (PUNAINEN tai MUSTA) ja niiden välisistä suhteista. Nämä säännöt varmistavat, että puu pysyy tasapainossa ja että vasemman ja oikean alipuun välinen korkeusero on enintään 1.

heittää merkkijono int javaan

3. Mitä etuja on punamustapuun käyttämisestä?

  • Tasapainotettu: Red-Black Trees tasapainottavat itsensä ja varmistavat tehokkaat haku-, lisäys- ja poistotoiminnot.
  • Tehokas: Ne tarjoavat O(log n) -ajan monimutkaisuuden useimmille toiminnoille.
  • Yksinkertainen toteuttaa: Red-Black Tree -kiinteistöjen ylläpitosäännöt ovat suhteellisen yksinkertaiset.
  • Laajasti käytetty: Ne ovat suosittu valinta erilaisten tietorakenteiden ja algoritmien toteuttamiseen.

4. Mitkä ovat punamustapuun käytön haitat?

  • Verrattuna yksinkertaisempiin tasapainotettuihin puihin, kuten AVL-puihin, punamustilla puilla on monimutkaisemmat lisäys- ja poistosäännöt.
  • Puna-mustan puun ominaisuuksien ylläpitäminen lisää pienen lisäkulun jokaiseen lisäys- ja poistotoimintoon.
  • Toistuvia lisäyksiä ja poistoja sisältäviin sovelluksiin muut tasapainotetut puurakenteet saattavat olla sopivampia.

5. Mitkä ovat punamustapuiden yleisiä sovelluksia?

  • Karttojen ja sarjojen toteuttaminen
  • Prioriteettijonot
  • Tiedostojärjestelmät
  • Muistissa olevat tietokannat
  • Grafiikka ja pelien kehitys (törmäysten havaitseminen, polun etsintä)
  • Puna-mustan puun määritelmä ja merkitys DSA:ssa
  • Itsetasapainottavat binaarihakupuut
  • Red Black Tree vs AVL Tree
  • Mitä eroa on kasalla ja punamustalla puulla?
  • Lisäys punamustapuuhun
  • Poisto punamustassa puussa
  • Punamustat puut | Ylhäältä alas -lisäys