[알고리즘] 레드블랙 트리 , RBT (Red-Black Tree)

레드블랙트리(Red Black Tree)는 자기 균형 이진 탐색 트리 구조로, 삽입과 삭제 연산 이후 레드/블랙의 색상을 사용하여 균형잡힌 정렬을 하는 이진 탐색 트리(BST)입니다.

 

RBT - https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

 

속성

• 모든 노드는 빨간색 또는 검은색을 가지고 있다.
• 루트 노드는 항상 검은색 이다.
• Leaf(NIL) 노드는 항상 검은색 이다.
• 빨강 노드의 자식은 모드 검정색이다.
• 임의의 노드에서 모든 리프노드에 이르는 경로에는 동일한 수의 검정 노드가 필요하다.

※NIL : 아무 데이터도 가지고 있지않는 더미 노드. 

특징

• 이진 탐색 트리(BST)의 한 종류
• BST의 최악의 경우 O(N)의 시간 복잡도를 개선해서 모든 경우의 시간복잡도 O(log N)을 유지
• 항상 균형을 유지하여 특정 케이스에 치우친 성능 저하가 없다.
  • 삽입,삭제 시 회전 연산을 통해 균형을 유지한다.
• Map, Set 자료구조는 RBT를 기반으로 구현되었다.

 

회전연산

삽입,삭제,탐색시 시간복잡도가 항상 O(log N)을 유지하기위해서 항상 균형잡힌 상태를 유지합니다.

해당 과정에서는 RBT의 속성을 유지하며 트리 구조를 조정하는데에는 왼쪽회전, 오른쪽 회전의 방식이 있습니다.

 

삽입

• 새 노드는 처음에 빨간색으로 삽입된다.
• 삽입 후, 트리는 RB-T 속성을 위반할 수 있으므로, 이를 수정하기 위해 재조정 및 색상 변경이 수행된다.
  • 삽입된 노드의 부모가 검정이면 트리 속성이 유지되므로 조정하지 않는다.
  • 삽입된 노드의 부모와 삼촌이 둘다 빨강일 경우
    • 부모 삼촌은 검정으로 변경
    • 조부모를 빨강으로 변경
    • 재귀적 처리를 통해 색상 조정
  • 부모가 빨강이고 삼촌이 검정일 경우
    • 회전연산을 통해 색상이 조정된다.
• 노드들은 필요에 따라 색상이 변경될 수 있으며, 회전연산을 통해 균형을 유지한다.
• BST와같이 재귀적으로 노드를 호출하며 조정된다.

 

삭제

• 삭제 노드가 레드 노드일 경우
  • 삭제 후 조정 처리가 필요없다
• 삭제 노드가 블랙 노드인 경우
  • 삭제 노드의 자리가 RBT속성을 위반하므로 추가적인 작업을 수행한다.
  • 형제가 레드일 경우
    • 부모-형제 색상 교환
    • 부모를 기준으로 회전연산
  • 형제가 블랙, 형제의 자식이 모두 블랙
    • 형제를 레드로 변경
    • 부모노드를 검정으로 변경 후 형제가 레드일 경우의 단계를 처러리
  • 형제가 블랙, 형제의 자식중 하나가 레드
    • 형제와 형제의 자식(레드)의 색상을 교환
    • 자식(레드)가 왼쪽일 경우 형제노드를 기준으로 오른쪽 회전
      • ---- 형제의 자식(레드)가 오른쪽일 경우 다음 단계부터 수행 ----
    • 부모와 형제 노드의 색상을 교환
    • 부모를 기준으로 왼쪽 회전
    • 형제노드의 오른쪽 자식을 블랙으로 변경

 

회전연산 - 왼쪽 회전

Left Rotation - https://aerimforest.tistory.com/239

 

	// Left Rotation
    void leftRotate(Node* node) {
        Node* rightNode = node->right; // 노드의 오른쪽 자식을 가져옴
        if (rightNode == nullptr) return; // 오른쪽 자식이 없으면 회전 불가

        node->right = rightNode->left; // 노드자식(오른쪽)의 왼쪽 서브트리를 노드의 오른쪽에 연결
        if (rightNode->left != nullptr) {
            rightNode->left->parent = node;
        }

        rightNode->parent = node->parent; // 노드의 부모를 노드자식(오른쪽)의 부모로 설정
        if (node->parent == nullptr) {
            root = rightNode; // 노드가 루트라면 노드자식(오른쪽)가 새 루트가 됨
        }
        else if (node == node->parent->left) {
            node->parent->left = rightNode;
        }
        else {
            node->parent->right = rightNode;
        }

        rightNode->left = node; // 노드를 노드자식(오른쪽)의 왼쪽 자식으로 설정
        node->parent = rightNode;
    }

 

 

회전연산 - 오른쪽 회전

Right Rotation - https://aerimforest.tistory.com/239

    //Right Rotation
    void rightRotate(Node* node) {
        Node* leftNode = node->left; // 노드의 왼쪽 자식을 가져옴
        if (leftNode == nullptr) return; // 왼쪽 자식이 없으면 회전 불가

        node->left = leftNode->right; // 노드 자식(왼쪽)의 오른쪽 서브트리를 노드의 왼쪽에 연결
        if (leftNode->right != nullptr) {
            leftNode->right->parent = node;
        }

        leftNode->parent = node->parent; // 노드의 부모를 노드 자식(왼쪽)의 부모로 설정
        if (node->parent == nullptr) {
            root = leftNode; // 노드가 루트라면 노드 자식(왼쪽)가 새 루트가 됨
        }
        else if (node == node->parent->left) {
            node->parent->left = leftNode;
        }
        else {
            node->parent->right = leftNode;
        }

        leftNode->right = node; // 노드를 노드 자식(왼쪽)의 오른쪽 자식으로 설정
        node->parent = leftNode;
    }