[자료구조/C언어] Red-Black Tree | 2-3 Tree | B-Tree

1. Red-Black Tree

1.1. Red-Black Tree란

• Binary Search Tree의 일종이다.
• Balance Tree의 일종이다.
• 다음 조건을 만족하면 Red-Black Tree이다.
  • – P1. 모든 노드는 빨간색 또는 검은색이다.
    – P2. 각 NULL 포인터는 검은색으로 간주된다.
    – P3. root는 검은색이다.
    – P4. 어떤 노드가 빨간색이면, 그 노드의 두 자식은 모두 검은색입니다
    – P5. root에서 어떤 leaf 노드로 가는 모든 경로는 동일한 수의 black 노드를 포함한다.

1.2. Red-Black Tree 예시

1.3. Red-Black Tree 의 기능

1.3.1 Searching

• Binary Search Tree랑 완전 같다.

Red-Black Tree Serch

// Recursive version
BSTNode* Search(BSTNode* root, Key key) {
	if (root == NULL || root->key == key) return root;
    else if (root->key > key) return Search(root->left_child, key);
    else return Search(root->right_child, key)
}

// Iterative version
BSTNode* Search(BSTNode* root, Key key) {
	BSTNode* cur = root;
    while (cur != NULL) {
    	if (cur->key == key) break;
        else if (cur->key > key) cur = cur->left_child;
        else
        	cur = cur->right_child;
    }
    return cur;
}

 

1.3.2 Insertion

• 항상 삽입되는 노드는 빨간색이어야 한다.
• 이것 역시 Binary Search Tree와 동일한 방식으로 삽입한다.
• 여기서 Red-Black Tree에 위반되는 경우가 생기면 해당 기능을 수행해서 수정해야 한다.
  • Color promotion, single rotation, double rotation
• Insertion 하는 경우를 살펴보자
  • Case 1: 아무것도 없다가 삽입하는 경우
    • 그냥 Red 노드 삽입 후 Black으로 색깔을 바꾸어서 P3에 위반되지 않게 고치면 된다.
  • Case 2: 삽입되는 X의 노드의 Uncle 노드가 red인 경우

    • 

      Case 2에 해당되는 트리(Red-Black Tree에 위반된 경우)

      • 1. X의 Parent와 Uncle 노드를 검정색으로 바꾼다.
      • 2. X의 Grandparent 노드를 빨간색으로 바꾼다.
      • 3. 그러면 Grandparent도 규칙에 위반되므로 1,2의 과정을 recursive해서 Grandparent와 다른 sub tree에서도 수정한다.
      • 
      • Color Promotion 과정
        color promotion
        을 진행한다.
  • Case 3: 삽입되는 X의 노드의 Uncle 노드가 Black인 경우
    • single rotation(LL, RR rotation)을 진행한다.

    • 

      왼쪽 : LL Rotation을 해야 하는 경우 / 오른쪽 : RR Rotation을 해야 하는 경우

      • 1. X의 grandparent 노드를 빨간색으로 바꾼다.
      • 2. X의 parent 노드를 검정색으로 바꾼다.
      • 3. 트리의 모양에 따라 LL / RR rotation을 진행한다.
  • Case 4: 1) 삽입되는 X의 노드의 Uncle 노드가 Black이고 삽입되는 위치가 왼쪽 Subtree의 오른쪽 Node인 경우 |  2) 삽입되는 X의 노드의 Uncle 노드가 Black이고 삽입되는 위치가 오른쪽 Subtree의 왼쪽 Node인 경우
    • Double Rotation을 진행한다.

    • 

      LR rotation 해야 하는 경우

      
      
      

    • 

      RL rotation을 해야 하는 경우

      
      
      • 1. X의 grandparent 노드를 빨간색으로 바꾼다.
      • 2. X의 노드를 Black으로 바꾼다.
      • 3. 트리의 모양에 따라 LR / RL rotation을 진행한다.
• Tree의 삽입은 아래 링크를 통해 그래픽으로 확인할 수 있다.

B-Tree Visualization (usfca.edu) 를 통해 삽입 과정에 대해 그래픽으로 확인할 수 있다.

B-Tree Visualization

 

 

1.4. Red-Black Tree 정리

• 전반적인 과정은 Binary Search Tree와 비슷하다, 그러나 여기에 Rebalance를 위해 color promotion과 rotation을 수행한다.

 

2. 2-3 Tree

2.1. 2-3 Tree란?

• 이것도 역시 Binary Search Tree의 확장판이다.
• 모든 내부 노드에는 2-노드 또는 3-노드가 있다.
• 2-노드: Children 2개인 요소가 1개 있다.
• 3-노드: Children이 3개인 2개의 요소가 있다.
  – Self-balanced tree  : 모든 리프 노드가 동일한 높이에 있다.

 

2.2. 2-Node

• 2-노드는 두 children이 있는 하나의 요소 X를 가진다.
• L과 R을 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다
  • X는 L의 모든 요소보다 크다
  • X는 R의 모든 요소보다 작다.
• L과 R은 같은 높이를 가진 non-empty의 2-3 Trees이다.
•  

  

  2-Node의 예시(아래 그래프)

  
  

2.3. 3-Node

• 3-노드에는 X < Y인 두 개의 요소 X 및 Y가 있다.
• L, M 및 R을 각각 왼쪽 자식 노드, 중간 자식 노드 및 오른쪽 자식 노드라고 한다.
  • L < X < M
  • M < Y < R
• L, M 및 R은 동일한 높이의 non-empty 2-3 trees이다.

3-Node의 예시

 

2.4. 2-3 Tree의 기능

2.4.1. Searching

• 간단하다. Binary Search Tree랑 같다.
•  

  

  2-3 Tree의 Searching

2.4.2. Insertion

• 다음과 같이 3가지 경우로 나누어진다.
  • Case1. 트리가 비어있는 경우
    • 노드를 생성하고 노드에 값을 입력한다.

      • 

        
        
  • Case2. 리프 노드가 하나의 값만을 가지는 경우
    • 단순히  노드에 새로운 값을 입력한다

    • 

      
      
  • Case3. 리프 노드가 2개의 값을 가지는 경우
    • 노드를 분할하고 3개의 값 부모의 중앙값을 뽑는다.
      • 부모가 3개의 값을 가지면 계속 분할하여 중앙값을 뽑고  필요한 경우 새 루트 노드를 구성한다.

    • 

      
      

    • 

      
      

B-Tree Visualization (usfca.edu)

B-Tree Visualization

 

2.4.3. Deletions

• 두가지 Case로 나누어진다.
  • Case1. 제거할 노드가 leaf 노드인 경우
    • 리프 노드가 3-노드인 경우 요소를 삭제하기만 하면 된다.
    • 그렇지 않으면...
  • Case2. 제거할 노드가 internal 노드(leaf 노드가 아닌 노드)인 경우
    • 자식 중 한 명에게서 요소를 빌립니다

 

3. B - Tree

• 2-3 Tree를 2-3-4 Tree로 확장하면
  • 4-Node: 4명의 Children이 있는 3개의 요소를 가지고 있게 된다.

• 

  2-3-4 Tree

  
  
• B-Tree
  • 2-3 트리와 2-3-4 트리의 일반화된 확장이라고 보면 된다.
  • 이것은 데이터베이스의 기록 색인에 널리 사용된다.

 

4. AVL tree vs. red-black tree vs. B-tree

• 모두 self-balanced trees 이므로 검색, 삽입 및 삭제 작업은 O(log n)에 내에 수행한다.
  • n은 노드 수이다.
• AVL Tree는 빈번한 검색에 더 효과적이다.
• Red-Black Tree는 잦은 업데이트에 더 효과적입니다
• B-트리는 대규모 data-set을 관리하는 데 효과적이며 디스크로부터 데이터에 엑세스를 해야한다.