공부/알고리즘
2022. 12. 20.
06. 검색 트리 - 레드 블랙 트리(RB Tree)
* 해당 포스트는 PC환경에 최적화되어있습니다. * 쉽게 배우는 알고리즘 개정판 교재로 공부했으며 학교에서 배운 내용과 섞어서 정리한 포스트입니다. * 저작권 문제는 hjl3066@gmail.com으로 연락 주시면 빠르게 조치하겠습니다. 레드 블랙 트리는 균형 잡힌 이진 검색 트리의 한 종류이다. 기존의 이진 검색 트리는 저장, 검색 등에 평균 O(log n)의 시간이 소요된다. 하지만 이진 검색 트리가 한쪽으로 치우친 경우 O(n) 시간이 소요된다는 단점이 있다. 이러한 단점을 해결하기 위해 항상 균형이 잡힌 이진 검색 트리를 고안했다. 레드 블랙 트리 : 노드 구분 및 규칙 적용을 통해 균형 유지 AVL 트리 : 레드 블랙 트리보다 더 엄격하게 균형 요구 레드 블랙 트리 이진 검색 트리의 모든 노드에..