[알고리즘] Ch6. Binary Search Trees - Red-black Tree

Background

• binary tree / binary search tree -> data structure
  • binary search tree는 순서 조건 만족해야 함
• binary search -> algorithm

 

 

Binary Search Tree property

• Binary search tree를 inorder traversal(왼쪽부터 탐색)하면 결과적으로 오름차순으로 정렬됨
• balanced tree일 경우 어떤 데이터를 찾을 때 O(log n) 시간이 걸린다.
• 하지만 long chain tree 구조이면, 어떤 데이터를 찾을 때 O(n) 시간이 걸린다. -> 한 방향으로 쭉 늘어진 형태
• Binary Tree Rotations 기술을 사용해서 트리를 균형 있게 만들 수 있다 ex) AVL tree

 

 

Red-Black tree

• Red-Black tree는 다음을 만족하는 binary search tree이다.
  • Root property: root는 항상 black
  • External Property: 모든 leaf node는 black
  • Internal Property: red node의 자식들은 black node이다.
  • Depth Property: 모든 leaves는 같은 black depth를 가진다.

 

 

Height of a Red-Black Tree

• n개의 item을 가진 red-black tree는 O(log n) height를 가진다.

 

 

Insertion

• red-black tree에 새로운 데이터를 삽입할 때, red로 삽입한다.
  • root, external, depth properties를 쉽게 만족하기 때문이다.
  • Internal property는 보장 안 함
• 삽입 과정:
  1. 적절한 위치 찾기(binary search) -> O(log n)
  2. red로 삽입 -> O(1)
  3. double red가 발생하는 경우, Restructuring or Recoloring을 수행한다. -> 다 맞춰질 때까지 반복

 

 

Double Red 처리

• sibiling ndoe가 black인 경우 -> Restructuring
  • Restructuring은 한 번하면, property 만족함
  • 시간 복잡도: O(1)
• 아닌 경우 -> Recoloring
  • Recoloring해도, 조상부분에서 double red가 발생할 수 있음 -> Restructuring or Recoloring 또 해야 함
  • 최악의 경우, root까지 타고 올라가면서 recoloring 해야 함 
  • 시간 복잡도: O(log n)

 

Restructuring

 

Recoloring