red–black tree (tsz. red–black trees)
A Red-Black fa egy speciális típusú kiegyensúlyozott bináris keresőfa, amelynek minden csomópontja egy színnel rendelkezik (piros vagy fekete). A fa fenntartja a következő fontos tulajdonságokat, amelyek biztosítják a logaritmikus időkomplexitást:
A Red-Black fa az AVL fához hasonlóan dinamikusan kiegyensúlyozza magát, de egyszerűbb a karbantartása és a műveletek gyorsabban végezhetők el.
A Red-Black fa két fő műveletet biztosít, amelyeket gyakran használunk: a beszúrás és a törlés. A beszúrás és törlés során a fa szabályainak fenntartása érdekében bizonyos forgatásokat és színezési műveleteket kell végezni.
A keresés művelete ugyanúgy működik, mint egy hagyományos bináris keresőfán. A keresési művelet során a fa bal vagy jobb ágán haladunk, attól függően, hogy a keresett elem kisebb vagy nagyobb a jelenlegi csomóponthoz képest. A keresés O(log n) idő alatt történik, mivel a fa mindig kiegyensúlyozott marad.
A beszúrás során a fa elejére kerül az új elem, és mint minden más bináris keresőfában, megtaláljuk a megfelelő helyet a szülő csomópont alapján. Az új csomópont kezdetben piros színű. A fa színezési szabályait és a forgatásokat alkalmazzuk, ha a beszúrás megsérti a fa szabályait. Ha a fa egyensúlyát a beszúrás megsérti, akkor balra és jobbra forgatásokat alkalmazunk, hogy visszaállítsuk a fa egyensúlyát és biztosítsuk a logaritmikus időt.
A törlés során a fában található csomópontot töröljük, majd a fa újra kiegyensúlyozására van szükség. A törlés után is biztosítani kell, hogy a Red-Black fa színezési szabályai érvényesek maradjanak, és ha szükséges, forgatásokat végzünk a fa kiegyensúlyozására.
A következő C++ példában egy egyszerű Red-Black fa implementációt mutatunk be. A kód tartalmazza az alapvető műveleteket, mint a beszúrás, törlés és a fa kiegyensúlyozása.
#include <iostream>
using namespace std;
enum Color { RED, BLACK };
struct Node {
int data;
Node *parent, *left, *right;
Color color;
};
// Segédfunkciók
int max(int a, int b) { return (a > b) ? a : b; }
int height(Node* node) {
if (node == nullptr) return 0;
return 1 + max(height(node->left), height(node->right));
}
// Jobbra forgatás
Node* rightRotate(Node* root, Node* x) {
Node* y = x->left;
x->left = y->right;
if (y->right != nullptr) y->right->parent = x;
y->parent = x->parent;
if (x->parent == nullptr) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->right = x;
x->parent = y;
return root;
}
// Balra forgatás
Node* leftRotate(Node* root, Node* x) {
Node* y = x->right;
x->right = y->left;
if (y->left != nullptr) y->left->parent = x;
y->parent = x->parent;
if (x->parent == nullptr) root = y;
else if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
y->left = x;
x->parent = y;
return root;
}
// Kiegyensúlyozás a beszúrás után
void fixInsert(Node* root, Node* k) {
Node* u;
while (k->parent->color == RED) {
if (k->parent == k->parent->parent->left) {
u = k->parent->parent->right;
if (u != nullptr && u->color == RED) {
k->parent->color = BLACK;
u->color = BLACK;
k->parent->parent->color = RED;
k = k->parent->parent;
} else {
if (k == k->parent->right) {
k = k->parent;
root = leftRotate(root, k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
root = rightRotate(root, k->parent->parent);
}
} else {
u = k->parent->parent->left;
if (u != nullptr && u->color == RED) {
k->parent->color = BLACK;
u->color = BLACK;
k->parent->parent->color = RED;
k = k->parent->parent;
} else {
if (k == k->parent->left) {
k = k->parent;
root = rightRotate(root, k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
root = leftRotate(root, k->parent->parent);
}
}
if (k == root) break;
}
root->color = BLACK;
}
// Beszúrás
Node* insert(Node* root, int data) {
Node* node = new Node;
node->data = data;
node->parent = nullptr;
node->left = nullptr;
node->right = nullptr;
node->color = RED;
Node* y = nullptr;
Node* x = root;
while (x != nullptr) {
y = x;
if (node->data < x->data) x = x->left;
else x = x->right;
}
node->parent = y;
if (y == nullptr) root = node;
else if (node->data < y->data) y->left = node;
else y->right = node;
fixInsert(root, node);
return root;
}
// Inorder Traversal
void inorder(Node* root) {
if (root != nullptr) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
int main() {
Node* root = nullptr;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 15);
root = insert(root, 25);
cout << "Inorder traversal of the Red-Black Tree: ";
inorder(root);
cout << endl;
return 0;
}
Node
struktúra minden csomópontot reprezentál, amely tárolja az adatot, a bal és jobb gyermeket, valamint a csomópont színét (piros vagy fekete).rightRotate
és leftRotate
függvények végzik el a szükséges forgatásokat a fa kiegyensúlyozására.fixInsert
függvény biztosítja, hogy a Red-Black fa szabályai érvényesek maradjanak a beszúrás után. A fa kiegyensúlyozásához alkalmazza a megfelelő forgatásokat.insert
függvény biztosítja az új csomópont beszúrását és a megfelelő helyre helyezi az adatokat a fa sorrendje alapján.inorder
függvény az összes faelemet inorder sorrendben írja ki.
A Red-Black fa egy kiegyensúlyozott bináris keresőfa, amely segít gyors adatkeresést végezni logaritmikus időben. A C++ implementáció bemutatja, hogyan lehet a fa kiegyensúlyozásához szükséges forgatásokat alkalmazni, és hogyan lehet fenntartani a fa szabályait. A Red-Black fa különösen előnyös, mivel a műveletek gyorsak és hatékonyak még nagy adatmennyiség esetén is, biztosítva a gyors keresést és módosítást.