2025-08-01 20:41

Status:

Tags: 자료구조

레드 블랙 트리

• 높이 균형 $O(\log n)$ 로 유지해서 삽입, 삭제 연산 $O(\log n)$ 보장하는 이진트리
• 회전과 색 재배치로 균형 유지
• 노드가 빨강 혹은 검정 색을 가지는 이진 탐색 트리

주요 특징

• 노드는 빨강 또는 검정
• 루트 노드는 항상 검정
• 빨강 아래 빨강 불가능
• 모든 루트의 검정 노드 수는 동일해야 함
• 마지막 리프 노드인 NIL 노드는 모두 검정
• 위 규칙으로 가장 먼 경로 길이와 가장 짧은 경로 차이가 2배 넘지 않고 높이 $O(\log n)$

삽입 삭제, 회전 등은 참고 노트로 AVL트리 랑 비교하면 높이는 좀더 길어질 수 있어서 검색은 약간 느릴 수 있지만 삽입, 삭제시 회전 횟수 적어서 변하는 연산이 자주 날때 유리

시간 복잡도: 모두 $O(\log n)$

연산	평균 / 최악
검색(Search)	$O(\log n)$
삽입(Insert)	$O(\log n)$
삭제(Delete)	$O(\log n)$
공간(Space)	$O(n)$

References

그래프 트리 레드 블랙 트리 핸드북 레드 블랙 트리 파이썬 구현 핸드북