Árbol rojo y negro en C++
Sheeraz Gul
15 febrero 2024
Este tutorial demuestra el árbol rojo-negro en C++.
Árbol rojo y negro en C++
El árbol rojo-negro se considera un árbol de búsqueda binario autoequilibrado que se utiliza en el que cada nodo contiene una propiedad distinta que indica el color del nodo. Red-Black tiene las siguientes cinco propiedades.
- Propiedad
Rojo/Negro: todos los nodos del árbol están coloreados, ya sea rojo o negro. - Propiedad
Raíz- La raíz siempre es negra. - Propiedad
Hoja- Cada hoja (NIL) es siempre negra. - Propiedad
Roja- Todos los hijos del nodo rojo deben ser negros si lo tienen. - Propiedad
Depth- Cualquier ruta de un nodo a otra hoja descendiente tendrá los mismos medios de profundidad negra que el número de nodos negros.
Si las condiciones anteriores no se cumplen en ninguna parte, entonces ese árbol no puede ser un árbol rojo y negro. Vea la estructura del árbol rojo-negro en la figura a continuación.
Como podemos ver, cada nodo tiene un color, una clave, un hijo izquierdo, un hijo derecho y un padre excepto el nodo raíz.
De las propiedades anteriores, el árbol rojo-negro está destinado a ser el árbol autoequilibrado porque la limitación del color de los nodos garantiza que cualquier camino desde la raíz hasta un conductor no sea más largo que el doble, lo que ayuda al árbol a mantener equilibrándose a sí mismo.
Rotación de subárboles en un árbol rojo-negro
En la rotación, las posiciones de los nodos de los subárboles se intercambian, lo que se usa para mantener las propiedades de los árboles rojo-negro, ya que se ven afectados por otras operaciones como la inserción y la eliminación. Los tipos de rotación son:
Rotación a la izquierda: en este tipo de rotación, la disposición de los nodos de la derecha se transforma en la disposición del nodo izquierdo.Rotación a la derecha: en este tipo de rotación, la disposición de los nodos de la izquierda se transforma en la disposición del nodo derecho.Rotación izquierda-derecha: en este tipo de rotación, la disposición se desplazará primero hacia la izquierda y luego hacia la derecha.Rotación Derecha-Izquierda- En este tipo de rotación, la disposición se desplazará primero hacia la derecha y luego hacia la izquierda.Recolor- En recolor, cambiamos el color del nodo; por ejemplo, si un nodo es rojo, se vuelve negro o viceversa.
Inserción
Siga los pasos a continuación para insertar un nodo en el árbol rojo-negro.
- Inserte el nodo usando la operación BST ordinaria.
- Colorea el nodo insertado de rojo.
- Finalmente, verifique si la inserción violó las propiedades del árbol rojo-negro; si lo hizo, tenemos que arreglarlo.
Aquí está el pseudocódigo para la inserción en el árbol rojo-negro.
RB - INSERT(Tree, n) BST -
INSERT(Tree, n) // ordinary BST insertion
while n.parent.color
== RED if n.parent == n.parent.parent.right u =
n.parent.parent
.left // uncle
if u.color
== RED u.color = BLACK n.parent.color = BLACK n.parent.parent.color =
RED n = n.parent.parent else if n == n.parent.left n =
n.parent LEFT -
ROTATE(Tree,
n) n.parent.color = BLACK n.parent.parent.color =
RED RIGHT -
ROTATE(Tree, n.parent.parent) else(
same with "left" and
"right" exchanged) Tree.root.color = BLACK
Supresión
La operación de eliminación es un poco más complicada que la inserción; para eliminar un nodo, también tenemos que seguir primero la eliminación de BST, lo que garantizará que el nodo sea un solo hijo o un nodo hoja.
El pseudocódigo a continuación muestra la operación de eliminación en el árbol rojo-negro.
RB-DELETE(Tree, n)
BST-DELETE(Tree, n)
while n ≠ Tree.root and n.color == BLACK
if n == n.parent.left
s = n.parent.right
if s.color == RED
s.color = BLACK
n.parent.color = RED
LEFT-ROTATE(Tree, n.parent)
s = n.parent.right
if s.left.color == BLACK and s.right.color == BLACK
s.color = RED
n = n.parent
else if s.right.color == BLACK
s.left.color = BLACK
s.color = RED
RIGHT-ROTATE(Tree, s)
s = n.parent.right
s.color = n.parent.right
n.parent.color = BLACK
s.right.color = BLACK
LEFT-ROTATE(Tree, n.parent)
n = Tree.root
else (same as with "right" and "left" exchanged)
n.color = BLACK
Como entendemos la rotación, inserción y eliminación de un árbol rojo-negro, intentemos implementarlo en C++.
#include <iostream>
using namespace std;
struct Node {
int NodeData;
Node *parentNode;
Node *leftNode;
Node *rightNode;
int NodeColor;
};
typedef Node *NodePtr;
class REDBLACKTREE {
private:
NodePtr root;
NodePtr TNULL;
void INITIALIZENULLNode(NodePtr node, NodePtr parentNode) {
node->NodeData = 0;
node->parentNode = parentNode;
node->leftNode = nullptr;
node->rightNode = nullptr;
node->NodeColor = 0;
}
// The Preorder
void PREORDERHELPER(NodePtr node) {
if (node != TNULL) {
cout << node->NodeData << " ";
PREORDERHELPER(node->leftNode);
PREORDERHELPER(node->rightNode);
}
}
// The Inorder
void INORDERHELPER(NodePtr node) {
if (node != TNULL) {
INORDERHELPER(node->leftNode);
cout << node->NodeData << " ";
INORDERHELPER(node->rightNode);
}
}
// the Post order
void POSTORDERHELPER(NodePtr node) {
if (node != TNULL) {
POSTORDERHELPER(node->leftNode);
POSTORDERHELPER(node->rightNode);
cout << node->NodeData << " ";
}
}
NodePtr SEARCHTREEHELPER(NodePtr node, int key) {
if (node == TNULL || key == node->NodeData) {
return node;
}
if (key < node->NodeData) {
return SEARCHTREEHELPER(node->leftNode, key);
}
return SEARCHTREEHELPER(node->rightNode, key);
}
// For balancing the tree after deletion
void DELETEFIX(NodePtr x) {
NodePtr s;
while (x != root && x->NodeColor == 0) {
if (x == x->parentNode->leftNode) {
s = x->parentNode->rightNode;
if (s->NodeColor == 1) {
s->NodeColor = 0;
x->parentNode->NodeColor = 1;
LEFTROTATE(x->parentNode);
s = x->parentNode->rightNode;
}
if (s->leftNode->NodeColor == 0 && s->rightNode->NodeColor == 0) {
s->NodeColor = 1;
x = x->parentNode;
} else {
if (s->rightNode->NodeColor == 0) {
s->leftNode->NodeColor = 0;
s->NodeColor = 1;
RIGHTNODEROTATE(s);
s = x->parentNode->rightNode;
}
s->NodeColor = x->parentNode->NodeColor;
x->parentNode->NodeColor = 0;
s->rightNode->NodeColor = 0;
LEFTROTATE(x->parentNode);
x = root;
}
} else {
s = x->parentNode->leftNode;
if (s->NodeColor == 1) {
s->NodeColor = 0;
x->parentNode->NodeColor = 1;
RIGHTNODEROTATE(x->parentNode);
s = x->parentNode->leftNode;
}
if (s->rightNode->NodeColor == 0 && s->rightNode->NodeColor == 0) {
s->NodeColor = 1;
x = x->parentNode;
} else {
if (s->leftNode->NodeColor == 0) {
s->rightNode->NodeColor = 0;
s->NodeColor = 1;
LEFTROTATE(s);
s = x->parentNode->leftNode;
}
s->NodeColor = x->parentNode->NodeColor;
x->parentNode->NodeColor = 0;
s->leftNode->NodeColor = 0;
RIGHTNODEROTATE(x->parentNode);
x = root;
}
}
}
x->NodeColor = 0;
}
void RBTRANSPLANT(NodePtr u, NodePtr v) {
if (u->parentNode == nullptr) {
root = v;
} else if (u == u->parentNode->leftNode) {
u->parentNode->leftNode = v;
} else {
u->parentNode->rightNode = v;
}
v->parentNode = u->parentNode;
}
void DELETENODEHELPER(NodePtr node, int key) {
NodePtr z = TNULL;
NodePtr x, y;
while (node != TNULL) {
if (node->NodeData == key) {
z = node;
}
if (node->NodeData <= key) {
node = node->rightNode;
} else {
node = node->leftNode;
}
}
if (z == TNULL) {
cout << "The Key is not found in the tree" << endl;
return;
}
y = z;
int y_original_NodeColor = y->NodeColor;
if (z->leftNode == TNULL) {
x = z->rightNode;
RBTRANSPLANT(z, z->rightNode);
} else if (z->rightNode == TNULL) {
x = z->leftNode;
RBTRANSPLANT(z, z->leftNode);
} else {
y = minimum(z->rightNode);
y_original_NodeColor = y->NodeColor;
x = y->rightNode;
if (y->parentNode == z) {
x->parentNode = y;
} else {
RBTRANSPLANT(y, y->rightNode);
y->rightNode = z->rightNode;
y->rightNode->parentNode = y;
}
RBTRANSPLANT(z, y);
y->leftNode = z->leftNode;
y->leftNode->parentNode = y;
y->NodeColor = z->NodeColor;
}
delete z;
if (y_original_NodeColor == 0) {
DELETEFIX(x);
}
}
// balance the tree after insertion
void INSERTFIX(NodePtr k) {
NodePtr u;
while (k->parentNode->NodeColor == 1) {
if (k->parentNode == k->parentNode->parentNode->rightNode) {
u = k->parentNode->parentNode->leftNode;
if (u->NodeColor == 1) {
u->NodeColor = 0;
k->parentNode->NodeColor = 0;
k->parentNode->parentNode->NodeColor = 1;
k = k->parentNode->parentNode;
} else {
if (k == k->parentNode->leftNode) {
k = k->parentNode;
RIGHTNODEROTATE(k);
}
k->parentNode->NodeColor = 0;
k->parentNode->parentNode->NodeColor = 1;
LEFTROTATE(k->parentNode->parentNode);
}
} else {
u = k->parentNode->parentNode->rightNode;
if (u->NodeColor == 1) {
u->NodeColor = 0;
k->parentNode->NodeColor = 0;
k->parentNode->parentNode->NodeColor = 1;
k = k->parentNode->parentNode;
} else {
if (k == k->parentNode->rightNode) {
k = k->parentNode;
LEFTROTATE(k);
}
k->parentNode->NodeColor = 0;
k->parentNode->parentNode->NodeColor = 1;
RIGHTNODEROTATE(k->parentNode->parentNode);
}
}
if (k == root) {
break;
}
}
root->NodeColor = 0;
}
void PRINTHELPER(NodePtr root, string indent, bool last) {
if (root != TNULL) {
cout << indent;
if (last) {
cout << "R-----";
indent += " ";
} else {
cout << "L-----";
indent += "| ";
}
string sNodeColor = root->NodeColor ? "RED" : "BLACK";
cout << root->NodeData << "(" << sNodeColor << ")" << endl;
PRINTHELPER(root->leftNode, indent, false);
PRINTHELPER(root->rightNode, indent, true);
}
}
public:
REDBLACKTREE() {
TNULL = new Node;
TNULL->NodeColor = 0;
TNULL->leftNode = nullptr;
TNULL->rightNode = nullptr;
root = TNULL;
}
void preorder() { PREORDERHELPER(this->root); }
void inorder() { INORDERHELPER(this->root); }
void postorder() { POSTORDERHELPER(this->root); }
NodePtr searchTree(int k) { return SEARCHTREEHELPER(this->root, k); }
NodePtr minimum(NodePtr node) {
while (node->leftNode != TNULL) {
node = node->leftNode;
}
return node;
}
NodePtr maximum(NodePtr node) {
while (node->rightNode != TNULL) {
node = node->rightNode;
}
return node;
}
NodePtr successor(NodePtr x) {
if (x->rightNode != TNULL) {
return minimum(x->rightNode);
}
NodePtr y = x->parentNode;
while (y != TNULL && x == y->rightNode) {
x = y;
y = y->parentNode;
}
return y;
}
NodePtr predecessor(NodePtr x) {
if (x->leftNode != TNULL) {
return maximum(x->leftNode);
}
NodePtr y = x->parentNode;
while (y != TNULL && x == y->leftNode) {
x = y;
y = y->parentNode;
}
return y;
}
void LEFTROTATE(NodePtr x) {
NodePtr y = x->rightNode;
x->rightNode = y->leftNode;
if (y->leftNode != TNULL) {
y->leftNode->parentNode = x;
}
y->parentNode = x->parentNode;
if (x->parentNode == nullptr) {
this->root = y;
} else if (x == x->parentNode->leftNode) {
x->parentNode->leftNode = y;
} else {
x->parentNode->rightNode = y;
}
y->leftNode = x;
x->parentNode = y;
}
void RIGHTNODEROTATE(NodePtr x) {
NodePtr y = x->leftNode;
x->leftNode = y->rightNode;
if (y->rightNode != TNULL) {
y->rightNode->parentNode = x;
}
y->parentNode = x->parentNode;
if (x->parentNode == nullptr) {
this->root = y;
} else if (x == x->parentNode->rightNode) {
x->parentNode->rightNode = y;
} else {
x->parentNode->leftNode = y;
}
y->rightNode = x;
x->parentNode = y;
}
// Inserting a node
void INSERTNODE(int key) {
NodePtr node = new Node;
node->parentNode = nullptr;
node->NodeData = key;
node->leftNode = TNULL;
node->rightNode = TNULL;
node->NodeColor = 1;
NodePtr y = nullptr;
NodePtr x = this->root;
while (x != TNULL) {
y = x;
if (node->NodeData < x->NodeData) {
x = x->leftNode;
} else {
x = x->rightNode;
}
}
node->parentNode = y;
if (y == nullptr) {
root = node;
} else if (node->NodeData < y->NodeData) {
y->leftNode = node;
} else {
y->rightNode = node;
}
if (node->parentNode == nullptr) {
node->NodeColor = 0;
return;
}
if (node->parentNode->parentNode == nullptr) {
return;
}
INSERTFIX(node);
}
NodePtr getRoot() { return this->root; }
void DELETENODE(int NodeData) { DELETENODEHELPER(this->root, NodeData); }
void printTree() {
if (root) {
PRINTHELPER(this->root, "", true);
}
}
};
int main() {
REDBLACKTREE DEMOBST;
DEMOBST.INSERTNODE(51);
DEMOBST.INSERTNODE(44);
DEMOBST.INSERTNODE(62);
DEMOBST.INSERTNODE(34);
DEMOBST.INSERTNODE(85);
DEMOBST.INSERTNODE(54);
DEMOBST.printTree();
cout << endl << "After deleting" << endl;
DEMOBST.DELETENODE(62);
DEMOBST.printTree();
}
El código anterior creará un árbol rojo-negro y aplicará operaciones de inserción, eliminación y rotación.
Producción :
R-----51(BLACK)
L-----44(BLACK)
| L-----34(RED)
R-----62(BLACK)
L-----54(RED)
R-----85(RED)
After deleting
R-----51(BLACK)
L-----44(BLACK)
| L-----34(RED)
R-----85(BLACK)
L-----54(RED)
Autor: Sheeraz Gul
Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.
LinkedIn Facebook