자료구조

[ 자료구조 ] 탐색 - 04 - 1 . 레드 블랙 트리 <회전 , 삽입>

파울로 디발자 2023. 3. 7. 23:46

[ 레드 블랙 트리 ]

[ 레드 블랙 트리 ]
이진 탐색 트리는 균형있게 자라지 못하는 경우가 대부분이다 . 이런 성장은 검색 효율을 심각하게 저하시킨다 .
레드 블랙 트리는 이를 해결하기 위한 이진 탐색 트리이다 .
해당 트리를 이해하는데 해당 사이트가 많은 도움이 되었다 . 참고하면서 공부하면 좋을것이다 .
레드 블랙 트리 시물레이터
 
이진 탐색 트리와 다른 점은 노드를 빨강 , 혹은 검정으로 표시한다는 점이다 . 
이를 구현한 구조체는 다음과 같다 .

typedef struct tagRBTNode
{
	struct tagRBTNode* Parent;
	struct tagRBTNode* Left;
	struct tagRBTNode* Right;
    
    enum { Red , Black } Color;
    
    ElementType Data;
}RBTNode;

[ 균형 유지의 비결 ]
레드 블랙 트리는 다음 규칙을 지킴으로써 균형을 유지한다 .

  • 모든 노드는 검정색 아니면 빨간색이다 .
  • 루트 노드는 검은색이다 .
  • 잎 노드는 검은색이다 .
  • 빨간 노드의 자식들은 모두 검은색이다 . 하지만 검은 노드의 자식이 빨간색일 필요는 없다 .
  • 루트 노드부터 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다 .

NIL 노드는 아무 데이터도 가지고 있지 않은 검은색 더미노드이다 .
이는 레드 블랙트리의 구현을 쉽게 하기 위해 사용한다 .
원래의 잎 노드의 색에 구애받지 않고 "잎노드는 검은색이다" 의 규칙을 지킬 수 있기 때문이다 .

[ 기본 연산 - 회전 ]

[ 회전 ]
회전은 레드 블랙 트리 연산의 기초 초식으로 , 부모 - 자식 노드의 위치를 바꾸는 연산이다 .
방향에 따라 우회전 (왼쪽 자식과 부모의 교체)과 좌회전 (오른쪽 자식과 부모의 교체)으로 나뉜다 .
 

그냥 바꾸는 것으로는 이진트리의 규칙인 왼쪽자식은 나보다 작고 오른쪽자식은 크다를 어기기에 다음 처리가 필요하다.
=>우회전시 왼쪽 자식노드의 오른쪽 자식 노드를 부모의 왼쪽  자식으로 연결한다 .
=>좌회전시 오른쪽 자식노드의 왼쪽 자식노드를 부모의 오른쪽 자식으로 연결한다 .
 
[ 구현 - 좌회전 ]

void RBT_RotateRight (RBTNode ** Root , RBTNode* Parent)
{
    RBTNode * LeftChld = Parent->Left ;
    //왼쪽 자식노드의 오른쪽 자식을 부모의 왼쪽 자식으로 등록한다.
    Parent ->Left = LeftChild->Right;
    
    //왼쪽 자식노드의 오른쪽 자식이 Nil (더미노드)가 아니라면 부모를 등록해준다
    if(LeftChld->Right != Nil )
    LeftChild->Right->Parent = Parent;
    
    //왼쪽 자식의 부모는 부모의 부모로 등록
    LeftChild->Parent = Parent -> Parent;
    
    //루트 노드라면 루트노드를 왼쪽 자식으로 변경한다 .
    if(Parent->Parent==NULL)
    (*Root) = LeftChild;
    //루트 노드가 아니라면
    else
    {
    	//왼쪽 자식 노드를 부모가 있던 곳으로 위치시킨다 (할아버지의 자식 노드)
    	//부모가 왼쪽 노드였다면
    	if(Parent == Parent -> Parent -> Left)
        Parent->Parent->Left = LeftChild;
        //부모가 우측 노드였다면
        else
        Parent->Parent->Right = LeftChild;
    }
}

[ 기본 연산 - 노드 삽입 ]

[ 삽입 ]
이진 탐색을 통해 삽입할 장소를 찾고 새 노드를 자식노드로 연결한다는 점은 이진 탐색 트리와 비슷하지만
레드 블랙 트리는 삽입 이후 무너졌을 규칙들을 살펴야 한다 .
 
레드 블랙 트리에 새 노드가 삽입되면 기본적으로 빨간색으로 칠하고 , 양쪽 자식에 NIL노드를 연결한다 .
해당 과정은 다음과 같다 .

  1. 이진 탐색을 통해 새 노드를 트리에 삽입한다 .
  2. 노드를 빨간색으로 칠하고 양쪽 자식에 NIL 노드를 연결한다 .
  3. 무너진 레드 블랙 트리의 규칙을 복구한다 .

이때 , 연결하는 NIL노드는 한개만 전역으로 생성한 후 새 노드를 생성할때마다 동일한 NIL 노드를 사용한다 .
 
[ 무너진 규칙의 복구 ]
무너진 규칙의 복구를 위해 레드 블랙 트리의 규칙을 다시 떠올리자면

  1. 모든 노드는 검정색 아니면 빨간색이다 .
  2. 루트 노드는 검은색이다 .
  3. 잎 노드는 검은색이다 .
  4. 빨간 노드의 자식들은 모두 검은색이다 . 하지만 검은 노드의 자식이 빨간색일 필요는 없다 .
  5. 루트 노드부터 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다 .

인데 , 삽입의 상황에서 신경써야 하는 규칙은 4번 . "빨간 노드의 자식들은 모두 검은색이다" 이다 .
즉 , 해당 규칙 위반 상황은 부모 노드의 색이 빨간색이라는 것을 의미한다 . (삽입 노드는 빨간색이기에)
 
이 경우 , 부모의 형제노드인 삼촌 노드에 따라 3가지 상황으로 다시 나뉜다 .

  1. 삼촌이 빨간색인경우
  2. 삼촌이 검은색인 경우 - 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우
  3. 삼촌이 검은색인 경우 - 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우

해당 상황의 해결을 위해 삼촌이 빨간색인 경우 색상의 변환을/ 삼촌이 검정색일 경우 회전을 수행한다.
 
[  규칙의 복구 - 삼촌이 빨간색일경우 ]

해당 경우 부모와 삼촌을 검은색으로 칠한다 (5번 규칙을 위해 삼촌도 칠한다) . 이후 할아버지 노드를 빨간색으로 칠한다 .
할아버지 노드를 빨간색으로 칠했기에 해당 작업으로 생긴 부작용을 다시 살펴봐야 한다 .
 
할아버지 노드를 새로 삽입한 노드로 간주하여 할아버지의 할아버지가 빨간색이라면 위의 3가지 상황을 다시 봐야한다 .
해당 확인은 부모노드가 검은색이거나 , 새로 삽입한 ( 혹은 간주하는 ) 노드가 루트 노드일때 끝이 난다 .
 
[  규칙의 복구 - 삼촌이 검정색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우 ]

해당 경우 부모노드를 좌회전 (오른쪽 자식과 부모의 위치를 교환)한다 .
이는  " 3 . 삼촌이검은색인 경우 - 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우" 로 문제의 유형을 바꾼 것이다 .
 
이후 부모노드를 새로 삽입한 노드로 간주하고 세번째 상황으로 넘어간다 . (해당 이미지에서는 B)
 
[  규칙의 복구 - 삼촌이 검정색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우 ]

해당 경우 부모노드를 검은색 , 할아버지 노드를 빨간색으로 칠한 후
할아버지 노드를 우회전(왼쪽 자식과 부모의 위치를 교환) 한다 .
여기까지의 적용으로 4번 규칙을 위배하지 않게 된다 .
 
[  구현 - 삽입 ]

void RBT_ReBuildAcfterInsert(RBTNode** Root , RBTNode* X)
{
	//4번 규칙의 위반인 경우 계속 반복한다 .
	while (X != (*Root)&& X->Parent->Color == Red)
    {
    	//부모노드가 할아버지노드의 왼쪽 자식인 경우
    	if(X->Parent==X->Parent->Parent->Left)
        {
        	//삼촌은 할아버지노드의 오른쪽 자식
        	RBTNode* Uncle =Parent->Parent->Right;
            
            //삼촌이 검정색일 경우 회전
            if(Uncle->Color==Black)
            {
            	//삽입한 노드가 부모의 오른쪽 노드일때
            	if(X==X->Parent->Right)
                {
                	X=X->Parent;
                    //좌회전
                    RBT_RotateLeft(Root,X);
                }
                //부모의 색은 검정
                X->Parent->Color=Black;
                //조부모의 색은 빨간
                X->Parent->Parent->Color=Red;
             	//우회전
                RBT_RotateRight(Root,X);
                
            }
            //삼촌이 빨간색일 경우 색의 변경
            else
            {
            	//부모와 삼촌은 검정
            	X->Parent->Color= Black;
            	Uncle->Color=Black;
                //조부모는 빨간
                X->Parent->Parent->Color=Red;
            }
        }
        //부모노드가 할아버지 노드의 오른쪽 자식인 경우
        else
        {
        	//삼촌은 할아버지노드의 왼쪽 자식
        	RBTNode* Uncle =Parent->Parent->Left;
            
            //삼촌이 검정색일 경우 회전
            if(Uncle->Color==Black)
            {
            	//삽입한 노드가 부모의 오른쪽 노드일때
            	if(X==X->Parent->Right)
                {
                	X=X->Parent;
                    //좌회전
                    RBT_RotateLeft(Root,X);
                }
                //부모의 색은 검정
                X->Parent->Color=Black;
                //조부모의 색은 빨간
                X->Parent->Parent->Color=Red;
             	//우회전
                RBT_RotateRight(Root,X);
                
            }
            //삼촌이 빨간색일 경우 색의 변경
            else
            {
            	//부모와 삼촌은 검정
            	X->Parent->Color= Black;
            	Uncle->Color=Black;
                //조부모는 빨간
                X->Parent->Parent->Color=Red;
            }
        }
        
        //루트는 항상 검은색
        (*Root)->Color = Black;
    }
}