게임알고리즘 11주차 - Balanced Tree, AVL Tree

효율적인 사용을 위해 균형 트리를 만들어야 한다.

binary search tree는 균형을 보장하지 않는다.

 

검색 시간 향상을 위한 트리 구조

- 디스크에 접근하는 시간(외부검색:external search)은 RAM에 접근하는 시간(내부검색:internal search)보다 훨씬 느림.

- 외부검색의 경우 선형시간 보장은 나쁜 성능을 초래함 > 항상 균형을 유지하는 이진트리 활용.

- 주기적으로 최적이진트리 구축 알고리즘을 이용하여 트리를 유지할 수 있음.

 

Balanced Tree

AVL 트리 : 아이템의 추가, 삭제, 검색 - 모두 0(log n)

B-트리 / 2-3트리 : 잎마디들의 깊이(수준)을 항상 같게 유지. 아이템의 추가, 삭제, 검색 - 모두 0(log n)

red-black tree : 아이템의 추가, 삭제, 검색 - 모두 0(log n), 키 값이 여러개이고, child가 여러개인 문제로 구현하기 까다로운 2-3 트리를 보완함.

 

AVL Tree

좌, 우 subtree의 높이의 차가 최대 1인 이진탐색트리.

 

AVL Tree에서 균형을 유지하는 방법

bf(balance factor) = height or left subtree - height of right subtree

bf of AVL tree = { -1, 0, 1 }

bf가 양수일 경우, 왼쪽으로 기울어져 있다는 의미이다.

 

AVL rotation to make a balanced tree

LL rotation : rotate right

RR rotation : rotate left

 

Structure of AVL tree node

struct Node {
    int key;
    int height;
    Node* left;
    Node* right;
    
    Node(int key) 
    {
        this->key = key;
        this->height = 1;
        this->left = NULL;
        this->right = NULL;
    }
};

 

Get balance and update height

int get_height(Node* node) 
{
    if (node == NULL)
    {
    	return 0;
    }
    return node->height;
}
    
int get_balance(Node* node) 
{
    if (node == NULL) 
    {
    	return 0;
    }
    get_height(node->left)-get_height(node->right);
}

void update_height(Node* node) 
{
    node->height = 1 + max(get_height(node->left), get_height(node->right));
}

 

Case 1 : LL rotation (rotate right)

Node* rotate_right(Node* node)
{
    Node* left = node->left;
    node->left = left->right;
    left->right = node;

    update_height(node);
    update_height(left);
    
    return left;
}

 

Case 2 : RR rotaion (rotate left)

Node* rotate_right(Node* node)
{
    Node* left = node->left;
    node->left = left->right;
    left->right = node;
    
    update_height(node);
    update_height(left);

    return left;
}

 

How to make balancing in LR imbalanced tree

rotate_left(node->left);
rotate_right(node);

 

How to make balancing in RL imbalanced tree

rotate_right(node->right);
rotate_left(node);

 

How to make a balanced tree

Node* balance(Node* node) 
{
    int balance_factor = get_balance(node);
    
    if (balance_factor > 1) 
    {
        if (get_balance(node->left) < 0) 
        {
        	node->left = rotate_left(node->left);
        }
        return rotate_right(node);
    }
    else if (balance_factor < -1)
    {
        if (get_balance(node->right) > 0) 
        {
        	node->right = rotate_right(node->right);
        }
        return rotate_left(node);
    }
    return node;
}

 

AVL Tree : insert a node into AVL tree

Node* insert(Node* node, int key) 
{
    if (node == NULL) 
    {
    	return new Node(key);
    }
    if (key < node->key) 
    {
    	node->left = insert(node->left, key);
    } 
    else 
    {
    	node->right = insert(node->right, key);
    }
    update_height(node);
    
    return balance(node);
}

 

Lab. Construct AVL tree by inserting the following data : 14, 17, 11, 7, 53, 4, 13, 12, 8, 60, 19, 16, 20

 

AVL Tree : delete a node in AVL tree

1. Find a node to delete

2. Delete the node in the same way as BST deletion

3. Balance the tree

Node* remove(Node* node, int key) 
{
    if (node == NULL) 
    {
    	return NULL;
    }
    if (key < node->key) 
    {
    	node->left = remove(node->left, key);
    } 
    else if (key > node->key) 
    {
    	node->right = remove(node->right, key);
    }
    else 
    { 
    	// 삭제할 노드를 찾음
        if (node->left == NULL && node->right == NULL) 
        {
            delete node;
            return NULL;
        }
        if (node->left == NULL)
        {
            Node* right = node->right;
            delete node;
            return right;
        }
        if (node->right == NULL) 
        {
            Node* left = node->left;
            delete node;
            return left;
        }
        Node* successor = node->right;
        
        while (successor->left != NULL) 
        {
        	successor = successor->left;
        }
        
        node->key = successor->key;
        node->right = remove(node->right, successor->key);
    }
    update_height(node);
    return balance(node);
}

 

AVL Tree : find an item in AVL tree

검색하는 것은 Binary Search Tree와 동일하다.

Node* search(Node* node, int key) 
{
    if (node == NULL || node->key == key) 
    {
    	return node;
    }
    if (key < node->key) 
    {
    	return search(node->left, key);
    } 
    else 
    {
    	return search(node->right, key);
    }
}

 

AVL Tree의 효율

- 탐색 효율 : 균형 잡힌 이진탐색트리이므로 O(log n) 보장

- 삽입, 삭제 될 때 마다 균형파괴여부를 검사하는 시간이 필요하다.

- 트리를 재구성(Rebuilding) 하는 시간이 필요하다.

- 실제 코딩 면에서 까다롭고 복잡한 편이다.

참고 자료 : https://sandy-silver-12c.notion.site/AVL-Tree-3e56074a83824810a04f4f72d83fd928

[Tree] AVL Tree

 

2-3 Tree

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

Three Node : 자식 노드가 3개이고 키가 2개인 노드

: Left Child/ Middle Child/ Right Child

 

2-3 트리는 2-노드

 

2-3 Tree의 특징

- B-Tree(통칭하는 개념)중 가장 간단한 형태이다.

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

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

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

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

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

 

The structure of 2-3 tree

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

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

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

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

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

- 작은 값이 왼쪽, 큰 값이 오른쪽에 정렬되어 있어야 한다.

- 연산 : insert. delete, search

 

Insert a node to 2-3 tree

- Binary Search의 insert와 동일하다.

- 룸이 없으면 세 개의 데이터 값 중에서 가운데 항목을 위로 올린다.

- 올라가서도 데이터 값의 개수를 체크한다.

- 높이는 항상 위쪽으로 자란다.

 

Delete a node from 2-3 tree

AVL Tree의 rotation과 비슷하다.

- leaf node의 경우그냥 삭제.

- 키 값이 두개일 경우 child는 반드시 세개가 되어야 한다.

 

2-3 Tree의 시간 복잡도 및 효율, Red Black Tree 다음 주 이어서 학습 예정.

24일 토요일 10시 기말평가 예정.