HOWTO · C++
C++의 레드 블랙 트리
이 튜토리얼은 C++의 레드-블랙 트리를 보여줍니다.
이 페이지의 내용
이 튜토리얼은 C++의 레드-블랙 트리를 보여줍니다.
C++의 레드 블랙 트리
레드-블랙 트리는 각 노드가 노드의 색상을 나타내는 고유 속성을 포함하는 경우 사용되는 자체 균형 이진 검색 트리로 간주됩니다. Red-Black에는 다음과 같은 다섯 가지 속성이 있습니다.
빨간색/검은색속성 - 트리의 모든 노드는 빨간색 또는 검은색으로 표시됩니다.루트속성 - 루트는 항상 검은색입니다.리프속성 - 모든 리프(NIL)는 항상 검은색입니다.빨간색속성 - 모든 빨간색 노드 자식이 있는 경우 검은색이어야 합니다.Depth속성 - 한 노드에서 다른 자손 리프까지의 모든 경로는 블랙 노드의 수와 동일한 블랙 깊이 수단을 갖습니다.
위의 조건이 충족되지 않으면 해당 트리는 레드 블랙 트리가 될 수 없습니다. 아래 그림에서 red-black 트리의 구조를 참조하십시오.
보시다시피 루트 노드를 제외한 각 노드에는 색상, 키, 왼쪽 자식, 오른쪽 자식 및 부모가 있습니다.
위의 속성에서 레드-블랙 트리는 노드 색상의 제한으로 인해 루트에서 리드까지의 경로가 두 번 이상 길지 않아 트리가 유지하는 데 도움이 되기 때문에 자체 균형 트리가 됩니다. 스스로 균형을 잡습니다.
Red-Black 트리에서 하위 트리의 회전
교체 시 하위 트리 노드의 위치가 서로 바뀌는데, 이는 삽입 및 삭제와 같은 다른 작업의 영향을 받기 때문에 red-black 트리의 속성을 유지하는 데 사용됩니다. 회전 유형은 다음과 같습니다.
왼쪽 회전- 이 유형의 회전에서는 오른쪽의 노드 배열이 왼쪽 노드의 배열로 변환됩니다.오른쪽 회전- 이 유형의 회전에서는 왼쪽의 노드 배열이 오른쪽 노드의 배열로 변환됩니다.왼쪽-오른쪽 회전- 이 유형의 회전에서는 배열이 먼저 왼쪽으로 이동한 다음 오른쪽으로 이동합니다.오른쪽-왼쪽 회전- 이 유형의 회전에서는 정렬이 먼저 오른쪽으로 이동한 다음 왼쪽으로 이동합니다.재색상- 재색상에서 노드의 색상을 뒤집습니다. 예를 들어 노드가 빨간색이면 검은색이 되거나 그 반대가 됩니다.
삽입
레드-블랙 트리에 노드를 삽입하려면 아래 단계를 따르십시오.
- 일반 BST 작업을 사용하여 노드를 삽입합니다.
- 삽입된 노드를 빨간색으로 색칠합니다.
- 마지막으로 삽입이 레드-블랙 트리 속성을 위반했는지 확인합니다. 만약 그렇다면, 우리는 그것을 고쳐야 합니다.
다음은 레드-블랙 트리에 삽입하기 위한 의사 코드입니다.
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
삭제
삭제 작업은 삽입보다 약간 까다롭습니다. 노드를 삭제하려면 먼저 BST 삭제를 따라야 합니다. 이렇게 하면 노드가 단일 자식 또는 리프 노드인지 확인할 수 있습니다.
아래 의사 코드는 레드-블랙 트리에서 삭제 작업을 보여줍니다.
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
레드-블랙 트리의 회전, 삽입 및 삭제를 이해했으므로 이를 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();
}
위의 코드는 red-black 트리를 만들고 삽입, 삭제 및 회전 작업을 적용합니다.
출력:
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)
