[자료 구조] 레드블랙트리(RedBlack Tree)

안녕하세요

이번 포스팅에서는 최근 자바의 Collection을 정리하다보니 TreeSet에 대해서 알게되었습니다

TreeSet은 기본적으로 레드블랙트리 구조로 되어있다는 것을 알게되었습니다

레드블랙트리에 대해서 모르는 부분이 많아 제 나름대로 정리해봤습니다

정리한 내용에 대해서 포스팅해보겠습니다

 

---

 

레드블랙트리란?

레드블랙트리는 이진탐색트리의 한 종류입니다

이전탐색트리에서 삽입, 삭제작업이 계속해서 이루어지면 잘 못하면 한 쪽으로 치우쳐진 트리가 생겨 자료 검색도가 떨어지는 문제가 발생할 수 있습니다

그 문제를 보완하기 위해 만든 트리가 레드블랙트리입니다

O(log n)의 시간복잡도를 가져 일정한 실행시간을 보장해줍니다

 

---

 

레드블랙트리의 특징

1. 모든 노드는 블랙, 레드의 색깔을 가집니다

2. 루트 노드는 항상 블랙입니다

3. 마지막 노드는 리프노드로써 항상 블랙입니다

4. 레드노드는 연속적으로 나올 수 없습니다

5. 모든 리프노드에서 루트노드까지 가는 경로의 블랙노드의 갯수는 모두 같습니다

 

여기까지 레드블랙트리의 대해서 간단하게 알아봤습니다

만약 시간이 된다면 간단하게 레드블랙트리에 대해서 구현해서 적겠습니다!