소개
빨간색과 검은색 노드로 이루어진 균형 이진 트리
이진트리가 편향되어 O(n)의 탐색효율을 가지게 되는것을 방지한다. O(logn)
탐색은 빠르나 삽입, 삭제는 다소 느릴 수 있다. (Rebalance 때문)
조건
1. 모든 노드는 빨간색 혹은 검은색의 색상을 가진다.
2. 루트 노드는 검은색이다.
3. 단말 노드는 검은색이다.
4. 빨간색 노드의 자식들은 모두 검은색이다 (검은 노드의 자식이 빨간색일 필요는 없다.)
5. 루트노드에서 단말노드까지의 검은색 노드의 수는 동일하다.
NIL 노드란 ?
검은색으로 생각하는 더미노드로 알고리즘의 구현을 편하게 해준다.
3번의 경우를 만족시킬 수도 있고, 다양한 예외처리에 사용하기 편하다.
구현
Color Type
노드의 색상을 나타내는 열거형 (enum)
Node
stPair - Key와 Value의 Pair
pParent - 부모 노드를 가리키는 포인터
pLchild - 왼쪽 자식 노드를 가리키는 포인터
pRchild - 오른쪽 자식 노드를 가리키는 포인터
color - 노드의 색상 타입
Member Variable
m_pRoot - 루트 노드를 가리키는 포인터
m_iCurCount - 현재 노드의 갯수
m_Nil - Nil 노드
Member Functions
GetSuccessor - 중위후속자를 리턴해줌 (중위순회 했을때 _pNode 다음의 노드를 리턴해준다.)
GetPredecessor - 중위선행자를 리턴해줌 (중위 순회 했을때 _pNode 이전의 노드를 리턴해준다.)
DeleteNode - iterator에서 Erase를 위해 사용할 내부 삭제 함수
Rotate_Right - 우회전 함수
Rotate_Left - 좌회전 함수
ReBalance : 데이터의 삽입시 균형이 깨지는 경우 균형을 맞춰준다. (위의 레드블랙 트리의 조건을 만족하지 못할 경우)
ReBalance_Delete : 데이터의 삭제시 균형이 깨지는 경우 균형을 맞춰준다. (위의 레드블랙 트리의 조건을 만족하지 못할 경우)
Member Functions
erase - iterator를 넣어주면 iterator 가 가리키고 있는 노드를 지워준다.
find - key 값으로 key를 가지는 노드를 가리키는 iterator를 반환해준다.
begin - 맨 처음 노드를 가리키는 iterator를 반환해준다.
end - 맨 마지막 노드의 다음을 가리키는 iterator를 반환해준다.
삽입
1. 이진트리의 삽입 처럼 좌우의 데이터를 비교하며 새로운 노드를 삽입해준다. (NIl 노드가 나올때 까지 탐색을 진행해준다.)
2. 노드의 삽입이 끝나면 Rebalance 함수로 깨진 레드블랙 트리의 균형을 맞춰준다.
1) 조건 4를 만족하지 않을 경우 (나도 Red 노드 부모도 Red 노드 인 경우)
Rebalance(tRBTNode<T1, T2>* _pPivot);
=> 나의 부모 노드가 할아버지 노드의 왼쪽 자식일 때
=> case 1 : 삼촌이 Red 노드 였을 경우
- 부모와 삼촌을 Black 노드로 바꾸고, 할아버지를 Red 노드로 바꿔준다.
=> case 2 : 삼촌이 Black 노드이고 내가 부모의 오른쪽 자식이라면 : Rotate_Left(_pPivot);
- 내 기준으로 왼쪽 회전을 해준다. (case3 으로 가게됨)
=> case 3 : 삼촌이 Black 노드이고 내가 부모의 왼쪽 자식이라면
위의 과정을 트리의 조건이 만족할 때 까지 진행해준다.
나의 부모 노드기 할아버지 노드의 왼쪽 자식일 때
- 부모를 Black 노드로, 할아버지를 Red노드로 바꿔주고, 할아버지 기준으로 오른쪽 회전을 해준다 : Rotate_Right(_pPivot->pParent->pParent);
위의 경우 참고
나의 부모 노드가 할아버지의 오른쪽 자식일 때
case 1 : 삼촌이 Red 노드 였을 경우
- 부모와 삼촌을 Black 노드로 바꾸고, 할아버지를 Red 노드로 바꿔준다.
case 2 : 삼촌이 Black 노드이고 내가 부모의 오른쪽 자식이라면
- 내 기준으로 오른쪽 회전을 해준다 (case3 으로 가게됨) : Rotate_Right(_pPivot);
case 3 : 삼촌이 Black 노드이고 내가 부모의 왼쪽 자식이라면
- 부모를 Black 노드로, 할아버지를 Red노드로 바꿔주고, 할아버지 기준으로 왼쪽 회전을 해준다 : Rotate_Left(_pPivot->pParent->pParent);
위의 과정을 트리의 조건이 만족할 때 까지 진행해준다.
삭제
Red 노드를 삭제할 경우 간단한 트리 예외처리만 해주면 된다.
하지만 블랙 노드를 지울경우는 조건 5번을 만족하지 않으므로 예외처리를 해줘야한다.
ReBalance_Delete(tRBTNode<T1, T2>* _pDB)
=> 부모의 왼쪽일 경우
=> case 1 : 형제 노드가 Red노드 일 경우
- 형제 노드를 Black 노드로 바꾸고 부모노드를 Red로 바꾼다. 그 후 부모기준으로 좌회전 한다.
=> case 2 : 형제 노드가 Black 노드이고, 자식이 모두 Black 노드일 경우
- 형제 노드만 Red 노드로 바꿔주고 이중 흑색 노드의 검은색 하나를 부모에게 전달해준다.
=> case 3 : 형제 노드가 Black 노드이고, 왼쪽 자식이 Red노드, 오른쪽 자식이 Black 노드 일 경우
- 형제 노드를 Red 노드로 바꿔주고, 형제 노드의 왼쪽 자식을 Black 노드로 바꿔준다. 그 후 형제노드 기준으로 우회전을 해준다.
=> case 4 : 형제가 Black 노드이고, 형제의 오른쪽 자식이 Red노드, 왼쪽 자식이 Black 노드 일 경우
- 형제 노드의 색깔을 부모노드의 색깔로 바꿔준다. 부모 노드와 형제노드의 오른쪽 자식을 Black 노드로 바꾼다. 그후 부모 노드 기준으로 우회전을 해준다.
위의 과정을 트리의 조건이 만족할 때 까지 진행해준다. (이중 흑색노드가 아닐 때 까지)
부모의 오른쪽일 경우
case 1 : 형제 노드가 Red노드 일 경우
- 형제 노드를 Black 노드로 바꾸고 부모노드를 Red로 바꾼다. 그 후 부모기준으로 좌회전 한다.
case 2 : 형제 노드가 Black 노드이고, 자식이 모두 Black 노드일 경우
- 형제 노드만 Red 노드로 바꿔주고 이중 흑색 노드의 검은색 하나를 부모에게 전달해준다.
case 3 : 형제 노드가 Black 노드이고, 왼쪽 자식이 Red노드, 오른쪽 자식이 Black 노드 일 경우
- 형제 노드를 Red 노드로 바꿔주고, 형제 노드의 오른쪽 자식을 Black 노드로 바꿔준다. 그 후 형제노드 기준으로 좌회전을 해준다.
case 4 : 형제가 Black 노드이고, 형제의 오른쪽 자식이 Red노드, 왼쪽 자식이 Black 노드 일 경우
- 형제 노드의 색깔을 부모노드의 색깔로 바꿔준다. 부모 노드와 형제노드의 왼쪽 자식을 Black 노드로 바꾼다. 그후 부모 노드 기준으로 우회전을 해준다.
위의 과정을 트리의 조건이 만족할 때 까지 진행해준다. (이중 흑색노드가 아닐 때 까지)
Iterator
Member Variable
m_pOwner : 순회할 트리
m_pNode : 현재 가리키고 있는 노드
Operator
- 중위후속자를 가리키는 자신을 반환해준다.
- 중위선행자를 가리키는 자신을 반환해준다.
- iterator가 가리키는 노드를 비교해준다.
소감
지금까지 구현해본 자료구조중에 가장 어려웠던 자료구조 였습니다.
구현이 까다로웠던 이유는 예외 처리가 많았고, 예외처리를 하기위해 구현해야할 내부 함수가 많아서 조금 복잡했습니다.
레드 블렉 트리를 구현해보면서 균형트리의 필요성을 느꼈고, 균형트리 (map)을 사용할 경우 삽입, 삭제시의 비효율성을 알게 되었습니다.