레드블랙 트리 (회전과 삽입)

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 구조, 알고리즘

대상자

• *소프트웨어 개발자, 컴퓨터 과학 학생**
• 난이도: 중간 (이진 탐색 트리와 회전 개념 이해 필요)

핵심 요약

• 레드블랙 트리의 5가지 속성은 균형 유지 및 O(log N) 시간 복잡도 보장
• 1. 모든 노드는 Red/Black, 2. 루트는 Black, 3. Nil 노드는 Black, 4. Red 노드의 자식은 Black, 5. Black Height 일관
• 삽입 시 Red 노드가 부모와 연속되면 삼촌 노드 색에 따라 사례 1 (Red 삼촌) 또는 사례 2 (Black 삼촌) 처리
• 회전 (좌/우)와 색 변경을 통해 속성 위반 해결, 5번 속성 (Black Height)은 자동 유지

섹션별 세부 요약

1. 레드블랙 트리 개요

• 균형 잡힌 이진 탐색 트리로, 최악의 경우 O(log N) 시간 복잡도 유지
• 트리 균형 유지 방법: 회전 연산, 색 변경
• Nil 노드는 Black으로 표기, 리프 노드는 Nil 노드

2. 회전 연산

• 좌회전: 트리가 오른쪽으로 치우쳤을 때, 기준 노드가 왼쪽으로 이동
• 절차: 오른쪽 자식의 왼쪽 서브트리 → 기준 노드의 오른쪽에 붙임, 기준 노드 → 오른쪽 자식의 왼쪽에 붙임
• 우회전: 트리가 왼쪽으로 치우쳤을 때, 기준 노드가 오른쪽으로 이동
• 절차: 왼쪽 자식의 오른쪽 서브트리 → 기준 노드의 왼쪽에 붙임, 기준 노드 → 왼쪽 자식의 오른쪽에 붙임

3. 삽입 알고리즘

• 삽입 시 노드는 Red, 자식 Nil 노드는 Black으로 초기화
• 속성 위반 시 처리:
• 사례 1 (삼촌 노드가 Red): 부모, 삼촌 → Black, 조부모 → Red, 조부모 위반 여부 재확인
• 사례 2 (삼촌 노드가 Black):
• 2A (방향 일치): 부모와 조부모 색 변경 후 회전 (우회전 또는 좌회전)
• 2B (방향 불일치): 부모 기준 회전 후 색 변경, 조부모 기준 회전

4. 삽입 예제

• 사례 1: 삼촌 노드가 Red → 색 변경 후 조부모 위반 여부 확인
• 사례 2: 삼촌 노드가 Black → 방향에 따라 회전 및 색 변경 수행
• 다중 회전 예: 방향 불일치 시 2단계 회전 (예: 부모 기준 우회전 → 조부모 기준 좌회전)

결론

• 레드블랙 트리 삽입 시, 삼촌 노드의 색과 삽입 위치에 따라 사례 1/2 처리
• 회전 및 색 변경을 통해 5가지 속성 유지, Black Height 일관성 보장
• 삽입 알고리즘 구현 시, 회전 방향과 색 변경 순서를 정확히 구현해야 성능 보장