[Java] 레드 블랙 트리

본 게시글은 학부 강의 '자료구조' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다.

 

2-3 트리의 구현이 너무 복잡해..
2-3 트리를 이진 트리처럼 만들어 보는거야!!

 

 

BST에 융통성이 생긴 2-3 트리. 성능도 좋았지만 노드가 많아지면서 노드 구조가 복잡해졌다. 그러기에 경우의 수가 너무 많아지는게 문제였다.

2-노드와 3-노드를 처리해야 하고

삽입, 삭제 시 너무나도 다양한 케이스들이 존재했다.

메모리 효율성 측면에서도 항상 3개의 자식 포인터 공간이 필요했다. 그래서 2-노드일 때 하나는 낭비가 된다.

 

그래서 좀 더 나은 방법은 없을까?

 

 

---

 

 

레드 블랙 트리

• 노드에 색을 부여하여 트리의 균형을 유지
• 탐색, 삽입, 삭제 연산의 수행 시간이 각각 O(logn)을 넘지 않는 매우 효율적인 자료구조
• 일반적인 레드 블랙 트리(Intro. to Algorithms, CLRS) : 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우를 고려해야 한다는 단점, 프로그램이 복잡하고 코드길이도 증가한다.
• 좌편향 레드 블랙(LeftLeaning Red-Black, LLRB) 트리 : 삽입이나 삭제 시 고려해야 하는 경우의 수가 매우 적어 코드 길이는 일반 레드 블랙 트리 프로그램의 약 1/5
• LLRB 트리는 AVL 트리, 2-3 트리, 2-3-4 트리, 일반 레드 블랙 트리보다 우수한 성능을 가진다.
• Introduction to Algorithms(CLRS)에 소개된 RB 트리가 일반적으로 사용되며, 전문 프로그래머가 코드를 작성해도 적어도 400lines

 

 

LLRB 트리와 2-3 트리의 관계

 

LLRB 트리는 2-3 트리에서 3-노드의 두 개의 키를 두 노드로 분리 저장하고, 작은 키는 레드, 큰 키는 블랙으로 만든 형태와 같다.

 

 

 

• LLRB 트리는 개념적으로 2-3 트리와 같기 때문에 2-3 트리의 장점인 완전 균형 트리의 형태를 내포
• LLRB 트리의 노드는 블랙 또는 레드의 두 가지 색 정보를 가지며, 노드와 부모를 연결하는 link의 색은 노드의 색과 동일
• LLRB 트리에서는 link의 색을 별도로 저장 안함
• 노드 n의 왼쪽 자식은 레드이고 그 연결 link도 레드이며, n의 오른쪽 자식은 블랙이고 그 연결 link도 블랙

 

 

LLRB 트리는 이진 탐색 트리로서 아래의 네 가지 조건을 만족한다.

• 루트와 null은 블랙이다.
• 루트로부터 각 null까지 2개의 연속도니 레드 link는 없다. <연속 레드 link 규칙>
• 루트로부터 각 null까지의 경로에 있는 블랙 link 수는 모두 같다. <동일 블랙 link 수 규칙>
• 레드 link는 왼쪽으로 기울어져 있다. <레드 link 좌편향 규칙>

 

 

---

 

RedBlackTree Class

 

 

 

public clss RedBlackTree<Key extends Comparable<Key>, Value> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;
    private class Node {	// Node 클래스
        Key id;
        Value name;
        Node left, right;
        boolean color;	// 부모 link의 색
        public Node(Key k, Value V, boolean col) {	// 노드 생성자
            id = k;
            name = v;
            color = col;
            left = right = null;
        }
    }
    private boolean isEmpty() {return root == null;}
    private boolean isRed(Node n) {
        if (n == null) return false;	// null의 색은 블랙
        return (n.color == RED);
    }
	// get(), put(), deleteMin(), delete() 선언
}

public Value get(Key k) {return get(root, k);}	// 탐색 연산
public Value get(Node n, Key k) {
    if (n == null) return null;	// 탐색 실패
    int t = n.id.compareTo(k);
    if (t > 0) return get(n.left, k);	// if (k<노드 n의 id) 왼쪽 서브트리 탐색
    else if (t < 0) return get(n.right, k);	// if (k>노드 n의 id) 오른쪽 서브트리 탐색
    else return (Value) n.name;	// 탐색 성공
}

 

 

---

 

 

레드 블랙 트리의 기본 연산

 

• LLRB 트리의 삽입, 삭제 연산을 위한 기본 연산
  • rotateLeft :  노드의 오른쪽 레드 link를 왼쪽으로 옮기는 연산
  • rotateRight : 노드의 왼쪽 레드 link를 오른쪽으로 옮기는 영ㄴ산
  • flipColors : 노드의 두 link의 색이 같을 때, 둘 다 다른 색으로 바꾸는 연산
• 회전이나 색 변환 연산은 삽입과 삭제 연산을 수행하는 도중에 트리의 규칙에 어긋나는 부분을 수정하는 데 이용

 

 

rotateLeft()

private Node rotateLeft(Node n) {
    Node x = n.right;
    n.right = x.left;
    x.left = n;
    x.color = n.color;
    n.color = RED;
    return x;
}

 

 

 

 

rotateRight()

private Node rotateRight(Node n) {
    Node x = n.left;
    x.right = n;
    x.color = n.color;
    n.color = RED;
    return x;
}

 

• 색 변환 연산은 (a)에서 (b)로, 또는 (b)에서 (a)로 각각 수행될 수 있다.

 

---

 

삽입 연산

 

public void put(Key k, Value v) {
    root = put(root, k, v);
    root.color = BLACK;
}
private Node put(Node n, Key k, Value v) {
    if (n == null) return new Node(k, v, RED);	// 새로운 레드 노드 생성
    int t = k.compareTo(n.id);
    if (t < 0) n.left = put(n.left, k, v);
    else if (t > 0) n.right = put(n.right, k, v);
    else n.name = v;	// k가 트리에 있는 경우 v로 name을 갱신
    // 오른쪽 linke가 레드인 경우 바로잡는다.
    if (!isRed(n.left) && isRed(n.right)) n = rotateLeft(n);
    if (isRed(n.left) && isRed(n.left.left)) n = rotateRight(n);
    if (isRed(n.left) && isRed(n.right)) flipColors(n);
    return n;
}

 

 

 

 

---

 

 

최솟값 삭제 연산

 

루트로부터 삭제하는 노드 방향으로 레드 link를 옮겨 궁극적으로 삭제하는 노드를 레드로 만든 후에 삭제한다.

 

 

루트로부터 삭제하는 노드 방향으로 레드 link를 옮기는 과정은 트리의 조건을 위반하지 않는 상태를 유지하며 진행한다. 이를 위한 2가지 방법으로 레드 link를 왼쪽 아래로 내려 보낸다.

다만 레드 link 좌편향 규칙에 위배되는 경우가 발생할 수 있으나 이는 삭제 후에 다시 루트 방향으로 올라가면서 수정한다.

 

[Case 1]

n.left와 n.left.left가 모두 블랙이고, 동시에 n.right.left도 블랙이면, flipColors(n) 수행

 

[Case 2]

n.left와 n.left.left가 모두 블랙이고, 동시에 n.right.left가 레드이면, n.right.left의 레드 link를 왼쪽 방향으로 보낸다.

 

Case 2

 

Case 2는 다음과 같은 일련의 기본 연산을 통해 레드 link를 왼쪽 아래로 내려보낸다.

 

 

• 아래의 코드는 두 가지의 case를 모두 고려한 moveRedLeft() 메서드이다.
• Case 1과 2의 공통된 첫 연산은 flipColors
• Case 2는 3개의 연산(line 04 ~ 06)이 추가로 필요하다.

private Node moveRedLeft(Node n) {
    flipColors(n);		// case 1과 case 2
    if (isRed(n.right.left)) {	// case 2
        n.right = rotateRight(n.right);
        n = rotateLeft(n);
        flipColors(n);
    }
    return n;
}

 

 

 

moveRedLeft()를 수행하여 최소값을 갖는 노드를 삭제 올라가면서 fixup()으로 Tree 재구성

public void deleteMin() {	// 최솟값 삭제
	root = deleteMin(root);
	root.color = BLACK;
}
private Node deleteMin(Node n) {
    if (n.left == null) return null;
    if (!isRed(n.left) && !isRed(n.left.left))
    	n = moveRedLeft(n);
    n.left = deleteMin(n.left);
    return fixUp(n);
}

 

 

 

fixUp() 메서드는 레드 블랙 트리 규칙에 어긋난 부분 수정

private Node fixUp(Node n) {
    if (isRed(n.right))	n = rotateLeft(n);
    if (isRed(n.left) && isRed(n.left.left)) n = rotateRight(n);
    if (isRed(n.left) && isRed(n.right)) flipColors(n);	// put() 함수와 동일
    return n;
}

 

 

 

deleteMin() 수행 과정 : 삭제하면서 균형 유지하기

 

 

 

// 레드-블랙 트리 삭제 메소드
public void delete(Key k) {
    root = delete(root, k);
    root.color = BLACK;
}

private Node delete(Node n, Key k) {
    // 삭제할 키가 현재 노드보다 작은 경우 (왼쪽 서브트리로)
    if (k.compareTo(n.id) < 0) {
        // 왼쪽으로 이동하기 전 빨간 링크 확보
        if (!isRed(n.left) && !isRed(n.left.left))
            n = moveRedLeft(n);
        n.left = delete(n.left, k);
    }
    // 삭제할 키가 현재 노드보다 크거나 같은 경우
    else {
        // 왼쪽 자식이 빨간색이면 오른쪽으로 회전
        if (isRed(n.left))
            n = rotateRight(n);
        
        // 삭제할 노드를 찾았고 오른쪽 자식이 없는 경우
        if (k.compareTo(n.id) == 0 && (n.right == null))
            return null;
        
        // 오른쪽으로 이동하기 전 빨간 링크 확보
        if (!isRed(n.right) && !isRed(n.right.left))
            n = moveRedRight(n);
        
        // 삭제할 노드를 찾은 경우
        if (k.compareTo(n.id) == 0) {
            // 중위 후속자(successor)로 대체
            Node successor = min(n.right);
            n.name = get(n.right, successor.id);  // successor의 name 복사
            n.id = successor.id;                  // successor의 id 복사
            n.right = deleteMin(n.right);         // successor 삭제
        }
        else {
            // 오른쪽 서브트리에서 계속 탐색
            n.right = delete(n.right, k);
        }
    }
    
    // 삭제 후 레드-블랙 트리 속성 복구
    return fixUp(n);
}

 

• moveRedLeft(n) : 왼쪽으로 가기 전 빨간 링크 생성
• moveRedRight(n) : 오른쪽으로 가기 전 빨간 링크 생성

 

Top-down 방식으로 내려가면서 미리 빨간 링크를 확보한다.

삭제 후 fixUp()으로 속성을 복구하여 자동 균형을 이루도록 한다.

 

 

 

 

moveRedRight()

private Node moveRedRight(Node n) {
    flipColors(n);              // case 1과 case 2 공통 작업
    
    if (isRed(n.left.left)) {   // case 2 조건
        n = rotateRight(n);     // 오른쪽 회전
        flipColors(n);          // 색깔 다시 조정
    }
    
    return n;
}

오른쪽 자식과 그 왼쪽 자식이 모두 검은색일 때 오른쪽으로 내려가면 빨간 링크가 없어서 삭제 작업이 어려워진다.

그래서 미리 빨간 링크를 만들어서 안전하게 이동한다.

 

 

---

 

수행 시간

LLRB 트리에서 삽입과 삭제 연산은 공통적으로 루트부터 탐색을 시작하여 이파리까지 내려가고, 다시 루트까지 거슬러 올라온다.

트리를 1층 내려갈 때나 올라갈 때에 수행되는 연산은 각각 O(1) 시간 소요, 삽입과 삭제 연산의 수행 시간은 각각 트리의 높이에 비례

n개의 노드를 갖는 레드 블랙 트리의 높이 h는 2logn보다 크지 않다.

루트부터 이파리까지 블랙 link 수가 동일하므로 레드 노드가 없는 경우에는 h = logn이며, 레드 노드가 최대로 많이 트리에 있는 경우에도 레드 link가 연속해서 존재할 수 없으므로 h ≤ 2logn이다.

 

 

응용

레드 블랙 트리는 반드시 제한된 시간 내에 연산이 수행되어야 하는 경우에 매우 적합한 자료구조이다.

실제 응용 사례로른 logn 시간보다 조금이라도 지체될 경우 매우 치명적인 상황을 야기할 수 있는 항공 교통 관제(Air Traffic Control), 핵발전소의 원자로(Nuclear Reactor) 제어, 심장박동 조정장치(Pacemakers) 등에 적합하다고 볼 수 있다.

 

RB 트리는 자바의 java.util.TreeMap과 java.util.TreeSet의 기본 자료구조로 사용된다. C++의 표준 라이브러리인 map, multimap, set, multiset에도 사용되고, 리눅스(Linux) 운영체제의 스케줄러에서도 레드블랙 트리가 활용된다.