piros-fekete fa
Kiejtés
- IPA: [ ˈpiroʃfɛkɛtɛfɒ]
Főnév
- (matematika, gráfelmélet, algoritmusok) A számítástudományban a piros-fekete fa alatt egy önkiegyensúlyozó bináris keresőfát értünk. A szerkezete összetett, de a gyakorlatban hatékony, hiszen a keresés, beszúrás és törlés lépésszáma a legrosszabb esetben is O(log n), ahol n a fában levő elemek száma.
Piros-fekete fa
A piros-fekete fa egy bináris keresőfa, amely garantálja, hogy a beszúrás, törlés és keresés műveletek időkomplexitása (O(n)) legyen. A piros-fekete fa egy önkiegyensúlyozó bináris keresőfa, amely egyensúlyi feltételek segítségével korlátozza a fa magasságát.
Tulajdonságok
Egy piros-fekete fa minden csúcsa rendelkezik egy szín attribútummal, amely lehet piros vagy fekete, és a következő tulajdonságokat teljesíti:
- Minden csúcs vagy piros, vagy fekete.
- A gyökér mindig fekete.
- Minden levél (NIL) fekete.
- A levelek olyan csúcsok, amelyekhez nem tartozik valódi érték.
- Egy piros csúcsnak nincsenek piros gyerekei.
- Azaz a piros csúcsok nem helyezkedhetnek egymás mellett (a fa “dupla piros” állapota nem engedélyezett).
- Bármely csúcsból egy levélig vezető összes út azonos számú fekete csúcsot tartalmaz.
- Ezt nevezzük fekete magasságnak.
Ezek a tulajdonságok biztosítják, hogy a fa kiegyensúlyozott maradjon, és a műveletek hatékonyan végrehajthatók legyenek.
Műveletek
1. Beszúrás
A beszúrás során először egy új csúcsot helyezünk el piros színnel. Ezután a fa tulajdonságainak megsértése esetén helyreállítjuk az egyensúlyt rotációkkal és színváltásokkal.
2. Törlés
A törlés során először eltávolítjuk a csúcsot, majd, ha szükséges, helyreállítjuk a tulajdonságokat hasonló rotációkkal és színváltásokkal.
3. Keresés
A keresés ugyanúgy működik, mint egy hagyományos bináris keresőfában, az időkomplexitása (O(n)).
4. Rotációk
- Balra forgatás: Az aktuális csúcs jobb gyermekét helyezzük a csúcs fölé.
- Jobbra forgatás: Az aktuális csúcs bal gyermekét helyezzük a csúcs fölé.
Időkomplexitás
- Beszúrás, törlés, keresés: (O(n)), mert a fa magassága legfeljebb (2 (n+1)).
Pszeudokód
Beszúrás
Insert(T, z):
helyezd el z-t a bináris keresőfa szabályai szerint
színezd z-t pirosra
amíg z nem a gyökér és z szülője piros:
ha z szülője a nagyapa bal gyereke:
ha z nagybátyja piros:
színezd z szülőjét és nagybátyját feketére
színezd z nagyapját pirosra
z = z nagyapja
különben:
ha z z szülőjének jobb gyereke:
z = z szülője
balra forgatás(z)
színezd z szülőjét feketére
színezd z nagyapját pirosra
jobbra forgatás(z nagyapja)
különben (szimmetrikus):
ugyanaz, mint fent, csak balra és jobbra cserélve
színezd a gyökeret feketére
Python implementáció
class Node:
def __init__(self, key, color="red", left=None, right=None, parent=None):
self.key = key
self.color = color
self.left = left
self.right = right
self.parent = parent
class RedBlackTree:
def __init__(self):
self.TNULL = Node(0, color="black")
self.root = self.TNULL
def insert(self, key):
new_node = Node(key, color="red", left=self.TNULL, right=self.TNULL)
y = None
x = self.root
while x != self.TNULL:
y = x
if new_node.key < x.key:
x = x.left
else:
x = x.right
new_node.parent = y
if y is None:
self.root = new_node
elif new_node.key < y.key:
y.left = new_node
else:
y.right = new_node
if new_node.parent is None:
new_node.color = "black"
return
if new_node.parent.parent is None:
return
self._fix_insert(new_node)
def _fix_insert(self, k):
while k.parent.color == "red":
if k.parent == k.parent.parent.right:
u = k.parent.parent.left
if u.color == "red":
u.color = "black"
k.parent.color = "black"
k.parent.parent.color = "red"
k = k.parent.parent
else:
if k == k.parent.left:
k = k.parent
self._rotate_right(k)
k.parent.color = "black"
k.parent.parent.color = "red"
self._rotate_left(k.parent.parent)
else:
u = k.parent.parent.right
if u.color == "red":
u.color = "black"
k.parent.color = "black"
k.parent.parent.color = "red"
k = k.parent.parent
else:
if k == k.parent.right:
k = k.parent
self._rotate_left(k)
k.parent.color = "black"
k.parent.parent.color = "red"
self._rotate_right(k.parent.parent)
if k == self.root:
break
self.root.color = "black"
def _rotate_left(self, x):
y = x.right
x.right = y.left
if y.left != self.TNULL:
y.left.parent = x
y.parent = x.parent
if x.parent is None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def _rotate_right(self, x):
y = x.left
x.left = y.right
if y.right != self.TNULL:
y.right.parent = x
y.parent = x.parent
if x.parent is None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
# Példa használat
rbt = RedBlackTree()
rbt.insert(10)
rbt.insert(20)
rbt.insert(30)
rbt.insert(15)
C++
#include <iostream>
using namespace std;
enum Color { RED, BLACK };
struct Node {
int data;
Color color;
Node* left;
Node* right;
Node* parent;
Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};
class RedBlackTree {
private:
Node* root;
void rotateLeft(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;
}
void rotateRight(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->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
void fixInsert(Node* k) {
Node* uncle;
while (k->parent != nullptr && k->parent->color == RED) {
if (k->parent == k->parent->parent->left) {
uncle = k->parent->parent->right;
// Ha a nagybáty piros
if (uncle != nullptr && uncle->color == RED) {
k->parent->color = BLACK;
uncle->color = BLACK;
k->parent->parent->color = RED;
k = k->parent->parent;
} else {
// Ha a nagybáty fekete
if (k == k->parent->right) {
k = k->parent;
rotateLeft(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rotateRight(k->parent->parent);
}
} else {
uncle = k->parent->parent->left;
// Szimmetrikus eset
if (uncle != nullptr && uncle->color == RED) {
k->parent->color = BLACK;
uncle->color = BLACK;
k->parent->parent->color = RED;
k = k->parent->parent;
} else {
if (k == k->parent->left) {
k = k->parent;
rotateRight(k);
}
k->parent->color = BLACK;
k->parent->parent->color = RED;
rotateLeft(k->parent->parent);
}
}
}
root->color = BLACK;
}
public:
RedBlackTree() : root(nullptr) {}
void insert(int data) {
Node* newNode = new Node(data);
if (root == nullptr) {
root = newNode;
root->color = BLACK;
return;
}
Node* current = root;
Node* parent = nullptr;
while (current != nullptr) {
parent = current;
if (newNode->data < current->data) {
current = current->left;
} else {
current = current->right;
}
}
newNode->parent = parent;
if (newNode->data < parent->data) {
parent->left = newNode;
} else {
parent->right = newNode;
}
fixInsert(newNode);
}
void inorderTraversal(Node* node) {
if (node == nullptr) return;
inorderTraversal(node->left);
cout << node->data << " ";
inorderTraversal(node->right);
}
void display() {
inorderTraversal(root);
cout << endl;
}
};
int main() {
RedBlackTree rbt;
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
rbt.insert(15);
rbt.insert(25);
rbt.insert(5);
cout << "Piros-fekete fa inorder bejárása: ";
rbt.display();
return 0;
}
Összegzés
A piros-fekete fa garantáltan hatékony adatszerkezet keresésekhez, beszúrásokhoz és törlésekhez. Bár bonyolultabb, mint az egyszerű bináris keresőfa, a stabil (O(n)) időkomplexitása miatt széles körben használják, például szótárak és prioritási sorok megvalósításában (pl. C++ STL map és set).
Fordítások
- angol: red-black tree (en)
- orosz: красно-чёрное дерево (ru) (krasno-čórnoje derevo)
- piros-fekete fa - Értelmező szótár (MEK)
- piros-fekete fa - Etimológiai szótár (UMIL)
- piros-fekete fa - Szótár.net (hu-hu)
- piros-fekete fa - DeepL (hu-de)
- piros-fekete fa - Яндекс (hu-ru)
- piros-fekete fa - Google (hu-en)
- piros-fekete fa - Helyesírási szótár (MTA)
- piros-fekete fa - Wikidata
- piros-fekete fa - Wikipédia (magyar)