2-3 트리 (2-3 Tree)

2-3 트리란 무엇일까?

2-3 트리는 이진 탐색 트리의 불균형 문제를 해결하고자 고안된 트리다.

한 노드가 3개의 자식 노드를 가질 수 있기 때문에 이진 탐색 트리는 아니다.

분할(Split)과 병합(Merge)을 통해 불균형 문제를 해결한다.

항상 양쪽 서브트리 간 높이 차가 0인, 완전 균형 탐색 트리다.

 

왜 2-3 트리를 배울까?

2-3 트리 또한 AVL 트리와 마찬가지로 그 자체로는 현재 잘 쓰이지 않는다.

하지만, 2-3 트리의 균형을 유지하는 방식은 현재 데이터베이스 관리를 위해 주로 사용하는 B 트리에서도 사용된다. 

결론적으로, 분할과 병합을 통한 트리 균형 유지 방법을 학습하기 위해 2-3 트리를 배운다.

 

2-3 트리의 조건

0. 트리의 조건을 상속받는다.

1. 왼쪽 서브트리의 모든 노드는 현재 노드의 값보다 작다.

2. 오른쪽 서브트리의 모든 노드는 현재 노드의 값보다 크다.

3. 중간 서브트리의 모든 노드는 현재 노드의 값들의 사잇값이다.

4. 모든 노드는 2-node와 3-node로 구성된다.

5. 키 값은 단말 노드부터 채운다.

6. 단말 노드(Leaf Node)를 제외한 N-node는 항상 N개의 자식을 가져야 한다.

7. 모든 단말 노드들이 같은 계층에 존재해야 한다.

---

2-3 트리에서 사용되는 용어

용어	설명
2-node	1개의 키 값과 2개의 자식 노드를 가지는 노드를 의미한다.
3-node	2개의 키 값과 3개의 자식 노드를 가지는 노드를 의미한다. 키 값은 항상 오름차순을 유지한다.
Promotion	2-node에서 3-node가 되는 것
Demotion	3-node에서 2-node가 되는 것
Overflow	노드의 키가 3개인 경우
Underflow	노드의 키가 존재하지 않는 경우
분할 (Split)	노드를 나누는 행위
병합 (Merge)	노드를 합치는 행위

 

2-3 트리의 트리 재구성

2-3 트리는 Overflow 또는 Underflow 발생 시 분할과 병합을 통해 트리를 재구성한다.

 

---

2-3 트리 구현

삽입 (Insert)

새로운 키를 저장할 단말 노드로 이동한다.

Overflow가 발생하면 노드를 분할하여 중간값을 루트노드로 하는 새로운 서브트리를 만든다.

해당 서브트리를 부모노드와 연결하고 만약, 그 과정에서 Overflow가 발생하면 위 과정을 반복한다.

Node *insert(Node *root, int key)
{
    if (root == NULL)
    {
        return createNewNode(key);
    }

    if (root->left == NULL) // root is leaf node
    {
        if (root->type == NODE2)
        {
            root->key[1] = key;
            if (root->key[0] > root->key[1]) 
            {
                swap(&(root->key[0]), &(root->key[1]));
            }
            root->type = NODE3;
        }
        else if (root->type == NODE3)
        {
            if (key < root->key[0])
            {
                swap(&key, &(root->key[0]));
            }
            else if (key > root->key[1])
            {
                swap(&key, &(root->key[1]));
            }

            root->left = createNewNode(root->key[0]);
            root->right = createNewNode(root->key[1]);
            root->key[0] = key;
            root->key[1] = INULL;
            root->type = NODE2;
        }

        return root;
    }

    Node *temp;
    int child;
    if (key < root->key[0])
    {
        temp = insert(root->left, key);
        child = LEFT;
    }
    else if (root->type == NODE2 && key > root->key[0])
    {
        temp = insert(root->right, key);
        child = RIGHT;
    }
    else if (root->type == NODE3 && key > root->key[1])
    {
        temp = insert(root->right, key);
        child = RIGHT;
    }
    else if (root->type == NODE3) // root->key[0] < key < root->key[1]
    {
        temp = insert(root->mid, key);
        child = MID;
    }

    if (temp->type == NODE3)
    {
        return root;
    }
    else if (temp->type == NODE2)
    {
        if (root->type == NODE2)
        {
            switch (child)
            {
            case LEFT:
                root->key[1] = root->key[0];
                root->key[0] = temp->key[0];
                root->left = temp->left;
                root->mid = temp->right;
                root->type = NODE3;
                break;

            case RIGHT:
                root->key[1] = temp->key[0];
                root->mid = temp->left;
                root->right = temp->right;
                root->type = NODE3;
                break;
            }
        }
        else if (root->type == NODE3)
        {
            switch (child)
            {
            case LEFT:
            {
                swap(&(temp->key[0]), &(root->key[0]));

                Node *leftNode = createNewNode(root->key[0]);
                leftNode->left = temp->left;
                leftNode->right = temp->right;
                
                Node *rightNode = createNewNode(root->key[1]);
                rightNode->left = root->mid;
                rightNode->right = root->right;

                root->key[0] = temp->key[0];
                root->key[1] = INULL;
                root->left = leftNode;
                root->mid = NULL;
                root->right = rightNode;
                root->type = NODE2;
                break;
            }

            case MID:
            {
                Node *leftNode = createNewNode(root->key[0]);
                leftNode->left = root->left;
                leftNode->right = temp->left;
                
                Node *rightNode = createNewNode(root->key[1]);
                rightNode->left = temp->right;
                rightNode->right = root->right;
                
                root->key[0] = temp->key[0];
                root->key[1] = INULL;
                root->left = leftNode;
                root->mid = NULL;
                root->right = rightNode;
                root->type = NODE2;
                break;
            }
            
            case RIGHT:
            {
                swap(&(temp->key[0]), &(root->key[1]));

                Node *leftNode = createNewNode(root->key[0]);
                leftNode->left = root->left;
                leftNode->right = root->mid;
                
                Node *rightNode = createNewNode(root->key[1]);
                rightNode->left = temp->left;
                rightNode->right = temp->right;
                
                root->key[0] = temp->key[0];
                root->key[1] = INULL;
                root->left = leftNode;
                root->mid = NULL;
                root->right = rightNode;
                root->type = NODE2;
                break;
            }
            }
        }
    }

    return root;
}

---

삭제 (Delete)

이진 탐색 트리와 유사한 방식으로 삭제할 키를 찾는다.

단, 단말 노드인 경우만을 고려하기 위해, 삭제할 키가 내부 노드인 경우 후임자를 대신 삭제한다.

 

삭제할 키의 노드가 3-node인 경우, 추가적인 작업 없이 키를 삭제할 수 있다.

 

삭제할 키의 노드가 2-node인 경우, underflow가 발생하고, 트리를 재조정 할 소요가 발생한다.

이 경우 다음과 같은 경우들을 고려해야 한다.

형제 노드 중 3-node가 있는 경우

형제 노드를 강등시키고, 형제 노드의 키를 부모 노드로 대치시킨 후 부모 노드의 키를 이용하여 underflow가 발생한 노드를 채움으로써 해소한다.

형제 노드의 키를 바로 사용할 수 없는 이유는 이진 탐색 트리의 특성을 깨지 않기 위함이다.

 

형제 노드 중 3-node가 없고, 부모 노드가 3-node인 경우

부모 노드를 강등시켜 underflow가 발생한 노드를 채우고 중간 노드와 병합하여 해소한다.

 

형제 노드들과 부모 노드 모두 2-node인 경우

부모 노드의 키를 남은 자식 노드에 병합시키고 underflow 해소의 책임을 부모 노드에 전가한다.

추후 구현 예정

---

검색 (Search)

중간 범위를 탐색하는 로직만 추가되었을 뿐, 이진 탐색 트리와 개념은 동일하다. 

Node *search(Node *root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (key < root->key[0])
    {
        root = search(root->left, key);
    }
    else if (root->type == NODE2 && key > root->key[0])
    {
        root = search(root->right, key);
    }
    else if (root->type == NODE3 && key > root->key[1])
    {
        root = search(root->right, key);
    }
    else if (root->type == NODE3 && root->key[0] < key && key < root->key[1]) // root->key[0] < key < root->key[1]
    {
        root = search(root->mid, key);
    }

    return root;
}

 

---

범위 검색 (Range Search)

중간 범위를 탐색하는 로직만 추가되었을 뿐, 이진 탐색 트리와 개념은 동일하다. 

void rangeSearch(Node *T, int x, int y)
{
    if (T != NULL)
    {
        if (x <= T->key[0])
        {
            rangeSearch(T->left, x, y);
        }

        if (x <= T->key[0] && T->key[0] <= y)
        {
            printf("%d ", T->key[0]);
        }
        if (T->type == NODE3 && x <= T->key[1] && T->key[1] <= y)
        {
            printf("%d ", T->key[1]);
        }

        if (T->type == NODE3 && x <= T->key[0] && T->key[1] <=y)
        {
            rangeSearch(T->mid, x, y);
        }

        if ((T->type == NODE2 && T->key[0] <= y) || (T->type == NODE3 && T->key[1] <= y))
        {
            rangeSearch(T->right, x, y);
        }
    }
}

---

시간 복잡도

2-3 트리의 높이는 ⌈log2​(k+1)⌉≤h≤⌊log3​(k+1)⌋ 이며, 완전 균형 트리로서 다음의 시간복잡도를 가진다.

연산	평균	최악
삽입	O(logN)	O(logN)
삭제	O(logN)	O(logN)
검색	O(logN)	O(logN)

---

문제점

2-3트리는 키와 자식의 숫자가 제한적이다.

이것을 좀 더 일반화 시킬 수 있는 방법을 생각해 볼 수 있다.

---

2-3 Tree Complete Code

#include <stdio.h>
#include <stdlib.h>
#define NODE0 -1
#define NODE2 2
#define NODE3 3
#define INULL 0
#define LEFT 0
#define MID 1
#define RIGHT 2
#define swap(a, b) \
    {              \
        *a ^= *b;  \
        *b ^= *a;  \
        *a ^= *b;  \
    }

typedef struct Node
{
    int type;
    int key[2];
    struct Node *left, *mid, *right;
} Node;

Node *createNewNode(int);
Node *split(Node *);
Node *merge(Node *);
Node *insert(Node *, int);
Node *delete(Node *, int);
Node *search(Node *, int);
void rangeSearch(Node *, int, int);
void preorder(Node *);
void inorder(Node *);
void postorder(Node *);

Node *createNewNode(int key)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key[0] = key;
    newNode->key[1] = INULL;
    newNode->type = NODE2;
    newNode->left = NULL;
    newNode->mid = NULL;
    newNode->right = NULL;
    return newNode;
}

Node *insert(Node *root, int key)
{
    if (root == NULL)
    {
        return createNewNode(key); // 루트가 있는 상태에서 노드를 추가할 때 문제 발생
    }

    if (root->left == NULL) // root is leaf node
    {
        if (root->type == NODE2)
        {
            root->key[1] = key;
            if (root->key[0] > root->key[1]) 
            {
                swap(&(root->key[0]), &(root->key[1]));
            }
            root->type = NODE3;
        }
        else if (root->type == NODE3)
        {
            if (key < root->key[0])
            {
                swap(&key, &(root->key[0]));
            }
            else if (key > root->key[1])
            {
                swap(&key, &(root->key[1]));
            }

            root->left = createNewNode(root->key[0]);
            root->right = createNewNode(root->key[1]);
            root->key[0] = key;
            root->key[1] = INULL;
            root->type = NODE2;
        }

        return root;
    }

    Node *temp;
    int child;
    if (key < root->key[0])
    {
        temp = insert(root->left, key);
        child = LEFT;
    }
    else if (root->type == NODE2 && key > root->key[0])
    {
        temp = insert(root->right, key);
        child = RIGHT;
    }
    else if (root->type == NODE3 && key > root->key[1])
    {
        temp = insert(root->right, key);
        child = RIGHT;
    }
    else if (root->type == NODE3) // root->key[0] < key < root->key[1]
    {
        temp = insert(root->mid, key);
        child = MID;
    }

    if (temp->type == NODE3)
    {
        return root;
    }
    else if (temp->type == NODE2)
    {
        if (root->type == NODE2)
        {
            switch (child)
            {
            case LEFT:
                root->key[1] = root->key[0];
                root->key[0] = temp->key[0];
                root->left = temp->left;
                root->mid = temp->right;
                root->type = NODE3;
                break;

            case RIGHT:
                root->key[1] = temp->key[0];
                root->mid = temp->left;
                root->right = temp->right;
                root->type = NODE3;
                break;
            }
        }
        else if (root->type == NODE3)
        {
            switch (child)
            {
            case LEFT:
            {
                swap(&(temp->key[0]), &(root->key[0]));

                Node *leftNode = createNewNode(root->key[0]);
                leftNode->left = temp->left;
                leftNode->right = temp->right;
                
                Node *rightNode = createNewNode(root->key[1]);
                rightNode->left = root->mid;
                rightNode->right = root->right;

                root->key[0] = temp->key[0];
                root->key[1] = INULL;
                root->left = leftNode;
                root->mid = NULL;
                root->right = rightNode;
                root->type = NODE2;
                break;
            }

            case MID:
            {
                Node *leftNode = createNewNode(root->key[0]);
                leftNode->left = root->left;
                leftNode->right = temp->left;
                
                Node *rightNode = createNewNode(root->key[1]);
                rightNode->left = temp->right;
                rightNode->right = root->right;
                
                root->key[0] = temp->key[0];
                root->key[1] = INULL;
                root->left = leftNode;
                root->mid = NULL;
                root->right = rightNode;
                root->type = NODE2;
                break;
            }
            
            case RIGHT:
            {
                swap(&(temp->key[0]), &(root->key[1]));

                Node *leftNode = createNewNode(root->key[0]);
                leftNode->left = root->left;
                leftNode->right = root->mid;
                
                Node *rightNode = createNewNode(root->key[1]);
                rightNode->left = temp->left;
                rightNode->right = temp->right;
                
                root->key[0] = temp->key[0];
                root->key[1] = INULL;
                root->left = leftNode;
                root->mid = NULL;
                root->right = rightNode;
                root->type = NODE2;
                break;
            }
            }
        }
    }

    return root;
}

Node *search(Node *root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (key < root->key[0])
    {
        root = search(root->left, key);
    }
    else if (root->type == NODE2 && key > root->key[0])
    {
        root = search(root->right, key);
    }
    else if (root->type == NODE3 && key > root->key[1])
    {
        root = search(root->right, key);
    }
    else if (root->type == NODE3 && root->key[0] < key && key < root->key[1]) // root->key[0] < key < root->key[1]
    {
        root = search(root->mid, key);
    }

    return root;
}

void rangeSearch(Node *T, int x, int y)
{
    if (T != NULL)
    {
        if (x <= T->key[0])
        {
            rangeSearch(T->left, x, y);
        }

        if (x <= T->key[0] && T->key[0] <= y)
        {
            printf("%d ", T->key[0]);
        }
        if (T->type == NODE3 && x <= T->key[1] && T->key[1] <= y)
        {
            printf("%d ", T->key[1]);
        }

        if (T->type == NODE3 && x <= T->key[0] && T->key[1] <=y)
        {
            rangeSearch(T->mid, x, y);
        }

        if ((T->type == NODE2 && T->key[0] <= y) || (T->type == NODE3 && T->key[1] <= y))
        {
            rangeSearch(T->right, x, y);
        }
    }
}

void inorder(Node* root) 
{
    if (root == NULL) {
        return;
    }

    inorder(root->left);
    printf("|%d %d| ", root->key[0], root->key[1]);
    inorder(root->mid);
    inorder(root->right);
}

void preorder(Node* root) 
{
    if (root == NULL) {
        return;
    }

    printf("|%d %d| ", root->key[0], root->key[1]);
    preorder(root->left);
    preorder(root->mid);
    preorder(root->right);
}

void postorder(Node* root)
{
    if (root == NULL) {
        return;
    }

    postorder(root->left);
    postorder(root->mid);
    postorder(root->right);
    printf("|%d %d| ", root->key[0], root->key[1]);
}

int main() {
    /* Let us create following tree
              40
           /     \
          20      60
         /  \    /  \
       10   30  50   70 */
    struct Node* root = NULL;
    for(int i=1; i<=7; i++)
    {
        root = insert(root, i*10);
    }

    printf("-----Origianl Tree-----\n");
    printf("Inorder:\n");
    inorder(root);

    printf("\n\nPreorder:\n");
    preorder(root);

    printf("\n\nSearch 30:\n");
    Node *ptr = search(root, 30);
    printf("|%d %d|", ptr->key[0], ptr->key[1]);

    printf("\n\nRange Search [10, 50]:\n");
    rangeSearch(root, 10, 50);
}