Red-Black 트리

Red-Black 트리는 이진 탐색 트리(BST)의 한 종류로, 스스로 균형을 유지하는 트리이다. 이 트리는 이진 탐색 트리에서 발생할 수 있는 최악의 경우(한쪽으로 치우친 트리)를 개선하여, 모든 연산(삽입, 삭제, 검색)이 O(log n) 시간 복잡도를 가지도록 설계되었다.

 

 

nil 노드

nil 노드는 트리에서 존재하지 않는 자식을 나타내기 위해 사용되며, 이는 모든 리프 노드(자녀가 없는 노드)를 나타내는 데 사용된다.

Red-Black 트리에서는 nil 노드도 블랙으로 간주되며, 트리의 균형을 유지하는 데 중요한 역할을 한다.

 

Black Height

Black Height는 노드 x에서 자손 nil 노드까지의 경로에 있는 블랙 노드의 수를 의미한다. 이때 x 자신도 이 수에 포함된다.

 

 

Red-Black 트리의 다섯 가지 속성

Red-Black 트리는 다음의 다섯 가지 속성을 통해 균형을 유지한다.

1. 모든 노드는 레드 또는 블랙이다.
2. 루트 노드는 항상 블랙이다.
3. 모든 nil 노드는 블랙이다.
4. 레드 노드의 자녀들은 모두 블랙이다. (즉, 레드 노드가 연속적으로 나타날 수 없다.)
5. 모든 경로에서 리프(nil 노드)까지 블랙 노드의 수는 같다. (이 경로에서 노드 자신도 블랙 수에 포함된다.)

 

삽입 방식

• 일반적인 BST 삽입 방식으로 새 노드를 삽입한다. 삽입된 노드의 색상은 항상 레드이다.
• 위반이 발생하면, 트리의 속성을 만족시키기 위해 트리 구조를 재조정(색상변경과 회전연산)한다.
• 새로운 노드를 레드로 삽입하면, 트리의 블랙 높이에 즉시 영향을 주지 않으므로 5번 속성이 위반되지 않는다. 만약 새로운 노드를 블랙으로 삽입한다면, 해당 노드의 경로 블랙 높이가 증가하게 되어 균형이 깨질 수 있다. 이를 복구하려면 추가적인 회전 및 색상 변경이 필요해져 복잡성이 증가한다.

 

삭제 방식

• 일반적인 BST 삭제 방식으로 노드를 삭제한다. 
• 삭제하려는 노드의 자녀가 없거나 하나일 경우, 삭제되는 색상은 삭제되는 노드의 색상과 같다.
• 삭제하려는 노드의 자녀가 둘일 경우, 삭제되는 색상은 삭제되는 노드의 successor(후계자)의 색상과 같다.
• 삭제된 색상이 블랙일 경우, 2번(루트 노드는 블랙), 4번(레드 노드의 자녀는 블랙), 5번(모든 경로에서 블랙 노드 수가 동일) 속성을 위반할 수 있다.
• 위반이 발생하면, 트리의 속성을 만족시키기 위해 트리 구조를 재조정한다.

 

삭제된 색을 통한 속성 위반 여부 확인

• 레드 색상: 삭제되는 색상이 레드일 경우, 어떠한 속성도 위반되지 않는다.
• 블랙 색상: 삭제되는 색상이 블랙일 경우, 2번(루트 노드는 블랙), 4번(레드 노드의 자녀는 블랙), 5번(모든 경로에서 블랙 노드 수가 동일) 속성을 위반할 수 있다. 이 경우, 삭제된 노드를 대체한 노드에 extra black을 부여하여 문제를 해결한다.

 

Extra Black

Extra Black 상태는 노드에 블랙 색상을 추가적으로 부여한 상태를 의미한다. 이는 블랙 노드의 수를 임시로 증가시키기 위해 사용된다.

• Doubly Black: 삭제된 노드의 색상에 블랙을 두 번 추가한 상태를 의미한다. 이는 블랙 높이 불균형을 해결하기 위한 임시 상태로, 4가지 케이스가 존재한다.
  • Case 1: Doubly Black 노드가 리프인 경우, 노드를 삭제하고, 부모의 black 상태를 유지한다.
  • Case 2: Doubly Black 노드가 자식이 있을 경우, 해당 자식을 블랙으로 변경한다.
  • Case 3: Doubly Black 노드의 형제 노드가 레드인 경우, 형제 노드를 블랙으로 변경하고, 부모 노드를 레드로 변경 후 회전 연산을 수행한다.
  • Case 4: Doubly Black 노드의 형제 노드가 블랙인 경우, 형제 노드의 자식 노드가 블랙으로 되어 있는지 확인한 후 적절한 조정을 수행한다.
• Red and Black: 레드 노드에 블랙 색상을 추가적으로 부여한 상태를 의미하며, 이를 블랙으로 변경하여 문제를 해결할 수 있다.

 

RB Tree vs AVL Tree

	RB Tree	AVL Tree
삽입/삭제/검색 시간복잡도	최악에도 O(logN)
삽입/삭제 성능	AVL 트리에 비해 빠르다.	RB 트리에 비해 삽입 삭제 후에 균형을 잡는데 더 많은 비용이 소모된다.
검색 성능	AVL 트리에 비해 느리다.	더 염격한 균형 때문에 RB 트리에 비해 빠르지만 크게 차이 없다.
응용 사례	linux kernel 내부에서 사용 자바 TreeMap 구현 C++ std::map 구현	dictionary 한번 만들어 놓으면 삽입/삭제가 거의 없고 검색이 대부분인 상황에서 사용