레드블랙트리 삭제 구현/ C++
2023. 3. 11. 21:40ㆍ개인공부/자료구조와 알고리즘
반환값은 다음 이터레이터를 반환한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
RedBlackTree::iterator& RedBlackTree::erase(iterator& iter) // 반환값은 중위후속자이다.
{
Node* iNode = iter.node;
iterator Returniter = iter; // 리턴 이터레이터
bool IsBlack = false; // 삭제한 노드의 색깔 false : RED ture: BLACK
iterator Successoriter = iter; // 중위 후속자
++Successoriter;
Node* Successor = Successoriter.node;
// 삭제할 노드가 자식이 없는 경우
if (iNode->LeftChild == Leaf && iNode->RightChild == Leaf)
{
if (iNode->Parent != nullptr)
{
Node* DoubleBlack = new Node;
DoubleBlack->Color = COLOR::BLACK;
DoubleBlack->Parent = iNode->Parent;
if (IsLeftChild(iNode))
iNode->Parent->LeftChild = DoubleBlack;
else
iNode->Parent->RightChild = DoubleBlack;
Returniter.node = DoubleBlack;
if (iNode->Color == COLOR::BLACK)
{
EraseFix(Returniter.node);
}
else
{
if (IsLeftChild(DoubleBlack))
DoubleBlack->Parent->LeftChild = Leaf;
else
DoubleBlack->Parent->RightChild = Leaf;
delete DoubleBlack;
}
return Successoriter;
}
else
{
// 루트노드인 경우
iter.tree->Root = nullptr;
Returniter.node = nullptr;
}
if (iNode->Color == COLOR::BLACK)
IsBlack = true;
delete iNode;
}
// 삭제할 노드가 2개의 자식을 가진 경우
else if (iNode->LeftChild != Leaf && iNode->RightChild != Leaf)
{
iNode->iKey = Successor->iKey;
iNode->Color = Successor->Color;
if (Successor->LeftChild == Leaf && Successor->RightChild == Leaf) // 리프 노드
{
if (IsLeftChild(Successor))
Successor->Parent->LeftChild = Leaf;
else
Successor->Parent->RightChild = Leaf;
}
else if (Successor->LeftChild != Leaf) // 왼쪽 자식을 가짐
{
if (IsLeftChild(Successor))
Successor->Parent->LeftChild = Successor->LeftChild;
else
Successor->Parent->RightChild = Successor->LeftChild;
}
else // 오른쪽 자식을 가짐
{
if (IsLeftChild(Successor))
Successor->Parent->LeftChild = Successor->RightChild;
else
Successor->Parent->RightChild = Successor->RightChild;
}
if (Successor->Color == COLOR::BLACK)
IsBlack = true;
delete Successor;
}
else // 자식노드를 한개 가진 경우
{
Node* Child;
if (iNode->LeftChild == Leaf)
Child = iNode->RightChild;
else
Child = iNode->LeftChild;
if (iNode->Parent != nullptr)
{
Child->Parent = iNode->Parent;
if (IsLeftChild(iNode))
iNode->Parent->LeftChild = Child;
else
iNode->Parent->RightChild = Child;
}
else
{
Child->Parent = nullptr;
Root = Child;
}
if (iNode->Color == COLOR::BLACK)
IsBlack = true;
delete iNode;
Returniter.node = Child;
}
if (IsBlack == true)
EraseFix(Returniter.node);
return Returniter;
}
void RedBlackTree::EraseFix(Node* x)
{
if (x == nullptr) // end이면 반환
{
return;
}
else if (x->Color == COLOR::RED || x->Parent == nullptr)// 대체된 자리를 검은색으로 칠한다.
{
x->Color = COLOR::BLACK;
return;
}
bool LeftChild = IsLeftChild(x);
Node* Sibling; // 형제노드
if (LeftChild == true)
Sibling = x->Parent->RightChild;
else
Sibling = x->Parent->LeftChild;
// Case Change
if (Sibling->Color == COLOR::RED)
{
Node* Parent = x->Parent;
Sibling->Color = COLOR::BLACK;
x->Parent->Color = COLOR::RED;
if (LeftChild == true)
LeftRotation(Sibling);
else
RightRotation(Sibling);
if (LeftChild == true)
Sibling = x->Parent->RightChild;
else
Sibling = x->Parent->LeftChild;
}
// Case A
if (Sibling->LeftChild->Color == COLOR::BLACK && Sibling->RightChild->Color ==COLOR::BLACK)
{
Sibling->Color = COLOR::RED;
if (x->Parent->Color == COLOR::RED)
x->Parent->Color = COLOR::BLACK;
else
EraseFix(x->Parent);
}
// Case B
else if (Sibling->LeftChild->Color == COLOR::RED && Sibling->RightChild->Color == COLOR::BLACK &&
LeftChild == true)
{
Sibling->Color = COLOR::RED;
Sibling->LeftChild->Color = COLOR::BLACK;
RightRotation(Sibling->LeftChild);
}
else if (Sibling->RightChild->Color == COLOR::RED && Sibling->LeftChild->Color == COLOR::BLACK &&
LeftChild == false)
{
Sibling->Color = COLOR::RED;
Sibling->RightChild->Color = COLOR::BLACK;
LeftRotation(Sibling->RightChild);
}
// Case C
else if (LeftChild == true && Sibling->RightChild->Color == COLOR::RED)
{
Sibling->Color = x->Parent->Color;
Sibling->RightChild->Color = COLOR::BLACK;
x->Parent->Color = COLOR::BLACK;
LeftRotation(Sibling);
}
else if (LeftChild == false && Sibling->LeftChild->Color == COLOR::RED)
{
Sibling->Color = x->Parent->Color;
Sibling->LeftChild->Color = COLOR::BLACK;
x->Parent->Color = COLOR::BLACK;
RightRotation(Sibling);
}
if (x->LeftChild == nullptr)
{
if (IsLeftChild(x))
x->Parent->LeftChild = Leaf;
else
x->Parent->RightChild = Leaf;
delete x;
}
}
|
cs |
'개인공부 > 자료구조와 알고리즘' 카테고리의 다른 글
| A* 알고리즘 (0) | 2023.04.29 |
|---|---|
| 레드블랙트리 - 삭제 (0) | 2023.03.10 |
| 레드블랙트리 증감연산자 / C++ (0) | 2023.03.10 |
| 레드블랙트리 insert구현 / C++ (0) | 2023.03.09 |
| 레드블랙트리 (자가균형 이진탐색트리) (0) | 2023.03.08 |