JUNGLE 240418 ~ 240420 (W05)
KRAFTON JUNGLE Week 05
BST (Binary Search Tree) 삭제
BSTNode* removeNodeFromTree(BSTNode *root, int value)
{
/* add your code here */
// root가 비어있을 때 NULL 반환
if (root == NULL)
return NULL;
- 루트가 비어있으면
NULL반환
// 재귀를 통해 탐색 및 삭제 후 연결시켜주는 과정 (이전 노드의 부모와 연결시켜주는 작업 ***)
if (value < root->item) {
root->left = removeNodeFromTree(root->left, value);
}
else if (value > root->item) {
root->right = removeNodeFromTree(root->right, value);
}
- 재귀를 통해서
value가 루트의 값보다 작으면 왼쪽 서브 트리 탐색, 크면 오른쪽 서브 트리 탐색- 또한, 이 코드를 통해 삭제 된 후 원래 노드의 부모와 연결 시켜주는 작업이 이루어짐
// 탐색 성공 시
else {
// 자식이 0개인 경우 (리프 노드 삭제 시)
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
- 리프 노드를 삭제 할 경우 그냥
free해주면 됨- 그리고
NULL반환
// 자식이 1개인 경우
else if (root->left == NULL) {
BSTNode* tmp = root->right; // tmp에 오른쪽 노드를 저장한 뒤 올림
free(root);
return tmp;
}
else if (root->right == NULL) {
BSTNode* tmp = root->left; // tmp에 왼쪽 노드를 저장한 뒤 올림
free(root);
return tmp;
}
- 자식이 1개인 경우,
tmp에 삭제 할 노드의 자식의 값을 저장한 다음tmp를root로 올린다.- 그리고
root메모리 해제 후tmp반환
// 자식이 2개인 경우
else {
BSTNode* tmp = findMinValue(root->right); // 후임자 대체 방식
root->item = tmp->item;
root->right = removeNodeFromTree(root->right, tmp->item); // 오른쪽 서브트리에서 재귀 호출
}
}
return root; // 루트 반환
}
- 이 경우가 가장 복잡하다.
- 후임자 대체 방식으로 할 것이므로
tmp에 후임자의 값을 저장 후 루트에 넣어줌- 그리고 오른쪽 서브트리에서 함수 재귀 호출
RB-Tree
- 자가 균형 이진 탐색 트리
RB_Tree의 속성
- 모든 노드는 red 혹은 black
- 루트 노드는 black
- 모든 nil (leaf) 노드는 black
- red의 자녀들은 black (red가 연속적으로 존재할 수 없다.)
- 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)
RB-Tree의 회전
삽입, 삭제 Fix_up 과정에서 필요하다.
Left_Rotate
left_rotate(T, x)
y = x.right // y 지정
x.right = y.left // 1. 서브트리 이동 및 연결
if y.left != T.nil
y.left.p = x
y.p = x.p // 2. 부모 연결
// 3. x의 위치에 맞게 서브트리 삽입
if x.p == T.nil // 3-1. x가 root 일 때
T.root = y
else if x == x.p.left // 3-2. x가 오른쪽에 위치할 때
x.p.left = y
else // 3-3. x가 왼쪽에 위치할 때
x.p.right = y
y.left = x // 4. x 위치 조정
x.p = y
Right_Rotate
right_rotate(T, x)
y = x.left // y 지정
x.left = y.right // 1. 서브트리 이동 및 연결
if y.right !- T.nil
y.right.p = x
y.p = x.p // 2. 부모 연결
// 3. x의 위치에 맞게 서브트리 삽입
if x.p == T.nil // 3-1. x가 root 일 때
T.root = y
else if x == x.p.right // 3-2. x가 오른쪽에 위치할 때
x.p.right = y
else // 3-3. x가 왼쪽에 위치할 때
x.p.left = y
y.right = x // 4. x 위치 조정
x.p = y
RB-Tree의 삽입
- 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입
- 빨간색 노드가 연속으로 2번 나타나는 경우, 삼촌 노드의 색에 따라 2가지 경우로 나뉨
- 새로 삽입할 노드를 N, 부모 노드를 P, 조상 노드를 G, 삼촌 노드를 U라고 했을 경우,
- 삼촌 노드가 Black 이라면, Restructuring 수행
- 삼촌 노드가 Red 라면, Recoloring 수행
Restructuring
- 새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬
- 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
- 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.
- restructuring 해야 하는 노드가 선형일 때와 삼각형일 때의 2가지 경우
- Restructuring (triangle): rotate Parent
- Restructuring (line): rotate Grandparent
Recoloring
- 새로운 노드의 부모와 삼촌을 검은색으로 바꾸고 조상을 빨간색으로 바꾼다.
- 조상이 루트 노드라면 검은색으로 바꾼다.
- 조상을 빨간색으로 바꿨을 때 또 다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.
Insert
RB_INSERT (T, z)
y = T.nil
x = T.root
// x가 Nil이 아닐 때까지 반복
while x != T.nil
y = x
if z.key < x.key // z의 위치를 찾는 과정
x = x.left
else
x = x.right
// 새로운 노드 z의 부모를 y로 설정
z.p = y
if y == T.nil
T.root = z
else if z.key < y.key
y.left = z
else
y.right = z
z.left = T.nil
z.right = T.nil
z.color = RED // 삽입은 무조건 빨간색으로
RB_INSERT_FIXUP (T, z)
Insert_fixup
RB_INSERT_FIXUP (T, z)
while z.p.color == RED
if z.p == z.p.p.left // 부모가 왼쪽 자식이라면,
y = z.p.p.right // y에 삼촌 노드 할당
if y.color == RED // 삼촌이 빨간색이라면 -> Recoloring
z.p.color = BLACK
y.color = BLACK
z.p.p.color = RED
z = z.p.p
else
if z == z.p.right // 삼촌이 검정색이라면 -> Restructuring
z = z.p // Case 1: Restructuring (Triangle)
LEFT_ROTATE(T, z)
z.p.color = BLACK // Case 2: Restructuring (Line)
z.p.p.color = RED
RIGHT_ROTATE (T, z.p.p)
RB-Tree의 삭제
Transplant
이식 과정에서는 target 노드와 그 노드의 parent 노드의 연결관계 만을 처리하는 과정
Transplant (T, u, v) // u는 삭제할 노드, v는 대체할 노드
if u.p == T.nil // 1. u가 루트 노드인 경우
T.root = v
else if u == u.p.right // 2. u가 오른쪽에 있었던 경우
u.p.right = v
else // 3. u가 왼쪽에 있었던 경우
u.p.left = v
v.p = u.p // 부모 연결
Delete
- 보통의 BST처럼 삭제
- 실제로 삭제된 노드가 RED면 종료
- 삭제된 노드가 BLACK이면
Delete_fixup호출
RB_DELETE (T, z)
y = z
y-original-color = y.color
// 자식이 하나거나 없을 경우
if z.left == T.nil
x = z.right
RB_TRANSPLANT (T, z, z.right)
else if z.right == T.nil
x = z.left
RB_TRANSPLANT (T, z, z.left)
// 자식이 둘인 경우
else
y = TREE_MINIMUM (z.right) // 후임자의 색 저장
y-original-color = y.color
x = y.right
if y.p == z // 후임자가 z의 자식인 경우
x.p = y
else // 후임자가 z의 자식이 아닌 경우
RB_TRANSPLANT (T, y, y.right)
y.right = z.right
y.right.p = y
RB_TRANSPLANT (T, z, y) // 삭제 후 대체 작업
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK // 삭제되는 색이 검정이라면,
RB_DELETE_FIXUP (T, x) // FIX_UP 호출
Delete_fixup
속성 위반 여부를 확인하는 방법은 삭제되는 색을 통해 알 수 있음
- 삭제하려는 노드의 자녀가 없거나 하나라면, 삭제되는 색(y)은 삭제되는 노드의 색
- 삭제하려는 노드의 자녀가 둘이라면, 삭제되는 색(y)은 삭제되는 노드의 전임자 or 후임자의 색
✔ Delete_fixup Case
- Extra BLACK을 순차적으로 트리의 위쪽으로 올려보냄.
- x가 RED & BLACK인 경우 그냥 BLACK 노드로 바꿔줌
- x가 루트가 되는 순간까지 올라가면 그냥 Extra BLACK을 제거
- w is RED
- w is BLACK, and w.left & w.right are BLACK
- w is BLACK, and w.left is RED & w.right is BLACK
- w is BLACK, and w.right is RED
RB_DELETE_FIXUP (T, x)
while x != T.root and x.color == BLACK
// x가 왼쪽 자식일 때
if x == x.p.left
w = x.p.right
if w.color == RED // Case 1: 형제 노드가 RED일 때
w.color = BLACK
x.p.color = RED
LEFT_ROTATE (T, x.p)
w = x.p.right
// Case 2,3,4: 형제 노드가 BLACK일 때
if w.left.color == BLACK and w.right.color == BLACK // Case 2: 형제의 자식들이 모두 BLACK일 때
w.color = RED
x = x.p
else if w.right.color == BLACK // Case 3: 형제의 오른쪽 자식이 BLACK일 때
w.left.color = BLACK
w.color = RED
RIGHT_ROTATE (T, w)
w = x.p.right
w.color = x.p.color // Case 4: 형제의 오른쪽 자식이 RED일 때
x.p.color = BLACK
w.right.color = BLACK
LEFT_ROTATE (T, x.p)
x = T.root
전체 코드 링크 : Click Here!!
