Red Black Tree (1) 개념 / 동작 방식

📚 개념

대표적인 균형 잡힌 이진 검색 트리(BinarySearchTree)

균형을 맞추기 위해 이진 검색 트리의 규칙에 맞게 모든 노드에 레드🔴 또는 블랙🖤 색상을 칠함

레드 블랙 특성

1. 루트는 블랙이다.
2. 모든 리프(NIL)는 블랙이다.
   • NIL 노드 : 자식 노드가 없을 때 자식 노드를 NIL 노드로 표기
3. 노드가 레드이면 그 자식 노드는 반드시 블랙이다. (즉, 레드 노드가 연속적으로 존재할 수 없다)
4. 자기 자신을 제외하고 임의의 노드에서 자손 NIL 노드까지 가는 경로에서 만나는 블랙 노드의 수는 같다.
   • 노드 x의 black height라고 함

➡️  4번 특성 활용해 노드 간 색 바꾸기

두 자녀 노드가 같은 색을 가질 때, 부모 노드와 자식 노드의 색을 바꿔줘도 4번 속성을 여전히 만족함

⚙️ 동작 방식

• 삽입, 삭제 연산 모두 케이스 3 / 케이스 4로 귀결되는 특징이 있음

삽입 (tree_insert)

삽입 방식은 일반적인 BST와 동일함. 삽입 후 레드 블랙 특성 위반 여부 확인 후 재조정.

⭐️ 삽입하는 노드($x$)의 색상은 항상 레드이다.

• 이유 : 4번 특성을 위반하지 않아야 하기 때문에

# Case 0 : 최초 노드 삽입
특성 위반 : 1. 루트는 블랙이다.
해결 방안 : 삽입한 노드의 색상을 블랙으로 바꿔준다.

# Case 1 : 부모 노드($p$)의 색상이 블랙일 때
특성 위반 : X

# Case 2 : 부모 노드($p$)의 색상이 레드일 때
특성 위반 : 3. 노드가 레드이면 그 자식 노드는 반드시 블랙이다.

# Case 2-1 : 부모 노드 $p$의 형제 노드 $sp$ (== 삼촌 노드)가 레드일 때
해결 방안 : $p$와 $sp$의 색상 ↔  $p^2$의 색상, 새로운 target이 조부모 노드 $p^2$가 됨. (4번 특성을 활용해 1보 후퇴)

# Case 2-2 : 삼촌 노드 $sp$가 블랙일 때 && $x$가 오른쪽 자식으로 삽입될 때
해결 방안 : 새로운 target을 부모 노드 $p$로 만들고, 새로운 target 기준으로 왼쪽 회전. 이후에는 Case 2-3 과 같은 방법으로 해결

# Case 2-3 : 삼촌 노드 $sp$가 블랙일 때 && 부모 노드 $p$의 형제 $x$가 왼쪽 자식으로 삽입될 때
해결 방안 : 조부모 $p^2$와 부모$p$의 색상 교환 후 조부모 노드를 기준으로 오른쪽 회전

삭제 (tree_erase)

삭제 방식 또한 일반적인 BST와 동일함.
일단 삭제를 한 후, 그 상태에서 RB 트리 특성을 위반하면 그 때 rebalancing / recoloring
⭐️ 어떤 색이 삭제되는지가 특성 위반 여부를 확인할 때 중요

1) 삭제하려는 노드의 (유효한 값을 가지는) 자녀가 없거나 하나라면 삭제되는 색 = 삭제되는 노드의 색
2) 삭제하려는 노드의 자녀가 둘이라면 삭제되는 색 = 삭제되는 노드의 successor의 색

# Case 1 : 삭제되는 색이 레드일 때
특성 위반 : X

# Case 2 : 삭제되는 색이 블랙일 때

# Case 2-1 : 삭제된 노드가 루트일 때
특성 위반 : 1
해결 방안 : 루트 노드를 대체하는 노드의 색상을 블랙으로 바꿈

# Case 2-2 : 삭제된 노드가 루트가 아닐 때 && target이 왼쪽 자식일 때
특성 위반 : 4
해결 방안 : 삭제한 노드의 위치를 대체하는 노드에 extra black 부여

# Case 2-2-1 : 삭제된 노드를 대체하는 노드가 red and black 노드가 되었을 때
해결 방안 : 그냥 블랙으로 바꿔버림

# Case 2-2-2 : doubly black 노드가 되었을 때

# Case 2-2-2-1 : doubly black의 형제가 레드일 때

해결 방안 : 형제 노드(D), 부모 노드(B)의 색상을 바꾸고 부모 노드 기준 왼쪽 회전. 이후 새로운 형제 노드는 target의 부모의 오른쪽 자식이 됨. 그 이후는 2-2-2-2, 2-2-2-3, 2-2-2-4 세 가지 케이스 중 하나로 해결

# Case 2-2-2-2 : doubly black의 형제가 블랙이고, 형제 노드의 모든 자식 노드가 블랙일 때
해결 방안 : target(A)과 그 형제(D)의 black을 모아 부모(B)에게 전달해서 부모가 extra black을 해결하도록 위임. 즉, 새로운 target은 부모 노드가 됨. 이후에는 2-2-2-3, 2-2-2-4 중 하나로 해결

# Case 2-2-2-3 : doubly black의 오른쪽 형제 노드가 블랙이고, 형제 노드의 왼쪽 자식 노드가 레드일 때
해결 방안 : 형제(D)와  왼쪽 자식(C) 노드 색 교체 후 형제 노드 기준 오른쪽 회전(new 형제의 오른쪽 자식이 레드가 되게). 회전 후 형제 노드가 target의 부모의 오른쪽 자식이 되도록 다시 조정. 이후에는 2-2-2-4를 적용해 해결

# Case 2-2-2-4 : doubly black 노드의 오른쪽 형제 노드가 블랙이고, 형제 노드의 오른쪽 자식 노드가 레드일 때
해결 방안 : 형제(D)는 부모(B)의 색으로, 형제의 오른쪽 자식(E)은 블랙으로, 부모(B)는 블랙으로 바꾼 후 부모를 기준으로 왼쪽으로 회전. 새로운 target은 트리의 루트.

AVL 트리는 삽입 삭제 후에 루트 노드까지 올라가서 balance factor를 비교하므로 삽입/삭제시 RB Tree가 더 빠름

AVL 트리가 균형을 더 엄격하게 잡기 때문에 검색 속도가 더 빠름