출처: https://zeddios.tistory.com/237 https://m.blog.naver.com/min-program/221231697752 https://www.codesdope.com/course/data-structures-red-black-trees-insertion/ https://www.youtube.com/watch?v=eO3GzpCCUSg&ab_channel=AlenaChang
visualization: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
Binary Search Tree의 한 종류, 고로 BST의 특성을 모두 포함한다.
RB Tree는 자가 균형 이진 탐색 나무로써, 대표적으로 연관 배열 등을 구현할 때 쓰이는 자료구조이다.
search operation은 O(log n)의 time complexity를 가진다
1. Root Property : 루트노드의 색깔은 무조건 **검정(Black)**이다.
2. External Property : 모든 **external node들은 검정(Black)**이다. (NIL node포함)
3. Internal Property : 빨강(Red)노드의 자식은 **검정(Black)**이다. == No Double Red(빨간색 노드가 연속으로 나올 수 없다.)
4. Depth Property : 모든 리프노드에서 Black Depth는 같다. == 루트노드에서 각 리프노의 경로에 존재하는 블랙노드의 개수는 같다. (그냥 노드의 수는 다를 수 있음.)
<aside> ⭐ 4번 property에 의해, tree의 제일 짧은 depth는 all black 일 경우이고, 3번 property에 의해, tree의 제일 긴 depth는 제일 짧은 depth 에 그 수 보다 무조건 적은 red 노드가 사이사이 껴잇을 때이다. 고로, 최소 depth는 최대 depth보다 2배 이상 차이가 나지 않는다. 이것이 rbtree가 균형을 유지하는 핵심이다.
</aside>