[자료구조] LLRB 트리

LLRB 트리란?(Left-Leaning Red Black 트리)

LLRB 트리는 2-3 트리를 Red-Black Tree로 구현한 것으로,

Red 링크가 항상 왼쪽으로 기울어지도록 만든 트리입니다.

 

LLRB 트리의 3가지 기본연산

LLRB 트리의 회전연산은 color변경이 별개인 RB와 달리, 회전과 color변경 작업을 모두 포함합니다.

📌 회전할 때 색이 바뀌는 규칙

1. 올라가는 노드: 원래 부모(내려가는 노드)가 갖고 있던 색을 그대로 뺏어옵니다. (부모가 검은색이었으면 검은색, 빨간색이었으면 빨간색이 됩니다.)
2. 내려가는 노드: 무조건 빨간색(RED)으로 바뀝니다.

 

1. rotateLeft

- 왼쪽으로 회전 + color변경

2. rotateRight

- 오른쪽으로 회전 + color변경

3. flipColors

- 노드 아래 두 링크의 색이 같을 때, 노드와 자식 노드들 둘다 다른색으로 변경.

 

 

그렇다면 이러한 연산들은 어떤 상황에 의해 쓰이는지 알아봅시다.

LLRB의 규칙 3가지

아래 규칙의 순서는 고려해야할 우선순위와 같습니다.

1. 오른쪽 Red link 금지

- 발견시 rotateLeft(n)

2. 왼쪽으로 Red link 2개 연속 금지

- 발견시 rotateRight(n)

3. 양쪽 자식 모두 Red 금지

- 발견시 flipColors(n)