TL;DR (세 줄 요약)레드-블랙 트리는 노드마다 빨강 또는 검정 색을 붙이고, 색에 대한 다섯 가지 규칙을 지키는 이진 탐색 트리입니다.이 규칙 덕분에 트리의 높이가 log n 수준으로 유지됩니다. 그래서 탐색, 삽입, 삭제가 최악의 경우에도 O(log n) 시간에 끝납니다.삽입이나 삭제로 규칙이 깨지면 색을 바꾸거나(재색칠) 회전으로 구조를 바꿔서 고칩니다. 삽입은 삼촌 노드의 색을, 삭제는 형제 노드의 색을 보고 처리 방법을 고릅니다.이 글은 크래프톤 정글 4기 Part 2 "탐험 준비" 4주차에 레드-블랙 트리를 공부하면서 정리한 기본 개념입니다. 먼저 알아야 하는 개념, 다섯 가지 규칙, 회전, 삽입, 삭제 순서로 설명합니다.1. 레드-블랙 트리는 무엇인가요?레드-블랙 트리(Red-Black ..