red–black tree

red–black tree (tsz. red–black trees)

1. (informatika) A Red-Black tree (piros-fekete fa) egy kiegyensúlyozott bináris keresőfa (BST), amelyet a matematikusok dolgoztak ki annak érdekében, hogy biztosítsák a fa műveleteinek (keresés, beszúrás, törlés) hatékonyságát és kiegyensúlyozottságát. A Red-Black fa speciális szabályokkal rendelkezik, amelyek garantálják, hogy a fa magassága soha ne legyen túl nagy, így a műveletek mindig logaritmikus időben végezhetők el. A Red-Black fa O(log n) időkomplexitással működik, ami azt jelenti, hogy a fa műveletei, mint például a keresés és a beszúrás, gyorsak, még nagy adatmennyiség esetén is.

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:

1. A gyökér csomópont fekete.
2. Minden levelek fekete színűek (a levelek itt a nullát tartalmazó csomópontokat jelentik).
3. Piros csomópontok nem lehetnek egymás mellett (nincs két egymást követő piros csomópont).
4. Minden út, amely a gyökértől egy levélig tart, ugyanannyi fekete csomópontot tartalmaz.

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.

1. A gyökér csomópont mindig fekete.
2. A piros csomópontok nem lehetnek egymás mellett.
3. Minden út, amely a gyökértől a levelekig vezet, ugyanannyi fekete csomópontot tartalmaz.

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;
}

1. Csomópontok: A 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).
2. Jobb és bal forgatás: A rightRotate és leftRotate függvények végzik el a szükséges forgatásokat a fa kiegyensúlyozására.
3. Színezés: A 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.
4. Beszúrás: Az 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.
5. Inorder Traversal: Az 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.

• red–black tree - Szótár.net (en-hu)
• red–black tree - Sztaki (en-hu)
• red–black tree - Merriam–Webster
• red–black tree - Cambridge
• red–black tree - WordNet
• red–black tree - Яндекс (en-ru)
• red–black tree - Google (en-hu)
• red–black tree - Wikidata
• red–black tree - Wikipédia (angol)