AVL Tree 추가 삭제 구현 (AVL Tree Insert Delete)

정말 오랜만에 포스팅하게 되었네요. 제 아드님들께서 저에게 자유 시간을 허락할 때에만 구현하고 글을 쓸 수 있다 보니, 기약 없이 시간이 흘러 가버렸네요. 게다가 AVL Tree (AVL 트리)를 어떻게 설명하면 쉽게 이해하고, 구현할 수 있을지 고민 하다 보니, 시간이 더 많이 지체된 것 같습니다. 제가 포스팅을 할 때, 꼭 말씀드리는 것이 있는데요. 구현에는 더 좋은 방법이 있을 수 있고, 드물겠지만, 제가 잘못 이해하고 구현한 것이 있을 수도 있습니다. 그러므로, 기본적인 알고리즘이 설명되어 있으면, 직접 고민해서 구현해보고, 제가 구현한 것과 비교해 보는 방식을 추천합니다.

이번에 이야기할 AVL 트리는 1962 년도에 G.M. Adelson-Velsky 와 E.M. Landis 라는 분들이 처음 소개해 준 균형 잡는 트리로 이름의 첫 글자를 따서 A.V.L 이라고 불리고 있습니다. 이 트리는 이 후 이야기할 2.3.4 트리나 R.B 트리 등의 초석이 되었다고 하니, 굉장히 중요합니다만, Open source 가 널린 요즘 세상에 직접 구현해서 쓰는 경우는 그리 많지 않습니다. 또한 더 좋은 (?) 트리도 많기 때문에 굳이 AVL 을 찾아 쓰지는 않고 있지요.

하지만, 세상이 그렇게 돌아간다고 해서, 외면하지는 말고, 최소한 무엇이다 라는 정도로 설명만 할 수 있어도 반은 성공한 것이나 다름없으니, 무엇인지 정도는 짧게 나마 살펴보고 지나가길 바랍니다.

먼저 AVL 트리의 기본 정의는 다음과 같습니다.

  • 이진 검색 트리와 같은 방식으로 트리를 유지한다. (값의 크기가 왼쪽 < 부모 < 오른쪽)
  • 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 2 가 되면 균형을 잡아 준다. (높이 차이를 1 이하로 유지한다)

혹시나 더 자세한 무언가를 찾으신다면 다음 링크들을 따라가면 됩니다.

지금까지 우리가 트리를 표현할 때 대부분 배열을 사용 했었는데요, 이번에도 지난 번 Tree 구조 (예쁘게?) 출력하기 처럼, heap 을 사용해서 구현하도록 하겠습니다. 사실, 배열로 구현하자니 귀찮은게 너무 많고, 또 왠만한 오덕이 아니고서야, 이런 트리를 배열로 구현해보라는 대회(?) 는 없을 겁니다.

먼저 AVL 트리는 이진 검색 트리 의 node 구조체를 기본으로 하고 있으며, 자식들의 높이 차이 또는 균형도(Balance Factor) 라고 하는 것을 표현하기 위한 변수를 하나 더 가지고 있습니다.

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

	int value;
	int balance;
};

그리고 이 노드 객체를 생성하는 함수는 다음과 같습니다.

struct tree_node *node_create(int value)
{
	struct tree_node *node;

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

	node->value = value;
	node->balance = 0;
	node->left = NULL;
	node->right = NULL;

	return node;
}

자료 구조를 정의했으니, 알고리즘에 대해 좀 더 깊이 있게 이야기해 보도록 하겠습니다. 새로 추가된 balance 에 대한 이야기 입니다. 균형도는 왼쪽 자식 노드를 뿌리 노드로 가지고 있는 서브 트리와 오른쪽 자식 노드를 뿌리 노드로 가지고 있는 서브 트리의 높이 차이를 의미합니다. 값을 계산하는 방식은 (저는)

오른쪽 서브 트리의 높이 – 왼쪽 서브 트리의 높이

로 했습니다. 만약 balance 값이 0 보다 작다면, 왼쪽 서브 트리의 높이 더 높은 것이고, 0 보다 크다면, 오른쪽 서브 트리의 높이가 더 높다는 이야기가 됩니다. 0 이면 자식이 없거나, 양쪽 서브 트리의 높이가 같은 것입니다.

avl-3251
균형 잡힌 AVL Tree (3251)

자 여기까지는 여러 참고 자료에서 설명하고 있는 내용과 같습니다. 그럼 이제 어떻게 그 balance 를 유지 하는지에 대해 이야기하도록 하겠습니다. 먼저 값을 추가할 때 즉 Insert 를 할 때 tree 의 균형을 유지하는 방법을 살펴보도록 하겠습니다.

avl-84c
균형 잡힌 AVL Tree (84C)

뿌리 노드 8 이 노드 4 와 노드 C 를 자식 노드 이면서 단말 노드 (leaf node) 로 가지고 있는 트리의 모습입니다. 노드들의 Balance 는 모두 0 이며, 균형이 잡혀 있습니다. (양쪽 서브 트리의 높이가 차이 1 이하 이므로) 이 트리에 바로 앞 그림에서 본 것 처럼 1을 추가하는 경우를 생각해 보겠습니다.

이진 트리에서 추가를 하려면, 부모 노드에서부터, 작으면 왼쪽, 크면 오른쪽으로 트리를 타고 내려갑니다. 먼저 노드 8 과 비교해서 왼쪽 자식으로 내려가고, 노드 4 와 비교해서 노드 4 의 왼쪽 자식 노드로 추가를 하게 됩니다.

이 때, 추가를 하면서 나무 높이의 변화를 살펴봅니다. 노드 4 를 기준으로 보면, 균형도가 0 이었는데, 왼쪽 서브 트리에 자식이 하나 추가되면서, -1 로 높이 차이가 발생합니다. 이 사실을 부모 노드인 노드 8 에게 알려줘서, 왼쪽 서브 트리에 자식이 추가되었고, 높이에 변화가 생겼다 (증가했다) 라는 것을 알려줘서 -1 로 균형도가 갱신되도록 해야 합니다.

avl-84c2
2 를 추가한 후

만약 여기에 6 을 추가하면, 쭉 타고 내려와서 노드 4 의 오른쪽 자식 노드로 추가가 됩니다. 그리고 노드 4 의 균형도가 0 으로 수정됩니다. 하지만 이 경우는 노드 4 의 높이에 변화가 생기지 않았기 때문에, 부모에게 알릴 것이 없습니다. 자기 자신의 균형도만 업데이트 하고, 부모 노드들의 균형도 갱신을 중단하는 것입니다.

avl-84c26
6 을 추가한 후

자 그럼 구현을 하려면, 새로운 노드를 추가하고 나서, 부모 노드들의 값을 갱신하던지 말던지 해야 하는데요. 그러려면 새 노드가 최종적으로 추가가 될 때까지 타고 내려온 부모 노드들을 알고 있어야 합니다. 이 를 위해, stack 을 사용합니다. (물론 재귀 호출로 구현해도 되지만, stack 을 직접 사용해서 비 재귀판으로 구현한다고 보면 됩니다)

stack 에 push 할 정보로는 노드의 정보와 타고 내려온 방향, 마지막으로 변경되기전의 균형도 입니다. 다음은 Stack 에 push 될 item 구조체 입니다.

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

자 이제, 이 stack 을 이용해 부모 노드들을 추적 하면서 값을 추가하는 코드를 보겠습니다.

iterator = *root;

while (iterator != NULL) {
	if (iterator->value < value) {
		stack[top].balance = iterator->balance;
		stack[top].path = RIGHT;
		stack[top].node = iterator;
		top++;

		iterator = iterator->right;
	}
	else if (iterator->value > value) {
		stack[top].balance = iterator->balance;
		stack[top].path = LEFT;
		stack[top].node = iterator;
		top++;

		iterator = iterator->left;
	}
	else {
		// Already exists (duplicated value)
		free(node);
		return -1;
	}
}

// Adding a new item to the tree
if (stack[top - 1].path == LEFT) stack[top - 1].node->left = node;
else stack[top - 1].node->right = node;

이렇게 부모 노드들에 대한 정보를 담고 내려온 후, 새 노드가 추가된 노드의 높이 변화가 있는지 살펴보고, 변화가 있다면, stack 을 타고 올라가면서 부모 노드들의 균형도를 갱신하는 코드를 보겠습니다.

i = top;
while (--i >= 0) {
	stack[i].node->balance += stack[i].path;

	if (stack[i].node->balance == 2) {
		// TODO
	}
	else if (stack[i].node->balance == -2) {
		// TODO
	} else if (abs(stack[i].balance) == 1) {
		// Children nodes of the parent node were filled. So there are no changes of the depth.
		break;
	}
}

앞서 설명했던 것과 같이, 새 노드가 추가된 자식 노드의 균형도를 업데이트하고 (3번 줄), 균형도가 1에서 0으로 변경된 경우에는 스택 타기를 중단합니다 (10번 줄).

여기까지 구현을 했다면, 이제 AVL 트리에서 각 노드들의 균형도를 기록할 수 있게 됩니다. 이제 어떻게 그 균형도가 0 또는 1이 되도록, 즉, 양쪽 서브 트리의 높이 차이가 2 미만이 되도록 할 수 있는지 살펴 보겠습니다.

avl-842
왼쪽이 더 높은 균형 깨진 AVL Tree

앞서 노드를 추가하는 코드에서 TODO 라고 비워 둔 곳이 두 군데 있었습니다. 노드의 균형도가 -2 또는 2 일 때인데요. 이 때 회전이라는 것을 하게 됩니다. 즉, 왼쪽 서브 트리의 높이가 오른쪽 보다 2 높으면 (균형도 -2), 오른쪽으로 트리를 회전시켜서 그 차이를 낮추는 것입니다.

8,4,2 가 추가되어 있는 노드의 경우, 뿌리 노드인 8 을 기준으로 오른쪽으로 회전을 시키는데, 오른쪽 회전은 중심 노드 (이 경우는 뿌리 노드 8) 를 오른쪽 자식 노드 방향으로 밀어내리고, 중심 노드의 왼쪽 자식 노드를 새로운 중심 노드가 되도록 끌어 올리는 것입니다. 자연스럽게 노드 2 는 새로운 중심 노드인 노드 4 의 왼쪽 자식 노드가 됩니다.

avl-428
오른쪽 회전으로 균형도 회복

여기서 우리가 확인해야 하는 것은 회전을 하면서 전체 트리의 높이가 2에서 1로 줄어 들었다는 것입니다. 즉, AVL Tree 에서의 회전이란, 균형도가 -2 또는 2 인 경우 발생하며, 높은쪽에서 낮은쪽으로 노드 하나씩 밀어 나가기 때문에 양쪽 서브 트리의 높이 차이가 없어지게 하는 것입니다.

그럼 이번에는 8,4,6 노드로 가지는 트리의 회전을 살펴 보겠습니다.

avl-846
8,4,6 이 추가된 노드

앞서 본 8,4,2 트리와는 다르게 노드 4 가 왼쪽이 아닌 오른쪽 자식 노드를 가지고 있습니다. 오른쪽 회전에서 이런 경우, 즉, 새 중심 노드에 오른쪽 자식 노드가 있다면, 중심 노드를 오른쪽으로 내리면서, 왼쪽 자식 노드로 붙여주게 됩니다.

avl-486
회전 후의 트리

그런데, 막상 회전을 시키고 보니, 앞서 842 트리와 달리 균형이 잡히지 않고, 도리어 오른쪽 서브 트리의 높이가 2만큼 높아지게 되었습니다.

이러한 문제를 해결하기 위해 AVL 에서는 4가지 회전을 설명하고 있습니다.

              LL : Left-Left

              RR: Right-Right

              LR : Left-Right

              RL : Right-Left

트리를 회전시킬 때, 중심 노드만 회전시키는 것이 아니고, 새로운 중심 노드가 될 노드도 함께 회전시키는 것입니다. 즉, 846 트리 같은 경우에는 노드 8 을 중심으로 오른쪽 회전을 하기 전에, 노드 4 를 중심으로 왼쪽 회전을 먼저 해서 842 트리와 같은 형태인 864 트리로 만들고, 864 트리를 오른쪽으로 회전시킵니다.

avl-864
노드 4 를 중심으로 좌측 회전 후 (L)
avl-648
노드 8 을 중심으로 우측 회전 후 (R)

이 회전을 LR 회전이라고 하며, 회전 결과 트리의 높이가 1로 줄어들면서 균형이 맞춴진 것을 확인할 수 있습니다. 그럼 실제 구현에서 어떤 회전을 선택해야 하는지 구분하는 방법을 알아보도록 하겠습니다.

먼저, 이재규님이 지으신 “C로 배우는 알고리즘” 에서는 어떤 경우에 어떤 회전을 해야 하는지 구분하기 위한 방법으로 노드가 삽입되는 경로를 사용하고 있습니다. 제가 제대로 이해를 하지 못해서 그런 것일지도 모르지만, 삽입 경로를 이용한 회전 방법 선택은 삭제에서는 사용하기 어렵기 때문에 저는 삽입 경로 보다는 새로운 중심 노드가 될 노드의 균형도와 중심 노드의 균형도를 이용해서 회전 방법을 결정하는 방법을 사용했습니다. 즉 회전을 할 때, 회전 되면서 높이가 낮아지는 쪽이 높이가 더 높은 상태가 되도록 해서 회전 될 수 있도록 트리의 높이를 조절하는 것입니다.

앞의 842 트리에서 노드 8의 균형도는 -2, 노드 4의 균형도는 -1 이었습니다. 두 노드의 균형도의 부호가 모두 음수인 경우에는 LL 회전으로, 846 트리와 같이 음수, 양수 인 경우에는 LR 회전으로, 만약 중심 노드의 균형도가 양수이고 새로운 중심 노드도 양수이면 RR 회전을 중심 노드가 양수이고 새로운 중심 노드가 음수이면 RL 회전을 합니다.

여기까지 구현하면 다음과 같습니다. (LR 이나 RL 은 Left 와 Right 회전의 조합이므로, Left 회전과 Right 회전만 구현합니다)

static int rotate_right(struct tree_node **root, struct tree_node *parent)
{
	struct tree_node *new_root;

	new_root = (*root)->left;
	if (new_root == NULL) return -1;

	if (parent != NULL) {
		if (parent->right == *root) parent->right = new_root;
		else parent->left = new_root;
	}

	(*root)->left = new_root->right;
	new_root->right = *root;
…
static int rotate_left(struct tree_node **root, struct tree_node *parent)
{
	struct tree_node *new_root;

	new_root = (*root)->right;
	if (new_root == NULL) return -1;

	if (parent != NULL) {
		if (parent->right == *root) parent->right = new_root;
		else parent->left = new_root;
	}

	(*root)->right = new_root->left;
	new_root->left = *root;
…
int tree_rotate_right(struct tree_node **root, struct tree_node *parent)
{
	if ((*root)->left == NULL) return -1;

	if ((*root)->left->balance > 0) {
		struct tree_node *tmp = (*root)->left;
		rotate_left(&tmp, *root);

		check_tree(*root, 0);
	}

	return rotate_right(root, parent);
}

int tree_rotate_left(struct tree_node **root, struct tree_node *parent)
{
	if ((*root)->right == NULL) return -1;

	if ((*root)->right->balance < 0) {
		struct tree_node *tmp = (*root)->right;
		rotate_right(&tmp, *root);

		check_tree(*root, 0);
	}

	return rotate_left(root, parent);
}

이제, 회전의 종류(case) 와 방법을 알았으니, 회전시 균형도 조정 방법에 대해 알아보겠습니다. (오른쪽 회전에 대한 설명은 생략하겠습니다. ^^)

사실 회전에서 가장 중요한 것은 회전 그 자체 보다도, 균형도 유지 방법이라고 개인적으로 생각합니다. 계산을 좀 해야 하거든요 ^^;

제가 회전을 하면서 균형도 조정을 할 때, 난감했던 것이, “어떻게 노드들의 깊이를 모두 확인하지 않고 균형도만 가지고 회전 후의 균형도를 결정할 수 있는가” 였습니다. 손으로 그려가며 할 때는 회전 후의 균형도를 모두 다시 채워 넣었죠. 그럼, 코딩을 할 때도, 회전을 하고 나면 매번 회전 노드의 모든 균형을 다시 계산해야 할까요? 여기에 그렇게 구현한 분이 있습니다.

아니면, 각각의 노드에 균형도 대신 높이 값을 가지고 있도록 해볼까요? 하지만, 위키피디아에서는 2비트 균형도 표시만으로도 충분히 구현할 수 있다고 합니다.

Properties[edit]

Balance factors can be kept up-to-date by knowing the previous balance factors and the change in height – it is not necessary to know the absolute height. For holding the AVL balance information in the traditional way, two bits per node are sufficient. However, later research showed if the AVL tree is implemented as a rank balanced tree with delta ranks allowed of 1 or 2 – with meaning "when going upward there is an additional increment in height of one or two", this can be done with one bit.

(출처: wikipedia - AVL Tree)

그럼 이제, 다시 처음으로 돌아가서 노드의 균형도에 대해서 되짚어 보겠습니다. 노드의 균형도란, 좌측 자식 노드를 뿌리 노드로 가지는 서브 트리와 우측 자식 노드를 뿌리 노드로 가지는 서브 트리의 높이 차이라고 했습니다. 다음과 같은 LR 또는 RL 회전이 필요한 트리에서 좌/우 회전을 해 보면서 균형도가 어떻게 갱신되는지 규칙을 찾아보겠습니다.

avl-84c265
균형이 깨진 AVL 트리 (84C265)

먼저 회전이 일어나면, 균형도가 변하는 노드는 뿌리 노드와 회전 후 뿌리 노드가 될 노드의 균형도가 변하게 되며, 다른 노드들의 균형도는 변화가 없습니다. 우리가 보고 있는 84C265 트리에서는 노드 4 를 뿌리로 가지는 서브 트리의 좌측 회전이 선행되어야 합니다.

avl-86c425
노드 4 를 중심으로 좌측 회전 후

이 때, 노드 4 의 균형도는 노드 5 의 높이와 노드 2 의 높이 차이로 결정되는 것을 알 수 있고, 노드 6 의 높이 차이는 회전된 노드 4 의 높이와 노드 6 의 우측 차식의 높이 차이로 결정되는 것을 알 수 있습니다. 이 내용을 수식으로 정리해보면 다음과 같습니다.

H(N) : 노드 N 의 높이

BF(N) : 노드 N 의 균형도

RC(N) : 노드 N 의 우측 자식 (트리에 값이 없는 노드를 표시하기 위해 사용)

LC(N) : 노드 N 의 좌측 자식 (트리에 값이 없는 노드를 표시하기 위해 사용)

N’ : 회전 후의 노드 N

BF(4’) = H(5) – H(2)

BF(6’) = H(RC(6)) – H(4’)

H(5) = H(6) – 1    (BF(6) < 0 이므로)

H(6) = H(2) + BF(4)

H(RC(6)) = H(6) + BF(6) – 1    (BF(6) < 0 이므로, H(6) 의 자식이므로, 높이 1 을 뺀다)

H(4’) = max(H(2), H(5)) + 1       (H(2) 와 H(5) 는 회전 후에도 변하지 않으므로, H(2’) 과 H(5’) 과 같음)

 

이 식들을 열거하여 풀어 나가면 다음과 같습니다.

BF(4’)    = H(2) + BF(4) – 1 – H(2) = BF(4) – 1

BF(6’)    = H(2) + BF(4) + BF(6) – 1 – (max(H(2), H(5)) + 1)

              = H(2) + BF(4) + BF(6) – 1 – max((H(2), H(5)) – 1

              = H(2) + BF(4) + BF(6) – 1 – max(H(2), H(2) + BF(4) – 1) – 1

              = H(2) + BF(4) + BF(6) – 1 – H(2) – max(0, BF(4) – 1) – 1

              = BF(4) + BF(6) – max(0, BF(4) – 1) – 2

              = BF(4’) + 1 + BF(6) – max(0, BF(4’)) – 2

= BF(4’) + BF(6) – max(0, BF(4’)) – 1

 

이번에는노드 6 의 자식 노드가 우측에만 있는 경우에 대해서 살펴 보겠습니다.

avl-84c267
노드 6 에 우측 자식 노드가 있는 경우

이번에도 노드 4를 뿌리로 가지는 서브 트리가 왼쪽으로 회전 되어야 합니다. 이 경우, 노드 4 와 노드 6 의 균형도가 어떻게 달라지는지 식을 유도해 보도록 하겠습니다.

BF(4’)    = H(LC(6)) – H(2)

H(6)       = H(2) + BF(4)

H(LC(6)) = H(6) – 1 – BF(6)    (BF(6) > 0 이므로)

BF(4’)    = H(2) + BF(4) – 1 – BF(6) – H(2) = BF(4) – BF(6) – 1

BF(6’)    = H(7) – H(4’)

H(7)       = H(6) – 1    (BF(6) > 0 이므로)

H(4’)     = max(H(2), H(LC(6)) + 1

BF(6’)    = H(6) – 1 – max(H(2), H(LC(6)) – 1

              = H(2) + BF(4) – 2 – max(H(2), H(2) + BF(4) – 1 – BF(6))

              = H(2) + BF(4) – 2 – H(2) – max(0, BF(4) – 1 – BF(6))

              = BF(4) – 2 – max(0, BF(4’))

              = BF(4’) + BF(6) – 1 – max(0, BF(4’))

 

지금까지는 서브 트리의 좌측 회전을 하면서 수식을 유도했습니다. 이번에는 서브 트리의 우측 회전을 하면서 수식을 유도해 보도록 하겠습니다.

avl-84caeb
우측 회전이 필요한 경우

노드 C 를 뿌리로 하는 CAEB 트리가 우측으로 회전해야 하는 상황인데요. 이 경우에도 두개의 노드 C 와 A 의 균형도만 변하게 되는 것을 알 수 있습니다.

avl-84acbe
노드 C 를 중심으로 우측 회전 시킨 후

BF(C’)    = H(E) – H(B)

H(A)      = H(E) – BF(C)

H(B)      = H(A) – 1    (BF(A) > 0 이므로)

              = H(E) – BF(C) – 1

BF(C’)    = H(E) – H(E) + BF(C) + 1 = BF(C) + 1

BF(A’)   = H(C’) – H(LC(A))

H(C’)     = max(H(B), H(E)) + 1

              = max(H(E) – BF(C) – 1, H(E)) + 1

              = H(E) + max(-BF(C) – 1, 0) + 1

H(LC(A))= H(E) – BF(C) – 1 – BF(A)

BF(A’)   = H(E) + max(-BF(C) – 1, 0) + 1 – H(E) + BF(C) + 1 + BF(A)

              = max(-BF(C) – 1, 0) + 1 + BF(C) + 1 + BF(A)

              = -min(BF(C) + 1, 0) + 1 + BF(C) + 1 + BF(A)

              = -min(BF(C’), 0) + BF(C’) + BF(A) + 1

 

마지막으로 노드 A 의 자식이 왼쪽에 달려 있는 경우에 대해 알아보겠습니다.

avl-84cae9
노드 A 에 왼쪽 자식이 있는 경우

역시 이번에도 C와 A 노드의 균형도를 찾아보도록 하겠습니다.

avl-84a9ce
노드 C 를 중심으로 우측 회전 후

BF(C’)    = H(E) - H(RC(A))

H(E)       = H(A) + BF(C)

H(RC(A))= H(A) + BF(A) – 1

BF(C’)    = H(A) + BF(C) – H(A) – BF(A) + 1 = BF(C) – BF(A) + 1

BF(A’)   = H(C’) – H(9)

H(C’)     = max(H(RC(A), H(E)) + 1

H(9)       = H(A) – 1    (BF(A) < 0 이므로)

BF(A’)   = max(H(RC(A), H(E)) + 1 – H(A) + 1

              = max(H(A) + BF(A) – 1, H(A) + BF(C)) + 1 – H(A) + 1

              = H(A) + max(BF(A) – 1, BF(C)) + 1 – H(A) + 1

              = max(BF(A) – 1, BF(C)) + 2

              = max(BF(A) – 1, BF(C’) + BF(A) – 1) + 2

              = BF(A) – 1 + max(0, BF(C’)) + 2

              = BF(A) + max(0, BF(C’)) + 1

 

자 이제, 이렇게 구한 공식들을 회전 한 후 노드의 균형도를 갱신하는 코드로 구현 하면 다음과 같이 됩니다.

// static int rotate_left(struct tree_node **root, struct tree_node *parent)
if (new_root->balance < 0) {
	(*root)->balance = (*root)->balance - 1;
	new_root->balance = (*root)->balance + new_root->balance - 1 - max(0, (*root)->balance);
}
else if (new_root->balance >= 0) {
	(*root)->balance = (*root)->balance - new_root->balance - 1;
	new_root->balance = (*root)->balance + new_root->balance - 1 - max(0, (*root)->balance);
}
// static int rotate_right(struct tree_node **root, struct tree_node *parent)
if (new_root->balance > 0) {
	(*root)->balance = (*root)->balance + 1;
	new_root->balance = (*root)->balance + new_root->balance + 1 - min((*root)->balance, 0);
}
else if (new_root->balance <= 0) {
	(*root)->balance = (*root)->balance - new_root->balance + 1;
	new_root->balance = new_root->balance + 1 + max(0, (*root)->balance);
}

지금까지 회전을 할 때, 균형도를 조작하는 방법을 어떻게 구현하는지 살펴보았습니다.

이제 트리에서 노드를 삭제하는 코드를 구현해 보도록 하겠습니다. 노드를 삭제할 때는 이진 트리에서 노드를 삭제할 때와 같은 방법으로 구현합니다. 다만, 이번에도 삽입할 때와 같이, 삭제된 노드의 부모 노드의 균형도 변화가 있는지, 있다면 회전이 필요한지를 확인하는 과정이 추가됩니다.

이번에도 균형도의 변화를 추적하기 위해 스택을 사용합니다.

삭제의 경우에도 삽입할 때처럼, 노드의 이전 균형도가 0 이었고, 자식 노드가 있었던 경우는 양쪽 자식이 가득 찬 노드 였으나, 삭제 후 -1 이나 1 이 되었다면 높이에는 변화가 없는 것입니다. 또한 균형도 값은 삽입할 때와는 반대로, 균형도에서 노드가 타고 내려온 방향의 값으로 빼면서 수정합니다.

(노드 삭제 코드는 뒤에 따라 올 전체 코드에서 tree_remove() 함수를 참고하면 됩니다.)

이제 AVL 트리에서 삽입과 삭제를 모두 살펴 보았습니다. 다만, 추가적으로 실제 구현을 하면서 필요한 테스트 함수들을 몇가지 더 하려고 합니다.

먼저 앞서 트리 구조 이쁘게(?) 출력하기 에서 소개했던 함수를 조금 수정해서, 트리의 균형도 값도 출력할 수 있도록 했습니다. 두번째로, validate_tree() 라는 함수를 만들어서, 균형도가 제대로 변경 되고 있는지 확인할 때 사용할 수 있도록 했습니다. 재귀 호출을 사용하여 간단히 구현되어 있습니다.

전체 코드는 github 에서 확인 할 수 있습니다.

그럼 모두 즐거운 취미 생활 하세요~

mail

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

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