자료구조 - 2-3 트리

[2-3 트리]

2-3 트리는 모든 내부 노드가 두 개 또는 세 개의 자식을 가지며, 모든 리프 노드가 동일한 깊이에 있는 균형 트리입니다.

이는 데이터베이스나 파일 시스템에서 사용되는 B-트리의 기본 형식입니다.

2-3 트리는 삽입, 삭제, 탐색 연산이 항상 균형 잡힌 상태에서 이루어지므로 시간 복잡도가 O(logn)입니다.

 

 

 

 

2-3 트리 작동 원리

1. 삽입:
   • 새로운 키를 삽입할 때, 현재 노드가 두 개의 키를 가지고 있지 않으면 키를 추가합니다.
   • 노드가 두 개의 키를 가지고 있을 때 키를 추가하면 노드가 분할됩니다.
   • 분할된 키 중 하나는 부모 노드로 올라가고, 나머지는 두 개의 자식 노드로 분할됩니다.
2. 삭제:
   • 리프 노드에서 키를 삭제할 때, 노드에 키가 하나만 있으면 병합 또는 차용이 필요합니다.
   • 내부 노드에서 키를 삭제할 때는 리프 노드에서 대체할 키를 찾아야 합니다.
   • 병합과 차용을 통해 트리의 균형을 유지합니다.

 

 

2-3 트리 의사 코드

class Node
{
    bool isThreeNode; // 두 개의 키를 가지는지 여부
    int key1, key2; // 키 값
    Node* left, middle, right; // 자식 노드
    // 기타 생성자 및 메서드 정의
};

Node* insert(Node* root, int key) 
{
    // 재귀적으로 트리 탐색 및 삽입
    if (root == null) 
    {
        return new Node(key);
    }

    if (root->isThreeNode)
    {
        // 세 개의 키를 가지는 경우 분할
        return split(root, key);
    }

    if (key < root->key1) 
    {
        root->left = insert(root->left, key);
    } 
    else if (root->isThreeNode && key > root->key2) 
    {
        root->right = insert(root->right, key);
    }
    else
    {
        root->middle = insert(root->middle, key);
    }

    return root;
}

Node* split(Node* node, int key) 
{
    // 노드 분할 논리
    // 새로운 노드 생성 및 반환
}

 

 

 

2-3 트리 예제

예제 배열: [10, 20, 30, 40, 50, 25]

1. 10 삽입: [10]

2. 20 삽입: [10, 20]

3. 30 삽입: [20] (중간 키가 부모로 올라가며 분할)
    왼쪽 자식: [10]
    오른쪽 자식: [30]

4. 40 삽입: [20]
    왼쪽 자식: [10]
    오른쪽 자식: [30, 40]

5. 50 삽입: [20, 40] (오른쪽 자식 분할)
    왼쪽 자식: [10]
    중간 자식: [30]
    오른쪽 자식: [50]

6. 25 삽입: [20, 40]
    왼쪽 자식: [10]
    중간 자식: [25, 30]
    오른쪽 자식: [50]

 

 

 

2-3 트리 코드

#include <iostream>
using namespace std;

class Node 
{
    public:
        int keys[2]; // 최대 두 개의 키
        Node* children[3]; // 최대 세 개의 자식
        int numKeys; // 현재 키의 개수

        Node() 
        {
            numKeys = 0;
            for (int i = 0; i < 3; ++i)
            {
                children[i] = nullptr;
            }
        }

        bool isThreeNode() 
        {
            return numKeys == 2;
        }
};

// 노드를 분할하는 함수
Node* split(Node* node, int key) 
{
    Node* newParent = new Node();
    Node* newChild = new Node();

    if (key < node->keys[0])
    {
        newParent->keys[0] = node->keys[0];
        newParent->numKeys = 1;

        newChild->keys[0] = node->keys[1];
        newChild->numKeys = 1;

        node->keys[0] = key;
        node->numKeys = 1;

        newParent->children[0] = node;
        newParent->children[1] = newChild;
    }
    else if (key > node->keys[1])
    {
        newParent->keys[0] = node->keys[1];
        newParent->numKeys = 1;

        newChild->keys[0] = key;
        newChild->numKeys = 1;

        newParent->children[0] = node;
        newParent->children[1] = newChild;

        node->numKeys = 1;
    } 
    else 
    {
        newParent->keys[0] = key;
        newParent->numKeys = 1;

        newChild->keys[0] = node->keys[1];
        newChild->numKeys = 1;

        newParent->children[0] = node;
        newParent->children[1] = newChild;

        node->numKeys = 1;
    }

    return newParent;
}

// 노드를 삽입하는 함수
Node* insert(Node* root, int key) 
{
    if (!root) 
    {
        root = new Node();
        root->keys[0] = key;
        root->numKeys = 1;
        return root;
    }

    if (root->isThreeNode()) 
    {
        return split(root, key);
    }

    if (key < root->keys[0]) 
    {
        root->children[0] = insert(root->children[0], key);
    } 
    else if (root->numKeys == 1 || key < root->keys[1]) 
    {
        root->children[1] = insert(root->children[1], key);
    }
    else 
    {
        root->children[2] = insert(root->children[2], key);
    }

    return root;
}

// 중위 순회
void inOrder(Node* root) 
{
    if (!root) return;
    if (root->numKeys > 0) inOrder(root->children[0]);
    cout << root->keys[0] << " ";
    if (root->numKeys > 1) inOrder(root->children[1]);
    if (root->numKeys > 1) cout << root->keys[1] << " ";
    inOrder(root->children[2]);
}

int main() 
{
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    cout << "중위 순회 결과: ";
    inOrder(root);

    return 0;
}

 

 

 

2-3 트리 장단점

 

장점 :

1. 균형 유지: 모든 리프 노드가 동일한 깊이에 있어, 삽입 및 삭제 연산 후에도 트리가 균형을 유지합니다.
2. 안정성: 트리가 균형을 유지하므로, 최악의 경우에도 탐색, 삽입, 삭제 연산이 효율적입니다.
3. 간단한 구현: B-트리에 비해 구현이 간단합니다.

단점 :

1. 복잡성 증가: 단순 이진 탐색 트리보다 구현이 복잡합니다.
2. 추가 메모리 사용: 각 노드가 추가 키와 자식 포인터를 저장해야 하므로 메모리 사용량이 증가합니다.

 

 

시간 복잡도

 

• 탐색: O(log⁡n)O(\log n)O(logn)
• 삽입: O(log⁡n)O(\log n)O(logn)
• 삭제: O(log⁡n)O(\log n)O(logn)