[Data Structure] 2-3 트리(2-3 tree)

---

2-3 트리

 

 

차수가 2 또는 3인 트리, 즉 하위 노드의 개수가 두 개 혹은 세 개인 트리이다. 2-노드라면 이진 탐색 트리처럼 한 개의 데이터와 두 개의 자식 노드를 가지고, 3-노드라면 두 개의 데이터와 세 개의 자식 노드를 가진다.

왼쪽 서브 트리에 있는 데이터들은 모두 첫 번째 데이터보다 작은 값이고, 중간 서브 트리에 있는 값들은 모두 첫 번째 데이터보다 크고, 두 번째 데이터보다 작아야 한다. 오른쪽 서브 트리에 있는 값들은 두 번째 데이터보다 커야 한다. 즉 이진 탐색 트리와 유사하게 정렬되어 있어야 한다.

즉 트리가 위와 같다면 왼쪽 서브 트리의 값은 모두 $ k $ 보다 작고, 오른쪽 서브 트리의 값은 모두 $k $ 보다 크다.

트리가 위와 같다면 왼쪽 서브 트리의 값은 $ k_1 $ 보다 작고, 중간 서브 트리의 값은 $ k_1 $ 과 $ k_2 $ 사이이며, 오른쪽 서브 트리의 값은 $ k_2 $ 보다 크다.

또한 2-3 트리는 모든 말단 노드가 같은 높이에 위치해야 한다. 즉 균형잡힌 상태를 유지해야 한다. 따라서 삽입, 삭제 등에서 균형 이진 탐색 트리와 유사하게 회전이 필요하다.

 

---

탐색 | C

 

탐색은 이진 탐색 트리와 비슷하다.

int search(Tree23Node *root, int key) {
    if (root == NULL) {
        return 0;
    } else if (key == root->key1 || (root->type == THREE_NODE && key == root->key2)) {
        return 1;
    } else if (root->type == TWO_NODE) {
        if (key < root->key1) {
            return search(root->left, key);
        } else {
            return search(root->right, key);
        }
    } else {
        if (key < root->key1) {
            return search(root->left, key);
        } else if (key < root->key2) {
            return search(root->middle, key);
        } else {
            return search(root->right, key);
        }
    }
}

 

---

삽입

 

하나의 노드가 가질 수 있는 값이 최대 두 개이기에 노드에 두 개 이상의 값이 삽입되면 분리가 필요하다.

만약 세 개의 값을 삽입한다고 해보자. 각 값들이 삽입되다가 세번째 값이 삽입되면 노드는 세 개의 값을 가질 수 없기 때문에 분리가 필요하게 될 것이다. 따라서 아래 그림과 같이 중앙값을 원래의 노드가 데이터로 가지고, 그보다 작은 값을 왼쪽 서브 트리로, 그보다 큰 값을 오른쪽 서브 트리로 내린다.

그 외에도 다양하게 분리가 필요할 것이다. 특히 단말 노드가 분리될 경우 상위 노드가 2-노드냐 3-노드냐가 분리에 영향을 미친다. 만약 2-노드 하위 단말 노드에서 에서 분리가 필요하다면 아래와 같이 분리가 될 것이다.

즉 2-노드 하위 단말 노드에서 분리가 이루어지면 2-노드가 3-노드가 된다.

만약 3-노드 하위 단말 노드에서 분리가 필요하다면 아래와 같이 분리가 될 것이다.

그런데 이 경우 3-노드가 두 개를 초과하는 데이터를 갖기 때문에 다시 분리가 필요하게 된다. 이는 비단말 노드의 분리이기 때문에 단말 노드와 같이 분리할 수 없다. 비단말 노드의 경우는 아래와 같이 분리된다.

만약 이렇게 분리했는데, 다시 또 분리가 필요하다면 다시 분리하면 된다. 그런데 만약 분리가 필요한 노드가 루트 노드라면 아래와 같이 분리된다.