레드 블랙 트리는 아래의 다섯가지 특징( 혹은 법칙 ) 을 가지는 이진 탐색 트리이다.
1. 모든 노드는 레드 혹은 블랙이다.
2. 루트 노드는 블랙이다.
3. 리프 노드는 블랙이다.
4. 레드 노드의 자식은 블랙이다. ( 레드노드가 연달아 배치 될수 없다 )
5. 루트 노드와 모든 리프 노드 사이에 존재하는 검은색 노드의 갯수는 같다.
특징자체는 단순하다. 하지만 5번 특징의 '사이에 존재하는' 란 표현이 조금 모호할수 있으므로 더 정확하게 설명하자면, 사이에 존재한다는 건 루트 노드부터 각각의 리프토드 까지 가는 각각의 경로상에 존재한다는 것을 뜻한다. 예를 들어
위와 같은 트리가 있다면, L1, L2는 블랙 노드를 하나 가지고있고, L3, L4는 두개 가지고있다는 것이다. (물론 그렇기때문에 위 트리는 레드블랙 트리가 아니다)
모호했던 5번 빼고는 나머지 설명은 다 이해했을 것이다. 그렇다면 각각의 특징들을 어떻게 구현해야 될지 좀 생각을 해보자.
1. 모든 노드는 레드 혹은 블랙이다.
이건 해결이라고 할것도없다. 그냥 모든 노드의 색 데이터를 레드 혹은 블랙으로만 표현하면된다.
2. 루트 노드는 블랙이다.
이것도 해결 자체는 간단하다. 루트 노드가 만약 레드노드 일경우, 블랙으로 칠하면된다. 해결은 간단하나 이 간단한 해결이 왜 가능한지는 조금 생각해봐야한다. 레드를 그냥 블랙으로 칠하는데 왜 문제가 되지 않을까 말이다. ( 어렵지 않으니 알아서 생각하길 바란다 )
3. 리프 노드는 블랙이다.
이것을 해결하기위해, 모든 리프노드를 검은색으로 칠하고 부모노드로 재귀를 타며 문제될만한 노드를 탐색하고 처리하는 미친 방법도 있겠지만, 더 간단히 생각해보자. 그냥 리프노드의 없는 자식을 검은색 리프노드로 취급하면된다. c++을 예를 들면, 리프노드가 가지고있는 자식 포인터의 null 값을 걍 검은색 리프노드로 취급하자는것이다.
4. 레드 노드의 자식은 블랙이다.
5. 루트 노드와 모든 리프 노드 사이에 존재하는 검은색 노드의 갯수는 같다.
4/5번의 특성을을 어떻게 구현할까를 생각하기 이전에, 4/5번 법칙이 삽입/삭제/검색 이 세가지 연산중 어느 연산에서 깨질 가능성이 있을지를 생각해보자... 물론 당연히 삽입/삭제이다. 검색이야 애초에 only read 작업이라 트리구조에 어떤 영향도 끼치지 않을것이고, 당연히 무언가를 추가하거나 무언가를 삭제할때 문제가 될것이다.
일단 삽입하는 노드는 무조건 레드노드로 할것이다( 블랙 노드일경우 문제가 더 많다 ), 그러면 어디에 삽입되냐에 따라 레드노드가 연달아 놓일 경우가 생길것이다, 즉 4번 법칙을 깨버릴것이고, 삭제의 경우 블랙노드를 삭제할경우 특정 경로에 블랙노드가 하나 줄어들게 되므로 5번 법칙에 문제가될것이다.그리고 이 두문제를 해결하기 위해 회전이란 테크닉을 이용할 것이므로, 우선은 회전이라는 테크닉부터 좀 간단히 알아보도록하자.
이게 회전이란 것이다. 만약 축 노드의 오른쪽에 회전 노드 가 존재한다면( 왼쪽 그림 ) 왼쪽회전이 가능하고, 만약 축 노드의 왼쪽에 회전 노드가 존재한다면 ( 오른쪽 그림) 반대로 오른쪽 회전이 가능하다. 결과는 설명 안해도 그림으로 충분히 이해가 가겠지만 수도코드로 쓰자면,
// left rotation
axis->rightChild = body->leftChild
body->leftChild = axis
axis->parent = body
// right rotation
axis->leftChild = body->rightChild
body->righChild = axis
axis->parent = body
이러하다. (물론 실제 코드에서는 부모노드 까지 고려해서 코딩을 해야한다) . 이제 대충 회전이 뭔지 알았으니 삽입/ 삭제에 대한 문제 해결법을 알아보자.
[삽입]
이제 삽입시 발생할수 있는 케이스를 나눌건데, 어떻게 나눌거냐하면, 삽입하려는 노드의 부모를 P, 그리고 그 형제를 S로 놓고 나올수있는 색깔별로 케이스를 나눌것이다.
그래. 이런식으로 놓고 나누자는것이다. 어쨋든 일단은 레드 블랙 트리의 다섯가지 법칙에 입각하여, 나올수 없는 케이스부터 생각해보자.
( A와 C는 아래 나올 case 4 의 하위 케이스를 나눌 때 쓸것이다. )
* null 노드를 NIL로 실제 메모리상에 존재하는 리프노드는 리프노드라 부르겠다.
[ 나올수 없는 케이스 ]
invalid case 1 P: Red, S:Black ( not NIL )
invalid case 2 P: Black, S:NIL
이 두경우는 절대 나올수가없다. 삽입이란 것은 리프노드 아래에 삽입함을 의미한다, 즉 부모가 레드인데 부모의 형제가 블랙이란것 자체가 이미 블랙의 갯수가 안맞는다는 것이고( case 2도 마찬가지이다 ) , 5번 법칙을 위배하는 것이기에 나올수 있는 형태가아니다.
아마 여기서 이런 의문이 들수도 있다. 아니 우리는 지금 S 노드 아래에 어떤 노드들이 있는지도 모르고, P의 다른 자식노드도 모르고, A노드 위에도 어떤 노드들이 있는지도 모르는데 어떻게 그걸 확정하느냐? 란 생각을 말이다. 좀 생각을 해보자. 과연 S의 자식 노드나 P의 다른 자식노드가 C노드부터 루트노드 경로까지의 부족한 블랙노드 하나를 채워줄수있을까? A노드 아래부터 틀어진 블랙노드의 갯수를 과연 A의 위에 존재하는 노드가 해결해줄수있을까? 둘다 불가능하다.
[ 나올수 있는 케이스 ]
case 1 P:Black, S:Red
case 2 P:Black, S:Black
case 3 P:Red, S:Red
case 4 P:Red, S:NIL
위 네가지 케이스가 나올수있는 케이스이다. 우선 가장 해결법이 쉬운(?) 케이스1, 2 부터 살펴보자. 아니 사실 쉬운게 아니라 어떠한 처리도 필요가없다. 일단은 나올수 있는 케이스라함은 블랙 노드 갯수에는 문제가 없다는 것이므로, 레드노드가 연달아 나올지를 검사해야하는데, P 노드가 블랙이므로 그럴 가능성조차없다. 그래서 이때는 별도의 처리가 불필요하다.
이번엔 케이스 3을 봐보자.
P: 2500, S : 1500, C : 3000, A : 2000
케이스 3의 경우 위와같이 P와 S를 블랙으로 칠하고 A를 레드로 칠하면된다. 하위 노드에 각각 하나씩 블랙을 칠해 늘어난 블랙을 상위 노드가 레드로 칠해 감소시킨것이다. 그리고 당연하지만 A노드의 경우 자식노드인 P와 S가 레드노드였기 때문에 레드노드일 가능성은 없다.
케이스 4의 경우는 나머지 케이스보다 조금 더 복잡하다. 일단 두개의 하위케이스로 나뉜다.
sub case 1 : P는 A의 왼쪽 자식이고 C는 P의 왼쪽 자식 ( left-left )
sub case 2 : P는 A의 왼쪽 자식이고 C는 P의 오른쪽 자식 ( left - right )
오른쪽 방향까지 고려하면 케이스가 두개 더 늘어나는데 어차피 처리방식이야 회전방향만 바뀔뿐이니 이건 알아서 해결하도록하자. 어쨋든 이 하위 두 케이스에 대해 어떻게 처리하나면,
P: 400, S : NIL, C : 300, A : 500
case 1 의 경우는 위와같이 P를 A에 대하여 오른쪽 회전시킨후 P의 색을 Black으로 A의 색을 Red로 바꾸고
P: 400, S : NIL, C : 450, A : 500
case 2의 경우는 위와같이 C를 P에 대하여 왼쪽회전시켜 문제를 case 1으로 바꾼후 case 1의 해결법 대로 해결한다. 수도코드를 쓰자면 이렇다.
if left-right case
rotate c about p to left
end if
p's color = black
a's color = red
rotate p about a to right
이렇게 삽입에 대한건 끝났고, 이제 삭제에 대해 알아보도록하자.
참고로 루트노드나, 루트노드의 자식으로 삽입시에는 별도의 처리가 필요없으니 예외처리를 하여 구현하도록하자.
[ 삭제 ]
삭제에 대해서도 케이스를 나눌건데, 요번엔 이렇게
놓도록하자. P가 이번에는 삭제노드이고 C는 P를 대체할 노드이다, 대체노드를 고르는 방법은 표준트리삭제방법과 같이, 삭제노드의 왼쪽 혹은 오른쪽 서브트리로 들어가 왼쪽의 경우는 가장 오른쪽의 리프노드로, 오른쪽의 경우는 가장 왼쪽의 리프노드로 고를것이다. ( 여기서는 왼쪽으로 들어가 고르는 방법을 사용할 것이고 삭제 방법은 케이스 마다 다르겠지만, 어떠한 케이스던지 일단은 표준트리삭제 방법에따라 노드를 삭제하고, 그후 조정을 통해 레드블랙 트리의 법칙을 맞춰가는 형식으로 구성할것이다.)
그럼 삭제 도 마찬가지로 케이스를 나눠보도록하자. 이번엔 P와 C의 관계부터 따질것이다.
case 1 P:Red, C:Red
case 2 P:Red, C:Black or NIL
case 3 P:Black, C:Red
case 4 P:Black, C:Black or NIL
* 만약 C가 NIL 이라면 P는 리프노드이다. 왜냐하면 표준트리삭제 에 따라 찾는 대상은 NIL 이아니라 실제 메모리에 존재하는 노드이다, 즉 C가 NIL인것은 왼쪽 오른쪽 둘다 대체할 노드가 없어 어쩔수없이 null 값을 넣은 경우일 뿐이다.
첫번쨰 케이스를보자. 문제가 있을까? 없다. 레드를 놓고 그 자리에 레드를 놓는다는것은 블랙에는 아무 영향이 없다는 것이다. 그렇기에 이 케이스의경우 별도의 처리가 필요없다.
케이스 2는 나중에 보도록하고, 케이스 3을 봐보도록하자. 문제가 있을까? 있다. 블랙을 대체한 것이 레드이기때문이다. 즉 블랙이 하나 줄어든 상태이다. 하지만 사실 이 케이스의 경우 해결법은 매우 간단하다. 그냥 대체한 레드를 블랙으로 칠하면된다. 레드를 어디서 빼왔든간에 문제가 될 경우는 없다 왜냐하면 대체한 노드의 경우 총 세 가지 경우가 있을텐데, 첫번째는 왼쪽에서 가장 오른쪽에 있는 리프노드, 두번째는 리프노드가 없어 대신한 왼쪽 자식노드, 세번째는 왼쪽 노드자체가 없어 오른쪽 자식노드인 경우인데 각 경우별로 생각을 해보면 알겠지만 문제될 경우가 없다. 그리고 여기서 대체한 노드를 삭제노드의 색으로 칠했듯 다른 모든 케이스에서도 대체한 노드를 삭제노드의 색으로 칠할것이다( 기본 삭제 동작이다 ).
그럼 이제 케이스 4를 보도록하자. 케이스 2는 4에 대한 해결법을 필요해서 4부터 설명해야한다. 4의 경우도 마찬가지로 하위케이스로 나뉘게된다.
sub case 1 : S가 A의 오른쪽 자식이고 블랙노드이고 자식노드중 레드노드를 적어도 하나를 포함한경우
sub case 2 : S가 A의 오른쪽 자식이고 블랙노드이고 자식노드 둘다 블랙노드인경우
sub case 2 : S가 A의 오른쪽 자식이고 레드노드인 경우( P가 블랙이므로 S의 자식노드는 4번과 5번 법칙에 따라 무조건 블랙노드 두개 )
글로는 햇갈릴수 있으니 그림을 봐보도록하자.
[sub case 1]
P = 11, S = 13, K = 14 ( 적어도 하나 )
* 여기서는 A가 레드 노드이지만 블랙 노드일 가능성도있다
[sub case 2]
P= 1, S = 3, K1 = NIL, K2 = NIL
[sub case 3]
P = 6, S = 10, K1 = 9, K2 = 11 ( 무조건 두개의 블랙 노드를 자식으로 가진다 )
이제 서브케이스가 각자 어떤 모습인지 정확히 알았을 것이다. 하지만 그전에 알아야될게, 더블 블랙이라는 개념이다. 아까 말했듯이 일단은 대체노드를 삭제노드의 색으로 칠할것이다, 그런데 현재 케이스의 경우 P도 블랙이고 C도 블랙이다. 즉 C에 블랙을 한번 덧칠해야되는 상황이 생기는데, 이 상황을 더블블랙이라고한다. 그리고 더블블랙이 발생했다함은 블랙의 갯수가 하나 모자르다는 뜻이다. 그래서 블랙의 자리를 채우기 위해 여기서도 회전이라는 테크닉이 이용된다.
이제 대충 감을 잡았을테니 걍 간단하게 수도코드나 쓰겠다. 사진찍고하기 너무 귀찮다..
[ a solution for the sub case 1]
// 삽입때 left-right 케이스에서 처리한것과 똑같다
if K is the left Child of S
K's color = BLACK
S's color = RED
rotate K about S to right
end if
K's color = BLACK
S's color = A's color // 이부분을 주의하자. A는 Red일수도 Black 일수도있다
A's color = BLACK // 이부분에서 더블블랙을 신경쓸 필요는 없다.
rotate S about A to left
[ a solution for the sub case 2]
S'color = RED
if A is RED
A's color = BLACK
else
// 만약 A가 애초에 블랙이었다면 더블블랙이 발생한것이므로
// 재귀하여 더블블랙을 처리한다.
recursive the double black proc
end if
재귀의 구조를 써서 처리하는게 가장 깔끔할것이다. 그리고 이 더블블랙이란건 루트노드에서는 아무 의미가 없는 소리이므로 재귀는 최대 루트노드까지 가게될것이다. 루트 노드에 도달했다면 블랙을 칠하고 끝내면된다.
[ a solution for the sub case 3 ]
S's color = BLACK
K1's color = RED // S의 왼쪽자식이다
rotate S about A to left
이 케이스의 경우 P가 블랙노드고 S가 레드이기 때문에 S의 부모인 A는 무조건 블랙일것이다. 그렇기 때문에 A에 대한 색을 칠하지 않아도된다. (사실 안하는게 좋다. 나의 경우 처음에 실수로 블랙을 칠했다가 그것때문에 버그를 발견 못했었다..)
대충 설명한듯 싶지만 이렇게 케이스4도 끝나게됬다. 남은건 케이스 3과 루트노드를 삭제할때분이다. 이부분에 대해서는 약간 꼼수같이 처리해서.. 사실 좋은 방식인지는 모르겠으나 일단 설명은 하겠다.
케이스 2의 경우 삭제되는것은 레드노드이다, 그리고 블랙노드가 대체되는데 이경우에도 당연히 그 블랙노드를 레드노드로 칠하게 될것이고, 그래서 특정 라인에 블랙 노드가 부족하게될것이다. 그래서 난 이걸 어떻게 처리할까 고민을하다가.. 결국 실제로는 삭제 대상인 레드노드를 삭제하는게 아니라 레드노드에 대체노드인 블랙노드의 값을 복사받은후 그 블랙노드를 삭제하는 식으로 처리하기로했다. 즉 블랙노드를 삭제 대상으로 바꿔 케이스 2를 다른 케이스( 3 혹은 4 )로 바꾼것이다. 루트노드도 똑같이 처리했다, 루트노드의 경우는 문제가 부모가 없기때문에 형제가 없다. 그래서 루트노드의 경우도 똑같이 대체노드를 삭제한다.
사실 꼼수라고 하긴했는데, 내가 참고한
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 요 사이트도 똑같이 처리하고있지 않나 예상은 하는중이다. 렌더링 되는게 보면 노드가 실제로 바뀌는게 아니라 대체노드의 값을 복사받는 형태이다.
어쨋든 이로서 지랄맞은 레드블랙 트리에 대한 포스팅을 끝내도록하겠다. 누군가 이 글을 읽는 이가 있다면 이글을 한번에 이해하여 나처럼 인터넷 이곳 저곳 뒤져가며 쌩고생하지 말기를 바란다..
■ 구현 ( 헤더 )
[RBNode.h]
#pragma once
enum COLOR { BLACK, RED } ;
typedef int KEY;
struct RBNode
{
KEY key;
COLOR color;
RBNode* parent;
RBNode* leftChild;
RBNode* rightChild;
};
|
[RBTree.h]
#pragma once
#include "RBNode.h"
typedef unsigned int SIZE;
class RBTree
{
private:
const KEY SPECIALKEY = -1;
private:
RBNode* root = nullptr;
SIZE size = 0;
private:
bool IsBlackNode(const RBNode* node);
private:
void RotateToRight(RBNode* child);
void RotateToLeft(RBNode* child);
RBNode* FindRightLeafNode(RBNode* node);
RBNode* FindSubstitute(RBNode* delNode);
private:
RBNode* CreateNode(const KEY& key, const COLOR& color,
RBNode* parent, RBNode* leftChild, RBNode* rightChild);
void FreeNode(RBNode*& node);
private:
void BalanceNodes_Insertion(RBNode* newNode);
void BalanceNodes_Deletion(RBNode* subsNode, RBNode* parent);
void DeleteNodeInStd(RBNode* delNode, RBNode* subsNode);
public:
bool Insert(const KEY& key);
bool Delete(const KEY& key);
RBNode* FindNode(const KEY& key, RBNode** prevNode);
void PrintSize() const;
void PrintInBFS() const;
void Clear(RBNode* node);
private:
RBTree();
~RBTree();
public:
static RBTree* Create(const KEY& key);
void Release();
};
|
■ 구현 ( 코드 )
[RBTree.cpp]
#include <iostream>
#include <assert.h>
#include <list>
#include "RBTree.h"
using namespace std;
bool RBTree::IsBlackNode(const RBNode * node)
{
if (!node || node->color == BLACK)
return true;
return false;
}
void RBTree::RotateToRight(RBNode* child)
{
if (!child || !child->parent)
{
_ASSERT(0);
return;
}
RBNode* parent = child->parent;
RBNode* child_rightChild = child->rightChild;
child->rightChild = child->parent;
child->parent = child->parent->parent;
parent->leftChild = child_rightChild;
if (parent->leftChild)
{
parent->leftChild->parent = parent;
}
if (parent->parent)
{
if (parent->parent->leftChild == parent)
{
parent->parent->leftChild = child;
}
else
{
parent->parent->rightChild = child;
}
}
parent->parent = child;
if (!child->parent)
{
this->root = child;
this->root->color = BLACK;
}
}
void RBTree::RotateToLeft(RBNode* child)
{
if (!child || !child->parent)
{
_ASSERT(0);
return;
}
RBNode* parent = child->parent;
RBNode* child_leftChild = child->leftChild;
child->leftChild = child->parent;
child->parent = child->parent->parent;
parent->rightChild = child_leftChild;
if (parent->rightChild)
{
parent->rightChild->parent = parent;
}
if (parent->parent)
{
if (parent->parent->leftChild == parent)
{
parent->parent->leftChild = child;
}
else
{
parent->parent->rightChild = child;
}
}
parent->parent = child;
if (!child->parent)
{
this->root = child;
this->root->color = BLACK;
}
}
RBNode * RBTree::FindRightLeafNode(RBNode * node)
{
RBNode* pNode = node;
while (pNode->rightChild)
{
pNode = pNode->rightChild;
}
return pNode;
}
RBNode * RBTree::FindSubstitute(RBNode * delNode)
{
RBNode* subsNode = nullptr;
if (delNode->leftChild)
{
// 오른쪽 단말노드가 없으면 delNode->leftChild 을 그대로 반환함
subsNode = FindRightLeafNode(delNode->leftChild);
}
else
{
subsNode = delNode->rightChild;
}
return subsNode;
}
RBNode * RBTree::CreateNode(const KEY & key, const COLOR & color,
RBNode * parent, RBNode * leftChild, RBNode * rightChild)
{
RBNode* node = new RBNode;
node->key = key;
node->color = color;
node->parent = parent;
node->leftChild = leftChild;
node->rightChild = rightChild;
this->size++;
return node;
}
void RBTree::FreeNode(RBNode *& node)
{
if (node)
{
delete node;
node = nullptr;
this->size--;
if (this->size < 0)
{
this->size = 0;
_ASSERT(0);
}
}
}
void RBTree::BalanceNodes_Insertion(RBNode * newNode)
{
// 루트노드인 경우는 무조건 블랙을 칠하고 종료
if (!newNode->parent)
{
newNode->color = BLACK;
return;
}
COLOR& parentCol = newNode->parent->color;
COLOR siblingCol = RED;
RBNode*& parent = newNode->parent;
RBNode*& ancestor = newNode->parent->parent;
/* 삽입하는 노드의 부모 컬러가 Black인
경우는 별도의 처리가 필요없다.*/
if (parentCol == BLACK)
return;
/* 조상이 없는 경우는 루트노드를
삽입 노드의 부모로 가질때 뿐이다. 이때도
별도의 처리는 필요가없다*/
if (!ancestor)
return;
// 부모가 조상의 왼쪽
if (ancestor->leftChild == parent)
{
if (IsBlackNode(ancestor->rightChild))
{
siblingCol = BLACK;
}
// 부모 Red - 친척 Red
if (siblingCol == RED)
{
parent->color = BLACK;
ancestor->rightChild->color = BLACK;
ancestor->color = RED;
if (!ancestor->parent)
{
ancestor->color = BLACK;
}
}
// 부모 Red - 친척 Black
else
{
if (parent->rightChild == newNode)
{
RotateToLeft(newNode);
}
parent->color = BLACK;
parent->parent->color = RED;
RotateToRight(parent);
}
}
// 부모가 조상의 오른쪽
else
{
if (IsBlackNode(ancestor->leftChild))
{
siblingCol = BLACK;
}
// 부모 Red - 친척 Red
if (siblingCol == RED)
{
parent->color = BLACK;
ancestor->leftChild->color = BLACK;
ancestor->color = RED;
if (!ancestor->parent)
{
ancestor->color = BLACK;
}
}
// 부모 Red - 친척 Black
else
{
if (parent->leftChild == newNode)
{
RotateToRight(newNode);
}
parent->color = BLACK;
parent->parent->color = RED;
RotateToLeft(parent);
}
}
}
void RBTree::BalanceNodes_Deletion(RBNode * subsNode, RBNode * parent)
{
// 루트 노드라면 검은색을 칠하고 종료
if (!parent)
{
subsNode->color = BLACK;
return;
}
if (parent->leftChild == subsNode)
{
if (IsBlackNode(parent->rightChild))
{
// 두 자식다 BlackNode
if(IsBlackNode(parent->rightChild->leftChild) && IsBlackNode(parent->rightChild->rightChild))
{
parent->rightChild->color = RED;
if (IsBlackNode(parent))
{
BalanceNodes_Deletion(parent, parent->parent);
}
else
{
parent->color = BLACK;
}
}
else
{
// 왼쪽 자식이 RedNode일때는 오른쪽으로 돌려 준다
if (!IsBlackNode(parent->rightChild->leftChild))
{
parent->rightChild->leftChild->color = BLACK;
parent->rightChild->color = RED;
RotateToRight(parent->rightChild->leftChild);
}
parent->rightChild->color = parent->color;
parent->color = BLACK;
parent->rightChild->rightChild->color = BLACK;
RotateToLeft(parent->rightChild);
}
}
else
{
parent->rightChild->color = BLACK;
parent->rightChild->leftChild->color = RED;
RotateToLeft(parent->rightChild);
}
}
else
{
if (IsBlackNode(parent->leftChild))
{
// 두 자식다 BlackNode
if (IsBlackNode(parent->leftChild->leftChild) && IsBlackNode(parent->leftChild->rightChild))
{
parent->leftChild->color = RED;
if (IsBlackNode(parent))
{
BalanceNodes_Deletion(parent, parent->parent);
}
else
{
parent->color = BLACK;
}
}
else
{
// 오른쪽 자식이 RedNode일때는 왼쪽으로 돌려 준다
if (!IsBlackNode(parent->leftChild->rightChild))
{
parent->leftChild->rightChild->color = BLACK;
parent->leftChild->color = RED;
RotateToLeft(parent->leftChild->rightChild);
}
parent->leftChild->color = parent->color;
parent->color = BLACK;
parent->leftChild->leftChild->color = BLACK;
RotateToRight(parent->leftChild);
}
}
else
{
parent->leftChild->color = BLACK;
parent->leftChild->rightChild->color = RED;
RotateToLeft(parent->leftChild);
}
}
}
void RBTree::DeleteNodeInStd(RBNode * delNode, RBNode * subsNode)
{
RBNode* rightChildParent = nullptr;
if (delNode->leftChild)
{
// 대체할 노드가 단말 노드일때
if (subsNode != delNode->leftChild)
{
subsNode->parent->rightChild = nullptr;
subsNode->leftChild = delNode->leftChild;
}
subsNode->parent = delNode->parent;
subsNode->rightChild = delNode->rightChild;
rightChildParent = subsNode;
}
else
{
rightChildParent = delNode->parent;
}
if (delNode->rightChild)
{
delNode->rightChild->parent = rightChildParent;
}
if (delNode->parent)
{
if (delNode->parent->leftChild == delNode)
{
delNode->parent->leftChild = subsNode;
}
else
{
delNode->parent->rightChild = subsNode;
}
}
if (!delNode->parent)
{
this->root = subsNode;
}
FreeNode(delNode);
}
bool RBTree::Insert(const KEY & key)
{
if (key == SPECIALKEY)
return false;
RBNode* prevNode = nullptr;
RBNode* node = FindNode(key, &prevNode);
if (node)
return false;
if (prevNode->key > key)
{
prevNode->leftChild = CreateNode(key, RED, prevNode, nullptr, nullptr);
BalanceNodes_Insertion(prevNode->leftChild);
}
else
{
prevNode->rightChild = CreateNode(key, RED, prevNode, nullptr, nullptr);
BalanceNodes_Insertion(prevNode->rightChild);
}
return true;
}
bool RBTree::Delete(const KEY & key)
{
RBNode* prevNode = nullptr;
RBNode* delNode = FindNode(key, &prevNode);
if (!delNode)
return false;
/* NOTE :
1. Black 노드가 삭제됬다함은 루트노드가 아니라면 삭제된 노드의 형제 노드가
무조건 존재함을 의미한다.즉 Black 삭제시에 형제노드의 존재여부를 점검할
필요가없다.
2. 위와 같은 이유로 삭제노드에 대한 대체노드가 Black 이라면 해당 노드는
왼쪽 서브트리에서 얻어온 노드이다.
3. 부모가 Red인 경우 Black 부모를 꼭 가지며, 자식은 없거나 혹은 Black 노드를
두개 이상을 보유하고있다.
4. 만약 대체한 노드가 Null-Leaf node라면 해당 노드는 오른쪽 서브트리에서 얻어
온 노드이다. 그러므로 삭제노드가 Red노드라면 별도의 처리가 필요없다.*/
RBNode* subsNode = nullptr;
while (true)
{
subsNode = FindSubstitute(delNode);
if (!IsBlackNode(delNode))
{
// 삭제노드 Red - 대체노드 Red
if (!IsBlackNode(subsNode))
{
DeleteNodeInStd(delNode, subsNode);
break;
}
// 삭제노드 Red - 대체노드 Black
else
{
if (!subsNode)
{
DeleteNodeInStd(delNode, subsNode);
break;
}
else
{
/* subs 노드가 존재하는 Black
노드일 경우에는 대체노드를
삭제하도록 유도.*/
delNode->key = subsNode->key;
delNode = subsNode;
}
}
}
else
{
// 삭제노드 Black - 대체노드 Red
if (!IsBlackNode(subsNode))
{
subsNode->color = BLACK;
DeleteNodeInStd(delNode, subsNode);
break;
}
// 삭제노드 Black - 대체노드 Black
else
{
if (!delNode->parent)
{
// 루트노드가 단말노드면 그냥 삭제
if (!subsNode)
{
DeleteNodeInStd(delNode, subsNode);
break;
}
else
{
/* 단말노드가 아니면 대체 노드를
삭제하도록 유도*/
delNode->key = subsNode->key;
delNode = subsNode;
}
}
else
{
RBNode* parent = delNode->parent;
DeleteNodeInStd(delNode, subsNode);
BalanceNodes_Deletion(subsNode, parent);
break;
}
}
}
}
return true;
}
RBNode * RBTree::FindNode(const KEY & key, RBNode ** prevNode)
{
RBNode* node = this->root;
while (node)
{
if (node->key == key)
{
return node;
}
if (node->key > key)
{
*prevNode = node;
node = node->leftChild;
}
else
{
*prevNode = node;
node = node->rightChild;
}
}
return nullptr;
}
void RBTree::PrintSize() const
{
cout << "size : " << this->size << endl;
}
void RBTree::PrintInBFS() const
{
if (!this->root)
return;
cout << "::RBTREE::" << endl;
list<RBNode*> nodeQueue;
nodeQueue.push_back(this->root);
while (nodeQueue.size())
{
RBNode* curNode = nodeQueue.front();
nodeQueue.pop_front();
KEY parentKey = SPECIALKEY;
KEY leftChildKey = SPECIALKEY;
KEY rightChildKey = SPECIALKEY;
if (curNode->parent)
parentKey = curNode->parent->key;
if (curNode->leftChild)
leftChildKey = curNode->leftChild->key;
if (curNode->rightChild)
rightChildKey = curNode->rightChild->key;
if (curNode->color == BLACK)
{
cout << "( " << curNode->key << ", BLACK )"
<< " parent : "<< parentKey
<< " leftChild : "<< leftChildKey
<< " rightChild : " << rightChildKey << endl;
}
else
{
cout << "( " << curNode->key << ", RED )"
<< " parent : " << parentKey
<< " leftChild : " << leftChildKey
<< " rightChild : " << rightChildKey << endl;
}
if (curNode->leftChild)
{
nodeQueue.push_back(curNode->leftChild);
}
if (curNode->rightChild)
{
nodeQueue.push_back(curNode->rightChild);
}
}
}
void RBTree::Clear(RBNode * node)
{
if (!node)
return;
Clear(node->leftChild);
Clear(node->rightChild);
FreeNode(node);
}
RBTree::RBTree()
{
}
RBTree::~RBTree()
{
}
RBTree * RBTree::Create(const KEY& key)
{
RBTree* tree = new RBTree;
tree->Clear(tree->root);
tree->root = tree->CreateNode(key, BLACK, nullptr, nullptr, nullptr);
return tree;
}
void RBTree::Release()
{
Clear(this->root);
delete this;
}
|
■ 실행 결과
#include "RBTree.h"
int main()
{
RBTree* tree = RBTree::Create(10);
tree->Insert(20);
tree->Insert(30);
tree->Insert(40);
tree->Insert(50);
tree->Insert(60);
tree->Insert(70);
tree->PrintInBFS();
tree->Delete(10);
tree->PrintInBFS();
tree->Delete(50);
tree->PrintInBFS();
tree->Delete(60);
tree->PrintInBFS();
tree->Delete(70);
tree->PrintInBFS();
tree->Delete(30);
tree->PrintInBFS();
tree->Release();
return 0;
}
|
■ 소스 코드
댓글 없음:
댓글 쓰기