2-3 Tree 추가 삭제 구현 (2-3 Tree Insert Delete)

이번에도 정말 오랜만에 포스팅을 하게 되었습니다. 하지만, 변함없이, 쭈욱… 이어서 오늘은 2-3 tree 에 대해 이야기를 해보려고 합니다.

blush

2-3 treeAVL tree 와 비슷하게, 균형 잡는 트리 중의 하나입니다. 2-3 tree 는 기존의 이진 트리와 달리, 하나의 노드에 최대 2개의 키 값이 저장 될 수 있는 구조를 가지고 있습니다. 키가 2 개가 되면서 자식도 3개를 가지게 됩니다.

또한, 2-3 tree 는 완전히 균형 잡힌 트리를 유지하게 되는데요. AVL 트리는 양쪽 서브 트리 중에 한쪽의 높이가 1 큰 것은 허용했던 것과는 다른 부분입니다. 즉, 2-3 tree 는 모든 leaf 노드가 같은 level 에 있게 됩니다.

2-3 tree overview
2-3 Tree

2-3 tree 는 다음과 같은 속성을 가지고 있습니다.

  1. 노드의 키는 정렬되어 있다. (왼쪽 키 < 오른쪽 키)
  2. 왼쪽 자식 노드는 왼쪽 키보다 작고, 가운데 자식 노드는 왼쪽 키 보다 크고 오른쪽 키 보다 작으며, 오른쪽 자식 노드는 오른쪽 키 보다 크다.
    왼쪽 자식 < 왼쪽 키 < 가운데 자식 < 오른쪽 키 < 오른쪽 자식
  3. 자식 노드의 level 은 모두 같다.
  4. 새로운 노드의 추가 또는 기존 노드의 삭제는 항상 leaf node 에서 일어난다.

이제, 이 속성에 맞게 2-3 트리의 동작을 구현하면 됩니다.

kiss

먼저, 2-3 노드의 구조체를 정의하겠습니다.

struct tree_node {
	struct tree_node *left;
	struct tree_node *middle;
	struct tree_node *right;

	int key[2];
};

그리고, AVL tree 를 할 때 처럼, stack 구조체를 정의하겠습니다. Stack 은 나중에 2-3 tree 의 균형을 잡을 때 사용하게 됩니다.

struct stack_item {
	struct tree_node *node;
	enum {
		LEFT = -1,
		MIDDLE = 0,
		RIGHT = 1,
	} path;
};

이제, 노드를 생성하는 함수를 작성하겠습니다.

struct tree_node *node_create(int key1, int key2)
{
	struct tree_node *node;

	node = malloc(sizeof(*node));
	if (node == NULL) return NULL;

	node->key[0] = key1;
	node->key[1] = key2;
	node->left = NULL;
	node->right = NULL;
	node->middle = NULL;

	return node;
}

2-3 트리에서 새로운 키를 삽입할 때, 노드를 분할 시키는 동작이 발생하게 됩니다. 분할은 2 개의 키를 가지는 3- 노드에서 발생합니다. 예를 들어, { 30, 20, 10 } 세개의 값을 2-3 트리에 삽입하는 경우를 살펴보겠습니다.

30 --
30 추가
30,20
20 추가 (정렬됨)

20을 삽입하면서, 노드의 키 값이 정렬되는 것을 확인할 수 있습니다.

10 추가
10 추가

두 개의 키를 삽입하면서, 노드가 가득 찼습니다. 이 상태에서, 10을 추가하면, 앞서 얘기 했던 분할 동작이 일어나게 됩니다. 노드가 세개의 키 값을 유지할 수 없기 때문에, 노드를 분할 시켜, 세개의 키 값을 트리가 유지할 수 있게 하는 과정입니다.

노드를 분할하는 규칙은 다음과 같습니다.

분할은 앞 서 2-3 트리의 속성 정의에 따라, leaf node 에서부터 발생하며, 경우에 따라, 부모 노드들도 분할되는 상황이 발생할 수 있습니다. 예를 들어, 처음에 봤던, 10 부터 80 까지 추가된 2-3 트리에 90 을 추가하는 경우를 살펴 보겠습니다.

분할
분할 예

먼저, 90 을 추가하기 위해 알맞은 leaf node 를 찾아 갑니다. 그 결과, { 70, 80 } 이 있는 노드에 90이 추가 되어야 하는데, { 70, 80 } 노드는 이미 가득 찼기 때문에, 분할이 일어나게 됩니다. 그 결과, 80 을 부모 노드로 해서 좌측에 70, 우측에 90 을 가지는 서브 트리가 만들어 지는데, 부모 노드인 { 30, 60 } 도 이미 가득 찬 상태이기 때문에, 80 이 들어갈 자리를 만들기 위해 다시 분할을 하게 됩니다. 즉, { 30, 60, 80 } 을 가지고 다시 한 번 분할을 하게 되며, 그 결과, 60 을 부모 노드로 하고 좌측과 우측 노드에 각각 30 80 이 자리를 잡게 됩니다. 그에 따라, 제일 처음 분할 되었던 70 과 90 노드는 80 의 자식 노드로 자리를 잡게 되며, 30 노드의 자식으로는 { 10, 20 }, { 40, 50 } 노드가 각각 왼쪽, 오른쪽 자식 노드가 됩니다.

angry

삭제는 삽입 보다 복잡한 과정으로 진행됩니다. 삭제도 leaf node 에서 발생해야 하는데요. 이를 위해서, 삭제될 노드를 찾은 후, 우측 자식 노드 (가운데 또는 오른쪽 자식) 의 왼쪽 leaf node (가장 작은 값) 또는 좌측 자식 노드의 오른쪽 (가운데 또는 우측 자식 노드) leaf node 와 값을 바꾼 후, leaf node 를 삭제합니다. 이 때, 노드의 키가 2개라면, 문제없이 삭제할 수 있지만, 노드의 키가 한 개 였다면 노드가 삭제 되면서 균형이 깨져서 문제가 됩니다. 즉, 노드가 삭제되면서, 모든 leaf node 가 같은 level 에 있어야 한다는 2-3 트리의 속성을 지키지 못하게 됩니다. 이런 경우, 형제 노드에서 값을 빌려 오거나, 부모 노드와 합치는 방법으로 균형을 유지하게 됩니다.

broken heart

이번에도 처음 예로 보여줬던, 10 부터 80 까지 값으로 구성된 2-3 트리에서 키를 삭제하면서 규칙을 살펴 보도록 하겠습니다.

삭제
삭제

제일 처음 80 을 삭제할 때에는 { 70, 80 } 노드에서, 80 을 지우는 것으로 쉽게 끝났습니다.

두 번째 70을 지울 때는 형제 노드인 { 40, 50 } 으로 부터 키를 하나 가져오게 되는데, 키를 가져올 때는 반드시, 부모 노드를 거쳐서 하나씩 밀면서 가져와야 합니다. 즉, 가운데 노드에서 50 을 가져오면서, 부모 노드의 60을 밀어냅니다. 밀려나간 60은 삭제된 70이 있던 자리로 가면서, 2-3 트리의 조건을 만족시킬 수 있게 됩니다.

세번째에 60을 삭제하면서, { 30, 50 } 노드가 두 개의 자식 노드만 갖게 되어, 2-3 노드의 규칙이 깨지게 됩니다. 즉, 모든 leaf 노드는 같은 level 에 있게 되지 못하는 상황이 발생하게 됩니다. 이 경우, 부모 노드 { 30, 50 } 에서 50 과 가운데 노드의 40 을 합쳐서 하나의 노드로 만들면서 2-3 트리의 속성을 만족 시키게 됩니다.

네번째는 30 을 삭제하는 경우입니다. 30은 leaf node 가 아니기 때문에, 30 을 대신할 leaf node 를 찾습니다. 30 의 우측 자식 노드인 { 40, 50 } 에서 왼쪽 40 이 대체할 키가 되며 30 과 40 값을 교환 한 후, 30을 삭제하게 됩니다.

다섯번째는 40을 삭제하는 경우입니다. 이번에도 40은 leaf node 가 아니기 때문에, 대신할 노드로 50 을 선택합니다. 40과 50의 값을 바꾼 후, 노드를 삭제하는데, 이 때, 노드가 삭제되어야 하는 상황이 발생합니다. 그러므로 형제 노드로부터 값을 빌려와서 노드가 삭제되지 않도록 해서 2-3 트리의 균형을 맞추게 됩니다.

이 외에 있을 수 있는 경우들에 대해서는 노트를 펼쳐서 레벨 3 정도 되는 가득 찬 2-3 트리를 만든 후, 하나씩 삭제하면서 경우의 수를 찾아 보시는 걸 추천합니다. ^^;

2-3 트리를 구현한 소스 코드는 github 에서 확인할 수 있습니다.

참고로, 2-3 트리를 구현하면서, 3 노드를 출력할 수 있게 tree_dump 함수를 수정했으며, 기존에 한 자리의 숫자만 (16 진수로 16개) 표현할 수 있던 것을 3자리 수 까지 표현할 수 있도록 확장 시켰습니다.

오늘은 날씨가 많이 덮네요;;;

indecision

그러니까, 집에서 시원하게 에어콘 틀어놓고, 즐거운 취미 생활하세요~

cool

Link: https://nicesj.com/article/calendar/3249

RSS Feed Since 2003, A story was began.
This page is optimized for the web crawlers, for examples, bingbot, googlebot, daum, naver and so on.
Please, visit the site again using the general user clients, for examples, chrome, firefox, ie and so on.

Previous Next