대학생활/수업

게임알고리즘 12주차 - 2-3 Tree, 2-3-4 Tree, Red-Black Tree

se.jeon 2023. 6. 7. 13:13
728x90
반응형

AVL Tree 복습.

balance factor가 1 이하인 트리.

Binary Tree는 balance factor가 1 이상인 경우가 많다. 시간이 걸리게 되는 요인.

균형, 높이를 맞추어 시간을 단축시키기 위한 기법 중 하나.

insert, delete 시 data의 balance가 깨지는 것을 막기 위해 rotation 시킨다.

 

AVL Tree의 rotation은 총 4가지.

- LL

- RR

- LR

- RL

 

Binary Search의 경우 key가 하나, 자식이 2개가 최대인 2node tree.

탐색 효율을 맞춰주기 위한 작업.

Tree의 높이가 낮을 수록 탐색에 있어 효율적이다.

 

2-3 Tree

B tree의 가장 단순한 포맷.

2-노드(Two Node) : 자식노드가 2개이고 키가 1개인 노드

3-노드(Three Node) : 자식 노드가 3개이고 키가 2개인 노드.

 : Left Child/ Middle Child/ Right Child

 

Binary Search Tree의 노드를 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값이라는 규칙이 유지된다.

 

2-3 트리는 2-노드 또는 3-노드만으로 구성된 특수한 형태의 B-Tree이다.

모든 leaf node는 같은 레벨에 있어야 한다. 완전균형트리를 지향하고 있다.

 

2-3 Tree의 특징

- B-Tree중 가장 간단한 형태

- AVL은 균형 트리를 지향하는 반면, 2-3 트리는 완전균형트리를 지향한다.

- 모든 단말 노드(Leaf node) 의 높이가 같다.

- 모든 내부 노드(Internal node)는 2개 또는 3개의 자식 노드를 가진다.

- 삽입, 삭제, 검색 연산의 시간 복잡도가 모두 O(logN) 이다.

- 대량의 데이터를 효율적으로 관리할 수 있다.

 

The structure of 2-3 tree

- 각 마디에는 키가 하나 또는 둘 존재

- 각 내부 마디의 자식 수는 키의 수 + 1

- 어떤 주어진 마디의 왼쪽(오른쪽) 부분 트리의 모든 키들은 그 마디에 저장되어 있는 마디보다 작거나(크거나) 같다.

- 모든 리프 노드 수준이 같다.

- 데이터는 트리 내의 모든 노드에 저장된다.

- 연산 : insert, delete, search

 

234Tree를 binary tree로 바꿔주는 것이 red-black tree.

 

Insert a node to 2-3 tree

- 2-3 Tree는 아래에서 위로 데이터가 확장된다.

- 한 쪽에 데이터가 치우친다면, 가운데 데이터를 위로 옮겨준다.

 

Lab. 10, 8, 7, 20, 30, 50을 차례대로 입력 받을 때 2-3 트리를 구성하시오.

 

Delete a node from 2-3 tree

- 좌우의 수가 다르다면, 많은 쪽을 중앙으로 가져온다.

- 좌우가 같을 때 left rotation 할 것인지, right rotation 할 것인지는 정하기 나름이다.

- 데이터가 두 개 뿐이게 될 경우, 하나의 노드로 병합을 해 준다.

- 내부 노드를 삭제 할 경우 successor를 취한다.

- 프로그램은 한 가지 룰을 만들면 그대로 유지해야 한다. successor 규칙을 정했으면 병합을 해서 처리하는 과정에서 successor의 값에 따라 구분을 해 주는 처리를 해 주어야 한다.

 

Search from 2-3 tree

root에서 시작해서 왼쪽, 오른쪽, 가운데 중 조건에 맞는 곳을 탐색하고, 없을 경우 null을 return한다.

 

The efficiency of searching in 2-3 Tree

- 모든 노드가 3-노드일 때 가장 높이가 낮음.

- Level 0의 루트노드가 3-노드라면 그 내부에는 2개의 키값이 들어감.

- Level 1에 3개의 3-노드가 있다면 그 내부에는 각각 2개의 키값이 들어감

- Level h까지의 키값의 수 N = 2(1+3+3^2+···+3^h) ≈ 3^h

- 트리 높이 h는 최대 레벨 수와 일치하므로 h ≈ log3N

- 최악의 경우 : 모든 노드가 2-노드로서 트리의 높이 ≈ h log2N

 

Binary Search Tree 는 가지가 2개이기 때문에 log2N

2-3 Tree는 가지가 3개이기 때문에 log3N

 

- 최선의 경우 : 트리 높이 h는 최대 레벨 수와 일치하므로 h ≈ log3N

- 최악의 경우 : 모든 노드가 2-노드로서 트리의 높이 h ≈ log2N

- 2-3 트리에는 2-노드와 3-노드가 섞여 있으므로 O(log3N) <= O(2-3 트리 효율) <= O(log2N)

 

- 이진탐색트리는 최악의 경우 O(N)이지만, 2-3트리는 항상 완전 균형트리를 유지하므로 최악의 경우에도 효율을 보장한다.

- 3-노드는 비교해야 할 키가 2개이므로 비교 횟수가 증가한다.

- 3-노드는 자식을 가리키는 포인터가 3개이므로 자식 노드가 없을 경우 2-노드에 비해 널 포인터가 차지하는 공간적 부담이 있다.

 

2-3-4 Tree

자식 노드를 가리키는 링크가 4개이고 키가 3개인 트리

- Left Child/ Left Middle Child/ Right Middle Child/ Right Child

- 노드의 삽입과 삭제는 2-3 트리와 유사

- 탐색 효율 : O(log4N) ≤ O(2-3-4트리효율) ≤ O(log2N)

 

4-node 제거방법

case 1) Root가 4-node인 경우

    중간 키 Y가 올라가서 트리 높이 증가

case 2) 내려가면서 만난 4-node가 2-node의 자식 노드인 경우

    중간 노드를 올리고, 나머지 노드는 분리되어 부모 노드의 왼쪽 자식과 중간 자식으로 붙게 됨. 높이는 그대로 유지.

case 3) 내려가면서 만난 4-node가 3-node의 자식노드인 경우

    부모노드가 4-node로 바뀌면서 왼쪽 중간자식, 오른쪽 중간자식으로 분리시켜 붙임. 트리 높이는 그대로 유지.

 

Red-Black Tree

2-3-4 트리를 이진 트리로 표현한 것. 노드나 엣지 정보를 색으로 구분하는 Tree. 효율성을 높이기 위한 아이디어.

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

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

- 4-node의 Red-Black 표현은 유일함

빨간색 node는 높이로 카운팅하지 않는다.

실제로 프로그램을 짤 때는 주로 node에 coloring을 한다.

 

Red-Black Tree 속성

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

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

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

 

Delete 4-node in 2-3-4 Tree -> Red-Black Tree

 

using node color

insert할 때 알고리즘에 따라 red/ black이 정해진다. 처음 insert시 red로 지정된다. parent도 red일 시 rebuilding.

 

Properties

1. Root node : 루트 노드는 black

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

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

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

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

2-3-4 Tree의 성질을 위배하는 것은 Red-Black Tree의 성질을 위배하는 것.

 

Red-Black Tree : Node Structure

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인 경우

    a. P의 부모 노드 G는 black이다. (g가 red이면 이미 성질을 위반한 것.)

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

    c. P의 형제 노드 S의 경우에 따라

        case 1. s가 red인 경우

        case 2. s가 black이고, a가 p의 오른쪽 자식인 경우

        case 1. s가 black이고, a가 p의 왼쪽 자식인 경우

 

Properties

1. Root node : 루트 노드는 black

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

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

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

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

 

A : input node

P: parent

S : sibling of parent

G : grandparent (parent of its parent)

 

case 1. S가 red인 경우 : Property 3번 위배.

    Recoloring 'P' and 'S' in black

    Recoloring 'G' in red

    If 'G' is a root node, recoloring 'G' in black

if (node->parent == node->parent->parent->left) 
{
    Node* uncle = node->parent->parent->right;
    
    if (uncle != nullptr && uncle->color == Color::RED) 
    {
        node->parent->color = Color::BLACK;
        uncle->color = Color::BLACK;
        node->parent->parent->color = Color::RED;
        node = node->parent->parent; // 위로 이동하여 계속
    }
}

case 2. S가 black이고, A가 P의 오른쪽 자식인 경우 : Property 3, 4번 위배.

    If it is RR shape, then do RR rotation

    If it is LR shape, then do RR rotation and LL rotation

    Recoloring 'P' and 'G'

if (node->parent == node->parent->parent->right) 
{
    Node* uncle = node->parent->parent->left;
    
    if (uncle != nullptr && uncle->color == Color::BLACK) 
    {
        node->parent->color = Color::BLACK;
        node->parent->parent->color = Color::RED;
        rotate_left(node->parent->parent);
    }
}

 

case 3. S가 black이고, A가 P의 왼쪽 자식인 경우 : Property 3, 4번 위반

    If it is LL shape, then do LL rotation

    If it is RL shape, then do LL rotation and RR rotation

    Recoloring 'P' and 'G' 

if (node->parent == node->parent->parent->left) 
{
    Node* uncle = node->parent->parent->right;
    
    if (uncle != nullptr && uncle->color == Color::BLACK 
    {
        node->parent->color = Color::BLACK;
        node->parent->parent->color = Color::RED;
        rotate_right(node->parent->parent);
    }
}
void insert(int key) 
{
    Node *new_node = new Node(key);
    
    if (root == nullptr) 
    {
        root = new_node;
        root->color = Color::BLACK;
        return;
    }
    
    Node *current = root;
    Node *parent = nullptr;

    while (current != nullptr) 
    {
        parent = current;
        
        if (key < current->key) 
        {
        	current = current->left;
        }
        else
        {
            current = current->right;
        }
    }

    new_node->parent = parent;

    if (key < parent->key) 
    {
        parent->left = new_node;
    } 
    else 
    {
        parent->right = new_node;
    }
    
    insertFixup(new_node);
}

 

보강 공지

21일 수요일까지 대면 수업 진행.

22일 목요일 오전 보강 > 시간을 옮겨 24일 토요일 오전 10시 비대면 온라인 기말평가

노트 필기 준비 필요. 객관식 주관식 단답식 골고루 출제 예정.

728x90
반응형