블랙레드 트리(Red-Black Tree)

🚀 들어가며

자바 TreeMap이 내부적으로 Red-Black Tree 구조로 동작하기 때문에
효율적인 데이터 관리와 정렬된 탐색 방법을 이해하기 위해 공부했습니다.

1️⃣ 블랙레드 트리란?

블랙레드 트리(Red-Black Tree)는 이진 탐색 트리(Binary Search Tree)의 일종으로 각 노드에 색상 정보를 추가하여 트리의 균형을 유지하는 자가 균형 이진 탐색 트리입니다. 노드의 색상은 "빨강(Red)" 또는 "검정(Black)"으로 구분되며 트리의 높이를 균형 있게 유지하여 최악의 경우에도 검색, 삽입, 삭제 연산이 O(log n) 시간 복잡도를 가질 수 있도록 합니다

2️⃣ 탄생 배경

블랙레드 트리는 이진 탐색 트리의 단점을 보완하기 위해 탄생했습니다.트리의 균형을 자동으로 유지할 수있는 알고리즘이 필요하게 되었는데 이는 트리의 높이를 제한하여 최악의 경우에도 효율적인 연산이 가능하도록 보장하기 위함입니다

3️⃣ 이진탐색 트리(BST)의 단점

🤣 단점

편향된 트리(Skewed Tree): 삽입 순서에 따라 트리가 한쪽으로 치우치게 될수 있습니다.
이미 정렬된 데이터를 순서대로 삽입하면 트리는 한쪽으로 길게 뻗어나가는 모양이 되며, 연결 리스트와 같은 구조가 됩니다.
최악의 경우 BST의 높이가 O(n)이 되어 검색 삽입 삭제 연산 모두에서 O(n)의 시간 복잡도가 발생할 수 있습니다.

4️⃣ 더블 레드(Double Red)?

더블 레드(Double Red) 문제는 레드블랙 트리의 빨강 노드는 연속해서 나올 수 없다 는 규칙이 깨지는 상황을 말합니다. 트리에서 삽입 연산을 수행이후 삽입된 노드와 그 부모 노드가 둘 다 빨간색일 때 발생하는 문제입니다.
"빨간색 노드의 자식 노드는 반드시 검정색이어야 합니다."

Restructuring

Restructuring: 더블 레드 문제를 해결하기 위해 트리의 구조를 변경하는 과정입니다. 주로 회전(Rotation)을 통해 트리의 노드 배치를 조정하여 균형을 맞추고, 트리의 규칙을 유지하게 됩니다. Restructuring은 삼촌 노드가 검정색일 때 사용됩니다.

Recoloring

Recoloring: 트리의 구조는 변경하지 않고 색상만 바꾸는 방법으로, 삼촌이 빨간색일 때 사용됩니다. 트리의 구조적 변화 없이 색상만 변경하여 균형을 유지합니다.

🧀 정리

블랙레드 트리는 균형 잡힌 트리구조를 유지함으로써 이진 탐색 트리의 단점을 해결하는 동시에, 다양한 응용 분야에서 사용될 수 있는 중요한 자료구조로 입니다
자바의 TreeMap이나 TreeSet은 내부적으로 블랙레드 트리를 사용합니다