게임알고리즘 13주차 - Red-Black Tree, B Tree

보강 공지

- 주말에 진행

- 영상 형태로 대체

- 그래프 기초 진행 예정 : 인공지능 시간에 최단경로 찾기를 할 예정. 이를 위한 기초.

 

시험 공지

- 시험은 기존대로 금주 토요일 오전 10시 진행 예정.

- 연필로 작성해서 파일로 업로드 해야 하는 항목이 있다. 필기구 + 연습장 준비 할 것.

- 코드 작성과 같은 부분은 거의 없을 예정.

- 수식에 대한 딥한 부분을 다루지는 않을 예정.

- 10시 시험이므로 10~15분 전에 팀즈에 입장 할 것.

- 팀즈 링크는 LMS에 올라 갈 예정.

- 시험 범위는 중간고사 범위인 정렬 알고리즘 이후 부터~B-Tree까지.

 

Red-Black Tree

2-3-4 트리를 이진트리로 표현한 것.

2-node는 그대로, 3-node는 왼쪽 또는 오른쪽 키를 루트로 하는 이진트리로 구성한다. (트리모양이 유일하지 않다.)

Red Link는 원래 3-node, 4-node에서 같은 노드에 속했었다는 사실을 나타낸다.

4-node 의 Red-Black표현은 유일하다.

 

Red-Black Tree 속성

- 트리를 내려오면서 연속적인 빨강링크 2개는 허용하지 않는다.

- 루트로부터 리프노드까지 검정 링크의 수는 모두 동일하다.

- 2개의 자식노드가 모두 빨강 링크일 때만 4-node에 해당

 

두 가지 컬러링의 방법

- 링크 컬러

- 노드 컬러

엣지 정보가 들어 가 있어야 한다.

실제 구현에서 링크 컬러방식보다는 노드 컬러방식을 더 많이 사용한다.

 

Balanced Tree의 원본형은 AVL Tree.

AVL Tree를 배우며 rotation 기법에 대해 배웠다.

Red-Black Tree도 같은 형태를 가진다. 연이어 Red 링크가 나오면 회전한다.

 

노드 컬러링 규칙과 동일하다.

왼쪽 차일드인지, 오른쪽 차일드인지도 구분 해 주어야 한다. 이어서 마저 다룰 예정.

 

Properties

1. Root node : 루트 노드는 Black

2. External nodes (leaf nodes) : 모든 leaf(nil) 노드는 black

3. Internal nodes : 노드가 red이면 그 노드의 자식은 반드시 black

4. Depth : 루트노드에서 임의의 리프 노드에 이르는 경로에 있는 black 노드의 수는 모두 같다.

** New node : 새로운 입력되는 노드는 red.

enum Color {RED, BLACK};

struct Node 
{
    int key;
    bool color;

    Node *parent;
    Node *left;
    Node *right;
    Node(int key) : key(key), color(Color::RED),

    parent(nullptr), left(nullptr), right(nullptr) {}
};

 

Red-Black Tree : insertion

새로운 node 입력에 대해 발생할 수 있는 case : 입력노드는 red 노드(a)

1. a의 부모 노드 p가 black인 경우 : 모든 성질을 만족함

2. a의 부모 노드 p가 red인 경우 : 케이스는 총 다섯가지.

   (1) p의 부모 노드 g는 black이다. (g가 red이면 이미 성질 위반)

   (2) a의 형제 노드는 black이다. (부모가 red이므로)

   위 둘을 충족하지 못한 상황이면 이미 Red-Black Tree가 아니다.

   (3) p의 형제 노드 s의 경우에 따라

       (case1) s가 red인 경우

       (case2) s가 black이고, a가 p의 오른쪽 자식인 경우

       (case2) s가 black이고, a가 p의 왼쪽 자식인 경우

 

node의 parent가 null일 경우 root node.

root node에 닿을 때 까지 위로 올라가면서 node들의 color를 검증한다.

rotation을 할 때 색상을 변경 해 준다.

 

Red-Black Tree : Remove

insert를 할 때는 uncle node를 많이 보는 경향이 있었는데, remove를 할 때는 brother node를 많이 보는 경향이 있다.

AVL Tree의 삭제 방식과 유사하며, Black color node가 삭제될 때 마다 Fixup을 진행한다.

1. 삭제할 노드의 Color가 Red인 경우 : Red-Black Tree의 높이와 무관함 -> just remove

2. 삭제할 노드의 Color가 Black인 경우 : Red-Black Tree의 속성이 깨짐 -> Fixup 필요

3. Fixup case : 총 8가지 (4 * 2)

   - 터미널 노드인 경우 : 1가지, 삭제할 노드로 Fixup

   - Child가 1개인 경우 : 2가지, null이 아닌 Child node로 Fixup

   - Child가 2개인 경우 : 1가지, successor로 Fixup

if(delNode == nullptr) // remove node가 없음
{
	return false;
}

if(delNode->left == nullptr && delNode->right == nullptr)
{
    removeFixup(fixUpNode);
}
else if(delNode->left == nullptr)
{
    fixUpNode = delNode->right;
    transPlant(delNode, delNode->right);

    removeFixup(fixUpNode);
}
else if(delNode->right == nullptr)
{
    fixUpNode = delNode->left;
    transPlant(delNode, delNode->left);

    removeFixup(fixUpNode);
}
else 
{
    Node *successor = delNode->right;

    while (successor->left != nullptr)
    {
        successor = successor->left;
    }
    fixUpNode = successor;

    removeFixup(fixUpNode);
    delNode->key = successor->key;
    delNode = successor;
}
remove delNode

Coloring

- uncle의 color가 red이면 parent, uncle의 색을 반전시키면 된다.
- rotation을 할 때 recoloring은 parent와 grand-parent만 반전시키면 된다.
- 한쪽으로 쭉 늘여져 있을 경우에는, parent와 grand-parent의 색상을 바꾸고 rotation 시켜준다.

- brother의 color가 red일 경우, brother와 parent의 색을 반전 시키고 recoloring 하면 된다.

- brother이 black이고, 조카들이 black일 경우 brother를 red로 바꾼다.

- brother이 black이고, 조카들 중 red가 있을 경우(왼/오 구분), 색상을 바꾸고 rotation 시켜준다.

 

TransPlant

Red-Black Tree에서 node를 삭제 시 필요하다.

Child가 1개인 노드를 삭제할 때 적용한다.

void transPlant(Node * src, Node *dest)
{
    if (src->parent == nullptr) // root 이면
    {
	    root = dest;
    }
    // parent의 왼쪽 자식이면
    else if(src == src->parent->left)
    {
	    src->parent->left = dest;
    }
    else
    {
	    src->parent->right = dest;
    }
    if(dest != nullptr)
    {
	    dest->parent = src->parent;
    }
}

src : 삭제 노드, dest : child

 

Fixup tree after remove a node

if(delNode->right == nullptr)
{
    fixUpNode = delNode->left;
    transPlant(delNode, delNode->left);
    
    removeFixup(fixUpNode);
}

Fixup tree after remove a node - case 1

if (node == node->parent->left) 
{
    brother = node->parent->right;
    
    // case 1
    if (brother->color == Color::RED) 
    {
        brother->color = Color::BLACK;
        node->parent->color = Color::RED;
        
        rotateLeft(node->parent);
        brother = node->parent->right;
    }
    if (brother->left == nullptr && brother->right == nullptr) 
    {
        brother->color = Color::RED;
        node = node->parent;
        continue;
    }
}
node->color = Color::BLACK;

Fixup tree after remove a node - case 2

if (node == node->parent->left) 
{
    brother = node->parent->right;
    
    // case 2
    if (brother->left->color == Color::BLACK && brother->right->color == Color::BLACK)
    {
        brother->color = Color::RED;
        node = node->parent;
    }
}
node->color = Color::BLACK;

Fixup tree after remove a node - case 3

if (node == node->parent->left)
{
    brother = node->parent->right;
    
    // case 3
    else if (brother->right->color == Color::BLACK) 
    {
        brother->left->color = Color::BLACK;
        brother->color = Color::RED;
        
        rotateRight(brother);
        brother = node->parent->right;
    }
}
node->color = Color::BLACK;

Fixup tree after remove a node - case 4

if (node == node->parent->left) 
{
    brother = node->parent->right;
    
    // case 4
    else if (brother->left->color == Color::BLACK) 
    {
        brother->color = node->parent->color
        node->parent->color = Color::BLACK;
        brother->right->color = Color::BLACK;
        
        rotateLeft(node->parent);
        node = root;
    }
}
node->color = Color::BLACK;

 

삭제할 노드가 아버지의 왼쪽 자식인 경우에 대해서 살펴봤다.

그 반대(Case of (node == node -> parent -> right))인 경우 4가지에 대한 처리도 해 주어야 한다.

반대 방향으로 동일한 방법을 적용하여 Fixup 처리 진행.

 

Sample code

https://sandy-silver-12c.notion.site/Tree-Red-Black-Tree-71ba5a780d744ae1abde872f08e467fc

[Tree] Red-Black Tree

 

Red-Black Tree의 효율

- 삽입 삭제를 위한 코드의 간결성은 이진 탐색트리와 비슷하다.

- 레드블랙 트리의 높이는 O(log2N)에 근접한다.

- 레드블랙 트리는 회전에 의해서 어느 정도 균형을 이룬다.

- 레드블랙 트리는 회전 시기를 판단하기 위해 코드 실행한다. 그에 따른 실행시간이 증가한다.

 

B Tree

2-3 Tree, 2-3-4 Tree 개념을 확장한 형태이다.

2-3-4-...-m : m-way Tree

   - Max children : m

   - Max Keys : m-1

   - m이 커질수록 하나의 노드 내부에서의 비교 횟수가 증가하고, 빈 포인터 공간이 많아진다.

   - 트리의 높이는 그만큼 낮아진다.

- 외부 탐색(External Search) 방법에 많이 사용된다.

 

Lab. Construct a B-tree of order 4 with following set of data : 5, 3, 21, 9, 1, 13, 2, 7, 10, 12, 4, 8

 

외부탐색(External Serarch) 방법

- 외부 저장장치인 파일로부터 찾는 레코드를 읽어 오기 위함.

- 데이터베이스 탐색 방법의 일종이다.

- 파일로부터 메인 메로리로 읽혀지는 기본 단위를 페이지(Page)라 함.

- 외부 탐색에서 알고리즘의 효율을 좌우하는 것은 입출력 시간이다.

- 입출력 시간은 페이지를 몇 번 입출력 했는가에 좌우된다.

 

B Tree의 검색 효율

2-node, 3-node, ..., m-node를 모두 감안하면 평균적인 링크의 수는 m/2

따라서 B Tree의 검색효율은 0(log(m/2)n)