logo

TechCodeview

Introduktion till röd-svart träd

Binära sökträd är en grundläggande datastruktur, men deras prestanda kan bli lidande om trädet blir obalanserat. Röda svarta träd är en typ av balanserat binärt sökträd som använder en uppsättning regler för att upprätthålla balans, vilket säkerställer logaritmisk tidskomplexitet för operationer som infogning, radering och sökning , oavsett trädets ursprungliga form. Röda svarta träd är självbalanserande och använder ett enkelt färgkodningsschema för att justera trädet efter varje modifiering.

Röd-svart träd

Innehållsförteckning



Vad är ett röd-svart träd?

A Röd-svart träd är en självbalansering binärt sökträd där varje nod har ett extra attribut: en färg, som kan vara antingen röd eller svart . Det primära syftet med dessa träd är att upprätthålla balans under insättningar och borttagningar, vilket säkerställer effektiv datahämtning och manipulering.

Egenskaper hos röd-svarta träd

A Röd-svart träd har följande egenskaper:

  1. Nodfärg : Varje nod är antingen röd eller svart .
  2. Root Property : Trädets rot är alltid svart .
  3. Röd egendom : Röda noder kan inte ha röda barn (inga två på varandra följande röda noder på någon väg).
  4. Svart egendom : Varje väg från en nod till dess efterkommande nollnoder (löv) har samma antal svart knutpunkter.
  5. Leaf Property : Alla blad (NIL-noder) är svart .

Dessa egenskaper säkerställer att den längsta vägen från roten till något löv inte är mer än dubbelt så lång som den kortaste vägen, vilket bibehåller trädets balans och effektiva prestanda.

Exempel på röd-svart träd

De Rätt röd-svart träd i bilden ovan säkerställer att varje väg från roten till en lövnod har samma antal svarta noder. I det här fallet finns det en (exklusive rotnoden).

De Felaktigt rött svart träd följer inte de röd-svarta egenskaperna som två röda noder ligger intill varandra. Ett annat problem är att en av vägarna till en lövnod har noll svarta noder, medan de andra två innehåller en svart nod.

Varför röd-svarta träd?

De flesta av BST-operationerna (t.ex. sökning, max, min, infoga, ta bort... etc) tar Åh) tid där h är höjden på BST . Kostnaden för dessa operationer kan bli På) för en skev Binärt träd. Om vi ​​ser till att höjden på trädet finns kvar O(log n) efter varje infogning och borttagning, då kan vi garantera en övre gräns för O(log n) för alla dessa operationer. Höjden på ett röd-svart träd är alltid O(log n) där n är antalet noder i trädet.

Mr. Nej.AlgoritmTidskomplexitet
1.SökO(log n)
2.Föra inO(log n)
3.RaderaO(log n)

I jämförelse med AVL-träd :

AVL-träden är mer balanserade jämfört med röd-svarta träd, men de kan orsaka fler rotationer under insättning och radering. Så om din applikation involverar frekventa insättningar och raderingar, bör röd-svarta träd föredras. Och om infogning och radering är mindre frekvent och sökning är en mer frekvent operation, då AVL-träd bör föredras framför det röd-svarta trädet.

Hur säkerställer ett röd-svart träd balans?

Ett enkelt exempel för att förstå balansering är att en kedja av 3 noder inte är möjlig i det röd-svarta trädet. Vi kan prova vilken kombination av färger som helst och se om alla bryter mot egenskapen Red-Black tree.

heltal till dubbel java

Korrekt struktur av tre node röd-svart träd

Intressanta punkter om Red-Black Tree:

  • De svart höjden på det röd-svarta trädet är antalet svarta noder på en väg från rotnoden till en lövnod. Lövnoder räknas också som svart knutpunkter. Alltså, ett rödsvart träd av höjd h har svart höjd>= h/2 .
  • Höjd på ett röd-svart träd med n noder är h<= 2 log 2 (n + 1) .
  • Alla blad (NIL) är svart .
  • De svart djup av en nod definieras som antalet svarta noder från roten till den noden, dvs antalet svarta förfäder.

Grundläggande funktioner på röd-svart träd:

De grundläggande operationerna på ett röd-svart träd inkluderar:

  1. Införande
  2. Sök
  3. Radering
  4. Rotation

1. Införande

Att infoga en ny nod i ett röd-svart träd innebär en tvåstegsprocess: att utföra en standard insättning av binärt sökträd (BST). , följt av att åtgärda eventuella överträdelser av röd-svart egenskaper.

Insättningssteg

  1. BST Insert : Infoga den nya noden som i en standard BST.
  2. Åtgärda överträdelser :
    • Om föräldern till den nya noden är svart , inga egenskaper kränks.
    • Om föräldern är röd , kan trädet bryta mot den röda egenskapen, vilket kräver korrigeringar.

Åtgärda överträdelser under insättning

Efter att ha infogat den nya noden som en röd nod, kan vi stöta på flera fall beroende på färgerna på nodens förälder och farbror (förälderns syskon):

  • Fall 1: Farbror är röd : Färga om föräldern och farbrorn till svart , och morföräldern till röd . Flytta sedan upp i trädet för att se efter ytterligare överträdelser.
  • Fall 2: Farbror är svart :
    • Underfall 2.1: Node är ett rätt barn : Utför en vänsterrotation på föräldern.
    • Underfall 2.2: Noden är ett vänsterbarn : Utför en högerrotation på morföräldern och färga om på lämpligt sätt.

2. Sökning

Att söka efter en nod i ett röd-svart träd liknar att söka i en standard Binärt sökträd (BST) . Sökoperationen följer en enkel väg från rot till a blad , jämföra målvärdet med den aktuella nodens värde och flytta åt vänster eller höger i enlighet med detta.

Söksteg

  1. Börja vid roten : Börja sökningen vid rotnoden.
  2. Gå igenom trädet :
    • Om målvärdet är lika med den aktuella nodens värde hittas noden.
    • Om målvärdet är mindre än den aktuella nodens värde, flytta till vänster underordnad.
    • Om målvärdet är större än den aktuella nodens värde, flytta till rätt underordnad.
  3. Upprepa : Fortsätt denna process tills målvärdet hittas eller en NIL-nod nås (vilket indikerar att värdet inte finns i trädet).

3. Radering

Att ta bort en nod från ett röd-svart träd innebär också en tvåstegsprocess: att utföra BST-borttagningen, följt av att åtgärda eventuella överträdelser som uppstår.

Raderingssteg

  1. BST radering : Ta bort noden med standard BST-regler.
  2. Fixa dubbelsvart :
    • Om en svart nod tas bort kan ett dubbelsvart tillstånd uppstå, vilket kräver specifika korrigeringar.

Åtgärda överträdelser under radering

När en svart nod tas bort hanterar vi problemet med dubbelsvart baserat på syskonens färg och färgerna på dess barn:

  • Fall 1: Syskon är rött : Rotera föräldern och färga om syskon och förälder.
  • Fall 2: Syskon är svart :
    • Underfall 2.1: Syskons barn är svarta : Färga om syskonet och föröka det dubbla svarta uppåt.
    • Underfall 2.2: Minst ett av syskonens barn är rött :
      • Om syskons bortre barn är rött : Utför en rotation på föräldern och syskon, och färga om på lämpligt sätt.
      • Om syskons närmaste barn är rött : Rotera syskon och dess barn, hantera sedan enligt ovan.

4. Rotation

Rotationer är grundläggande operationer för att upprätthålla den balanserade strukturen hos ett röd-svart träd (RBT). De hjälper till att bevara trädets egenskaper och säkerställer att den längsta vägen från roten till något löv inte är mer än dubbelt så lång som den kortaste vägen. Rotationer finns i två typer: vänsterrotationer och högerrotationer.

1. Vänsterrotation

En vänsterrotation vid noden 𝑥 x rör sig 𝑥 x ner till vänster och dess högra barn 𝑦 och upp att ta 𝑥 x s plats.

Visualisering av Left Roation 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Vänsterrotationssteg:

  1. Uppsättning och att vara rätt barn till x .
  2. Flytta och s vänstra underträd till x högra underträdet.
  3. Uppdatera föräldern till x och och .
  4. Uppdatering x sin förälder att peka på och istället för x .
  5. Uppsättning och lämnade barnet till x .
  6. Uppdatering x sin förälder till och .

Pseudokod för vänsterrotation:

Vänsterrotation 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->höger;  x->höger = y->vänster;  if (y->vänster != NIL) { y->vänster->förälder = x;  } y->förälder = x->förälder;  if (x->parent == nullptr) { rot = y;  } annat om (x == x->förälder->vänster) { x->förälder->vänster = y;  } annat { x->förälder->höger = y;  } y->vänster = x;  x->förälder = y; }>

2. Högerrotation

En högerrotation vid noden 𝑥 x rör sig 𝑥 x ner till höger och dess vänstra barn 𝑦 och upp att ta 𝑥 x s plats.

Visualisering av högerrotation: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Höger rotationssteg:

  1. Uppsättning och att vara vänster barn till x .
  2. Flytta och s högra underträd till x s vänstra underträd.
  3. Uppdatera föräldern till x och och .
  4. Uppdatering x sin förälder att peka på och istället för x .
  5. Uppsättning och rätt barn till x .
  6. Uppdatering x sin förälder till och .

Pseudokod för högerrotation:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->vänster;  x->vänster = y->höger;  if (y->right != NIL) { y->right->parent = x;  } y->förälder = x->förälder;  if (x->parent == nullptr) { rot = y;  } annat om (x == x->förälder->höger) { x->förälder->höger = y;  } annat { x->förälder->vänster = y;  } y->höger = x;  x->förälder = y; }>

När ska man utföra rotationer?

Rotationer i röd-svarta träd utförs vanligtvis under insättningar och borttagningar för att bibehålla trädets egenskaper. Nedan är scenarierna för rotationer:

1. Åtgärda överträdelser efter insättning

När en ny nod infogas färgas den alltid röd. Detta kan skapa överträdelser av Red-Black Tree-egenskaper, specifikt:

  • Roten måste vara svart .
  • Röd noder inte kan ha röd barn.

Fallanalys för fixering av insättningar:

  • Fall 1: Omfärgning och förökning uppåt
    • Om föräldern och farbrorn till den nya noden är båda röd , färga om föräldern och farbrorn till svart , och morföräldern till röd . Applicera sedan korrigeringen rekursivt på morföräldern.
  • Fall 2: Rotation och omfärgning
    • Om den nya nodens farbror är svart och den nya noden är det högra barnet till ett vänster barn (eller vice versa), utför en rotation för att flytta upp den nya noden och justera den.
    • Om den nya nodens farbror är svart och den nya noden är det vänstra barnet till ett vänster barn (eller höger om ett höger), utför en rotation och färga om föräldern och farföräldern för att åtgärda överträdelsen.

2. Åtgärda överträdelser efter radering

Efter borttagning kan trädet behöva fixas för att återställa egenskaper:

  • När en svart nod tas bort, eller en röd nod ersätts med en svart nod, kan en dubbelsvart situation uppstå.

Fallanalys för att åtgärda borttagningar:

  • Fall 1: Syskon är rött
    • Färglägg om syskon och förälder och utför en rotation.
  • Fall 2: Syskon är svart med svarta barn
    • Färga om syskonet till rött och flytta upp problemet till föräldern.
  • Fall 3: Syskon är svart med minst ett rött barn
    • Rotera och färglägg om för att lösa problemet med dubbelsvart.

Implementering av Red-Black Tree:

Här är en detaljerad implementering av ett röd-svart träd inklusive infognings-, sök- och rotationsfunktioner:

java lokal datumtid
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->höger;  x->höger = y->vänster;  if (y->vänster != NIL) { y->vänster->förälder = x;  } y->förälder = x->förälder;  if (x->parent == nullptr) { rot = y;  } annat om (x == x->förälder->vänster) { x->förälder->vänster = y;  } annat { x->förälder->höger = y;  } y->vänster = x;  x->förälder = y;  } // Verktygsfunktion för att utföra högerrotation void rightRotate(Node* x) { Node* y = x->left;  x->vänster = y->höger;  if (y->right != NIL) { y->right->parent = x;  } y->förälder = x->förälder;  if (x->parent == nullptr) { rot = y;  } annat om (x == x->förälder->höger) { x->förälder->höger = y;  } annat { x->förälder->vänster = y;  } y->höger = x;  x->förälder = y;  } // Funktion för att fixa Red-Black Tree-egenskaper efter // insertion void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->förälder == k->förälder->förälder->vänster) { Node* u = k->förälder->förälder->höger; // farbror om (u->färg == 'RED') { k->förälder->färg = 'SVART';  u->färg = 'SVART';  k->förälder->förälder->färg = 'RED';  k = k->förälder->förälder;  } else { if (k == k->förälder->höger) { k = k->förälder;  vänsterRotera(k);  } k->förälder->färg = 'SVART';  k->förälder->förälder->färg = 'RED';  rightRotate(k->förälder->förälder);  } } else { Node* u = k->förälder->förälder->vänster; // farbror if (u->färg == 'RED') { k->förälder->färg = 'SVART';  u->färg = 'SVART';  k->förälder->förälder->färg = 'RED';  k = k->förälder->förälder;  } else { if (k == k->förälder->vänster) { k = k->förälder;  högerRotera(k);  } k->förälder->färg = 'SVART';  k->förälder->förälder->färg = 'RED';  leftRotate(k->förälder->förälder);  } } } root->color = 'SVART';  } // Inorder traversal helper function void inorderHelper(Node* node) { if (nod != NIL) { inorderHelper(nod->vänster);  cout<< node->data<< ' ';  inorderHelper(node->höger);  } } // Sök hjälpfunktion Node* searchHelper(Node* nod, int data) { if (nod == NIL || data == nod->data) { return node;  } if (data< node->data) { return searchHelper(nod->vänster, data);  } return searchHelper(nod->höger, data);  } public: // Constructor RedBlackTree() { NIL = new Node(0);  NIL->färg = 'SVART';  NIL->vänster = NIL->höger = NIL;  rot = NIL;  } // Insert function void insert(int data) { Node* new_node = new Node(data);  new_node->left = NIL;  new_node->right = NIL;  Nod* förälder = nullptr;  Nod* ström = rot;  // BST insert while (current != NIL) { parent = current;  if (ny_nod->data< current->data) { aktuell = aktuell->vänster;  } annat { aktuell = aktuell->höger;  } } new_node->förälder = förälder;  if (förälder == nullptr) { rot = ny_nod;  } annat om (new_node->data< parent->data) { parent->left = new_node;  } else { parent->right = new_node;  } if (new_node->parent == nullptr) { new_node->color = 'SVART';  lämna tillbaka;  } if (new_node->parent->parent == nullptr) { return;  } fixInsert(ny_nod);  } // Inorder traversal void inorder() { inorderHelper(root); } // Sökfunktion Nod* sök(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Infoga element 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; }>

Fördelar med röd-svarta träd:

  • Balanserad: Röd-svarta träd är självbalanserande, vilket innebär att de automatiskt upprätthåller en balans mellan höjderna på vänster och höger underträd. Detta säkerställer att sökning, infogning och radering tar O(log n) tid i värsta fall.
  • Effektiv sökning, infogning och radering: Tack vare sin balanserade struktur erbjuder Red-Black Trees effektiv drift. Sökning, infogning och radering tar alla O(log n) tid i värsta fall.
  • Enkel att implementera: Reglerna för att underhålla Red-Black Tree-egenskaperna är relativt enkla och okomplicerade att implementera.
  • Används i stor utsträckning: Röd-svarta träd är ett populärt val för att implementera olika datastrukturer, såsom kartor, uppsättningar och prioriterade köer.

Nackdelar med röd-svarta träd:

  • Mer komplexa än andra balanserade träd: Jämfört med enklare balanserade träd som AVL-träd har rödsvarta träd mer komplexa regler för insättning och borttagning.
  • Konstant overhead: Att bibehålla egenskaperna för röd-svart träd lägger till en liten overhead till varje insättnings- och raderingsoperation.
  • Inte optimalt för alla användningsfall: Även om det är effektivt för de flesta operationer, är Red-Black Trees kanske inte det bästa valet för applikationer där frekventa insättningar och raderingar krävs, eftersom den konstanta omkostnaden kan bli betydande.

Tillämpningar av röd-svarta träd:

  • Implementera kartor och uppsättningar: Röd-svarta träd används ofta för att implementera kartor och uppsättningar, där effektiv sökning, infogning och radering är avgörande.
  • Prioriterade köer: Röd-svarta träd kan användas för att implementera prioritetsköer, där element ordnas baserat på deras prioritet.
  • Filsystem: Röd-svarta träd används i vissa filsystem för att hantera fil- och katalogstrukturer.
  • Databaser i minnet: Röd-svarta träd används ibland i minnesdatabaser för att lagra och hämta data effektivt.
  • Grafik och spelutveckling: Röd-svarta träd kan användas i grafik och spel utveckling för uppgifter som kollisionsdetektering och sökväg.

Vanliga frågor (FAQs) om röd-svart träd:

1. Vad är ett röd-svart träd?

Ett rött-svart träd är ett självbalanserande binärt sökträd som upprätthåller en balans mellan höjderna på dess vänstra och högra underträd. Detta säkerställer att sökning, infogning och radering tar O(log n) tid i värsta fall. Röd-svarta träd används ofta i olika applikationer där effektiva datastrukturer krävs.

2. Hur bibehåller ett röd-svart träd sin balans?

Röd-svarta träd upprätthåller sin balans genom att upprätthålla specifika regler för färgerna på noderna (RÖDA eller SVARTA) och relationerna mellan dem. Dessa regler säkerställer att trädet förblir balanserat och att höjdskillnaden mellan vänster och höger underträd är högst 1.

3. Vilka är fördelarna med att använda ett röd-svart träd?

  • Balanserad: Röd-svarta träd är självbalanserande, vilket säkerställer effektiv sökning, infogning och radering.
  • Effektiv: De erbjuder O(log n) tidskomplexitet för de flesta operationer.
  • Enkel att implementera: Reglerna för att underhålla Red-Black Tree-egenskaper är relativt enkla.
  • Används i stor utsträckning: De är ett populärt val för att implementera olika datastrukturer och algoritmer.

4. Vilka är nackdelarna med att använda ett röd-svart träd?

  • Jämfört med enklare balanserade träd som AVL-träd har rödsvarta träd mer komplexa regler för insättning och borttagning.
  • Att bibehålla egenskaperna för röd-svart träd lägger till en liten overhead till varje insättnings- och raderingsoperation.
  • För applikationer med frekventa insättningar och borttagningar kan andra balanserade trädstrukturer vara mer lämpliga.

5. Vilka är några vanliga tillämpningar av röd-svarta träd?

  • Implementering av kartor och uppsättningar
  • Prioriterade köer
  • Filsystem
  • In-memory databaser
  • Grafik och spelutveckling (kollisionsdetektering, sökväg)
  • Red-Black Tree definition och betydelse i DSA
  • Självbalanserande binära sökträd
  • Red Black Tree vs AVL Tree
  • Vad är skillnaden mellan Heap och Red-Black Tree?
  • Insättning i röd-svart träd
  • Borttagning i röd-svart träd
  • Röd-svarta träd | Top-Down-insättning