이 포스팅의 알고리즘 강의는 이곳에서 보실 수 있습니다.

레드-블랙 트리

• 이진탐색트리의 일종
• 균형잡힌 트리: 높이가 O(logn)
• search, insert, delete 연산을 최악의 경우에도 O(logn) 시간에 지원한다.

예시

• 위 사진에서 NIL노드는 실제로 구현하진 않는다.

정의

• 다음의 조건을 만족해야한다.
  1. 각 노드는 red 혹은 black이고,
  2. 루트노드는 black이고
  3. 모든 리프노드(즉, NIL노드)는 black이고,
  4. red노드의 자식들은 전부 black이고(즉, red노드는 연속되어 등장하지 않는다.)
  5. 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black노드가 존재한다.
• 4번과 5번의 조건이 가장 중요하다.
• 노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 엣지의 개수이다.
• 노드 x의 블랙-높이 bh(x)는 x로부터 리프노드까지의 경로상의 블랙노드의 개수이다. (노드 x 자신은 불포함시킨다.)
• 높이가 h인 노드의 블랙-높이는 bh>=h/2 이다.
  • 조건 4에 의해 레드노드는 연속될 수 없으므로 당연하다. (black의 개수는 Red보다 크거나 같다.)
• 노드 x를 루트로 하는 임의의 부트리는 적어도 2의 bh(x)승 - 1개의 내부노드를 포함한다.(수학적귀납법)
• n개의 내부노드를 가지는 레드블랙트리의 높이는 2log(n+1)이하이다.

Left and Right Rotation

• Rotation을 하더라도 BST의 특성은 유지된다.
• x는 로테이트 시킬 노드를 뜻한다.
• 예시

insert

• 기본적인 과정은 BST와 동일하다.
• RB-INSERT-FIXUP
• insert에는 6가지 케이스가 존재한다. (1,2,3은 부모노드의 왼쪽 4,5,6은 오른쪽이며 과정은 같다.)

Delete

느낀 점

• RB트리의 강의를 보았지만 이 트리의 가장 중요한점은 삽입과 삭제 시에 정확한 순서를 지켜야한다는 점이다. 정확한 순서를 지키기만 한다면 규칙에 어긋나지 않기에 상관없다고 강의에서 나오지만 아직 전체적인 과정이 그림으로 보면 이해가 되지만 코드로 구현하기엔 어렵다는 느낌이 든다.