RBTREE란?

• 이진 탐색 트리의 한 종류이다.
• 스스로 균형을 잡는다.
  • 5가지의 속성이 있으며, 이 규칙이 깨지면 해당 규칙을 바로 잡기 위해 조정을 하며, 이 과정에서 균형을 찾는다.
  • 이러한 특성 덕분에 BST의 WorstCase의 단점을 개선하였다.

RBTREE의 5가지 속성

1. 모든 노드는 Red 아니면 Black이다.
2. 루트 노드는 Black이다.
3. 모든 Nil노드는 Black이다.
   1. Nil노드는 존재하지 않음을 의미한다.
   2. 자녀가 없을 경우, 자녀를 Nil노드로 표기한다.
   3. 값이 있는 노드와 동등하게 취급한다.
   4. 사실상, RB Tree의 leaf 노드이다.
4. Red의 자녀들은 Black이다.
   1. Red가 연속적으로 존재할 경우 규칙이 깨진다.
   2. 삽입 시, Red 노드를 삽입하므로 해당 규칙이 깨질 가능성이 높다.
5. 임의의 노드에서 자손 Nil노드까지 가는 경로들의 Black의 수는 같다.
   1. 삭제 시, Black을 삭제할 경우 해당 규칙이 깨질 가능성이 높다.

회전

• 조정을 통해 균형을 맞출 때 사용한다.
• 회전을 통하여, 이때 이진검색트리의 특성을 보전할 수 있다.
  • 작은 값은 left에, 큰 값은 right에 있는 특성

왼쪽 회전

• 시작
  • 회전 대상은 x이다.
  • y는 x의 오른쪽 자녀다.
• 순서
  • y의 왼쪽 자녀는 x의 오른쪽 자녀로 연결된다.
  • y는 x의 부모와 연결된다.
  • x는 y의 왼쪽 자녀로 연결된다.

오른쪽 회전