RB트리

트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

노드에 자식 노드가 없다면, 그 노드는 리프노드라고 부름.
레드-블랙 트리에서 리프노드들은 비어있고 자료를 가지고 있지 않음.

항상 자신의 오른쪽 부분트리보다는 작거나 같고, 왼쪽 부분트리보다는 크거나 같음.

rbtree는 함수형 프로그래밍에서 특히 유용. 연관 배열이나 집합 등을 구현하는 경우가 많다.

rb트리 속성

1. 모든 노드는 red or black
2. 루트 노드는 black
3. 모든 nil(leaf) 노드는 black
4. red의 자녀들은 black = red가 연속적으로 존재할 수 없다.
5. 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black수는 같다.( 자기 자신은 카운트 제외)
6. rb트리가 5번 속성을 만족하고 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족함.
7. rb트리에서 삽입/삭제 시 주로 4,5번 속성을 위반하는데, 이를 해결하려고 구조를 바꾸다보면 자연스럽게 트리의 균형이 잡힌다.
8. 구조를 바꾸면서 bst의 특징을 유지시키는 방법은 회전이다. 회전을 어떻게 쓸지가 관건이다.

rb트리 삽입

1. 삽입 방식은 일반적인 이진탐색트리랑 같다.
2. 삽입 후 rb트리 위반여부 확인한다.
3. 위반했다면 재조정한다.
4. 트리 속성을 다시 만족한다.
5. 삽입한 노드의 색은 항상 red로 시작

• 왜? 5번 속성을 만족하기 위해서임

rb트리 삭제

1. 삭제전 rb트리 속성을 만족한 상태임
2. 삭제 방식은 일반적인 bst와 동일
3. 삭제 후 rb트리 속성 위반 여부 확인
4. 위반했다면 재조정
5. rb트리 속성 다시 만족
6. rb트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요

• 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색 = 삭제되는 노드의 색
• 삭제하려는 노드의 자녀가 둘이라면 삭제되는 색 = 삭제되는 노드의 successor의 색

7. 삭제되는 색이 red라면 어떤 속성도 위반하지 않는다.

• 삭제되는 색이 black이라면 2,4,5 속성을 위반할 수도 있다.

8. 삭제되는 색이 black일때

• 5번 속성을 주로 위반한다.
• 삭제되는 색이 있던 위치를 대체한 노드에 extra black을 부여.
• 대체한 노드가 red-and-black이 됐다면 black으로 바꿔주면 끝.
• 대체한 노드가 doubly black 이 됐다면 case 1,2,3,4 중 하나로 해결
  이거 봐야함

black height

1. 노드 x에서 임의의 자손 nil노드까지 내려가는 경로에서의 black수(자기 자신은 카운트에서 제외)

nil노드를 알아야함

1. 존재하지 않음을 의미하는 노드
2. 자녀가 없을 때 자녀를 nill노드로 표기
3. 값이 있는 노드와 동등한 취급
4. rb트리에서 leaf노드는 nil노드