-
GLib의 GTree로 알아보는 균형 이진 트리 알고리즘Programmer/Computer Science 2013. 8. 20. 17:31
GLib에서 제공하는 균형 이진 트리(balanced binary tree)의 구현인 GTree의 알고리즘을 살펴보자. GTree는 AVL tree (Adelson-Velskii and Landis' tree) 알고리즘을 사용하였다.
[그림 1]
우선 균형 상태에 대한 정의부터 해야하겠다. 트리 A가 균형 상태라고 하면
- A의 하위 트리(subtree) A(L)과 A(R)이 균형 상태이고
- A(L)과 A(R)의 높이의 차이가 1 이하이다.
abs(height(A(L)) - height(A(R))) <= 1
노드(node)의 균형율(balance factor)를 정의해보자. 균형율은 양쪽 하위 트리의 높이의 차이, 즉,
height(A(L)) - height(A(R))
또는height(A(R)) - height(A(L))
이다. 둘 중에 하나만 택한다. 노드가 균형 상태이려면 균형율이 -1, 0, 1의 값을 가져야한다.struct _GTreeNode { gpointer key; /* key for this node */ gpointer value; /* value stored at this node */ GTreeNode *left; /* left subtree */ GTreeNode *right; /* right subtree */ gint8 balance; /* height (right) - height (left) */ guint8 left_child; guint8 right_child; };[소스 1] GTreeNode 구조체
GTreeNode의 균형율은 오른쪽 하위 트리에서 왼쪽 하위 트리의 차를 계산하고 있으며, GtreeNode 구조체의 balance라를 멤버 변수에 저장한다.
균형 상태를 유지하기 위해서는 모든 노드의 균형율을 -1, 0, 1로 유지해야 한다. 이 값이 아닌 경우(-2 또는 2)가 되면 균형을 맞추기 위한 조작이 필요하다. 단, 이진 탐색 트리(binary search tree)의 형태는 유지해야 한다. 균형을 맞추는 회전(rotate) 형태에 따라서 LL(Left-Left), RR(Right-Right), LR(Left-Right), RL(Right-Left)로 분류한다. 회전 형태를 판단하고 처리하는 구현은 [소스 2]의 g_tree_node_balance 함수이다.
노드
하위노드
형태
node->balance < -1
node->left->balance <= 0
LL
node->left->balance > 0
LR
node->balance > 1
node->right->balance >= 0
RR
node->right->balance < 0
RL
[표 1] GTreeNode의 balance 값에 따른 회전 형태
static GTreeNode* g_tree_node_balance (GTreeNode *node) { if (node->balance < -1) { if (node->left->balance > 0) node->left = g_tree_node_rotate_left (node->left); node = g_tree_node_rotate_right (node); } else if (node->balance > 1) { if (node->right->balance < 0) node->right = g_tree_node_rotate_right (node->right); node = g_tree_node_rotate_left (node); } return node; }[소스 2] g_tree_node_balance 함수
g_tree_node_balance 함수는 노드의 삽입(g_tree_insert_internal)과 삭제(g_tree_remove_internal) 과정에서 호출된다. 루트 노드부터 변경이 가해진 노드까지 경로(path)를 노드를 거꾸로 올라가면서 균형을 맞춘다. 여러 교제에서는 재귀 함수를 이용하여 구현하고 있으나, GTree는 -아마도 성능상의 이유로- 노드 경로의 스택과 반복(loop)으로 구현하였다.
static void g_tree_insert_internal (GTree *tree, gpointer key, gpointer value, gboolean replace) { GTreeNode *path[MAX_GTREE_HEIGHT]; /* inserts a new key and value into the tree. */ /* ... skip ... */ /* restore balance. This is the goodness of a non-recursive implementation, when we are done with balancing we 'break' the loop and we are done. */ while (1) { GTreeNode *bparent = path[--idx]; gboolean left_node = (bparent && node == bparent->left); if (node->balance < -1 || node->balance > 1) { node = g_tree_node_balance (node); if (bparent == NULL) tree->root = node; else if (left_node) bparent->left = node; else bparent->right = node; } if (node->balance == 0 || bparent == NULL) break; if (left_node) bparent->balance -= 1; else bparent->balance += 1; node = bparent; } }[소스 3] g_tree_insert_internal 함수 중에서 반복으로 균형을 맞추는 소스
LL (Left-Left) 형태
[그림 2-1]
[그림 2-1]이 LL의 형태이다. 노드 A의 균형율이 -2로 왼쪽으로 균형이 깨진 상태를 보여준다(node->balance < -1). 노드 B의 왼쪽 자식 노드의 높이가 오른쪽에 비해서 크거나 같은 상태이다(node->left->balance >= 0). (A 노드에 도착했으면 그 하위 노드는 이미 균형 트리이기 때문에 균형율이 0보다 작거나 같다는 것은 곧 -1 또는 0이라는 의미이다.)
[그림 2-2]
[그림 2-2]의 트리는 [그림 2-1]의 트리의 노드 B와 A를 오른쪽으로 회전시킨 모양이다. LL 형태는 노드를 오른쪽으로 회전하여 균형을 맞춘다. 이것을 구현한 것이 [소스 4]의 g_tree_node_rotate_right 함수이다. 즉, LL 형태의 노드는 이 함수를 이용하여 균형을 맞춘다.
static GTreeNode* g_tree_node_rotate_right (GTreeNode *node) { GTreeNode *left; /* ... skip ... */ left = node->left; if (left->right_child) node->left = left->right; else { node->left_child = FALSE; left->right_child = TRUE; } left->right = node; /* ... skip ... */ }[소스 4] g_tree_node_rotate_right 함수 중에 노드 순환
[소스 5]는 g_tree_node_rotate_right 함수에서 오른쪽 회전 이후에 노드 A와 B의 균형율을 다시 설정하는 내용이다.
static GTreeNode* g_tree_node_rotate_right (GTreeNode *node) { GTreeNode *left; gint a_bal; gint b_bal; left = node->left; /* ... skip ... */ a_bal = node->balance; b_bal = left->balance; if (b_bal <= 0) { if (b_bal > a_bal) left->balance = b_bal + 1; else left->balance = a_bal + 2; node->balance = a_bal - b_bal + 1; } /* ... skip ... */ return left; }[소스 5] g_tree_node_rotate_right 함수 중에 균형율의 재설정
- (15줄) 변경된 트리의 B의 균형율은, 변경 전에 사용한 B(R)이 A(R) 보다 높거나 같기 때문에, 기존의 균형율 (B(R)과 B(L)의 차이)에 A가 더해진 값이다. 즉, 기존 값에 추가된 A에 해당하는 증가분 1을 더해준다.
- (18줄) 새로운 트리의 A의 균형율은, B(L)이 B(R)보다 크거나 같음으로, 이전 트리에서 사용한 것과 내용이 바뀌었다.
- 중간의 왼쪽의 트리에서 B가 없어졌음으로 1만큼 증가시키고,
- B(L) 대신에 B(R)이 사용됨으로 둘 사이의 차이 즉, 이전 트리의 B의 균형율을 더한다.
- 정리하면, 이전 A의 균형율에 이전 B의 균형율과 1을 더한다.
LR (Left-Right) 형태
[그림 3-1]
[그림 3-2]
[그림 3-1]이 LR의 형태이다. 노드 A의 balance factor가 -2로 왼쪽으로 균형이 깨진 상태를 보여준다(node->balance < -1). LL과 다르게 자식 노드 B는 오른쪽의 노드가 더 깊다(node->left->balance > 0). [소스 2]의 g_tree_node_balance 함수를 보면 자식 노드 B에 대해서 g_tree_node_rotate_left를 수행한 후에, 노드 A를 인자로 g_tree_node_rotate_right를 호출한다. 자식 노드 B에 대해서 g_tree_node_rotate_left를 수행하는 것을 설명하려면, B의 자식 노드가 필요하다. 따라서 [그림 3-1]을 [그림 3-2]로 다시 그리도록 하겠다. (여기서도 잊지 말아야 하는 것은 A의 모든 자식 노드들은 이미 균형 상태이다. 즉, B와 C의 균형율은 -1, 0, 1 이다.)
[그림 3-3]
[그림 3-3]의 트리는 [그림 3-2]의 트리의 노드 B와 C를 왼쪽으로 회전-이동시킨 모양이 되었다. 회전 이동하는 코드는 생략한다. LR에서의 g_tree_node_rotate_left 함수의 균형율을 다시 설정하는 것을 살펴보자.
static GTreeNode* g_tree_node_rotate_left (GTreeNode *node) { GTreeNode *right; gint b_bal; gint c_bal; right = node->right; /* ... skip ... */ b_bal = node->balance; c_bal = right->balance; if (c_bal <= 0) { if (b_bal >= 1) right->balance = c_bal - 1; else right->balance = b_bal + c_bal - 2; node->balance = b_bal - 1; } else { if (b_bal <= c_bal) right->balance = b_bal - 2; else right->balance = c_bal - 1; node->balance = b_bal - c_bal - 1; } return right; }[소스 6] g_tree_node_rotate_left 함수 중에 균형율 재설정
(16, 26줄) C의 균형율에 C(R)과 C(L)이 그대로 사용될 경우(c_bal <= 0 && b_bal >= 1) 또는 (c_bal > 0 && b_bal > c_bal)
- 새로운 C의 균형율에 사용할 노드는 변함이 없음으로, 오른쪽 하위 노드에 B가 추가된 내용만 반영하면 된다.
- 즉, 기존 C의 균형율에 1을 감소시킨다.
- (18줄) 기존 트리에서 B와 C의 균형율에 모두 C(L)이 각각 균형율의 오른쪽과 왼쪽으로 사용된 경우(c_bal <= 0 && b_bal < 1),
- 기존 B와 C의 균형율을 더하면 C(L)이 소거되고, C(R)과 B(L)와 C가 남는다.
- C를 제외하기 위해서 1을 감소시킨다.
- 새로운 트리에서 왼쪽에 B가 추가되었음으로 1을 다시 감소시킨다.
- 정리하면, 이전 A의 균형율에 이전 B의 균형율을 더하고 2를 감소시킨다.
- (24줄) 기존 트리에서 B와 C의 균형율에 모두 C(R)이 각각 균형율의 오른쪽과 왼쪽으로 사용된 경우(c_bal > 0 && b_bal <= c_bal),
- 이전 트리의 B의 균형율에서 오른쪽의 C를 제거하기 위해서 1을 감소시키고,
- 변경된 트리에서 C의 왼쪽에 B가 추가하기 위해서 다시 1을 감소시킨다.
- 즉, 이전 트리의 B의 균형율에서 2를 감소킨다.
- B, C의 위치 이동에 따른 내용만 반영한다.
- 변경된 B의 균형율은 오른쪽 하위 노드에 C가 없어졌음으로 1을 감소시킨다.
- C(R)을 제거하기 위해서 이전 B의 균형율에서 이전 C의 균형율을 빼고
- 오른쪽 하위 노드에 C가 없어졌음으로 1을 감소시킨다.
- 정리하면, 이전 B의 균형율에서 이전 C의 균형율과 1을 뺀다
LR 형태의 하위 트리를 왼쪽으로 회전시키면 LL 트리의 형태가 나온다. 이제 노드 A를 오른쪽으로 회전시키면 [그림 3-4]와 같이 좌우 균형이 맞는 형태가 된다.
[그림 3-4]
[소스 5]에서 함수 g_tree_node_rotate_right에서 생략된 부분을 추가하면, 아래의 [소스 7]과 같다. (균형율을 재 설정하는 부분은 충분히 설명되었음으로 생략한다.)
static GTreeNode* g_tree_node_rotate_right (GTreeNode *node) { GTreeNode *left; gint a_bal; gint b_bal; left = node->left; /* ... skip ... */ a_bal = node->balance; b_bal = left->balance; if (b_bal <= 0) { if (b_bal > a_bal) left->balance = b_bal + 1; else left->balance = a_bal + 2; node->balance = a_bal - b_bal + 1; } else { if (a_bal <= -1) left->balance = b_bal + 1; else left->balance = a_bal + b_bal + 2; node->balance = a_bal + 1; } return left; }[소스 7] g_tree_node_rotate_right 함수 중에 균형율의 재설정 2
이상으로, GTree에서 균형 이진 트리가 어떻게 유지되는지 살펴보았다. 균형 이진 트리는 메모리 공간을 효율적으로 활용하면서도 삽입/삭제/검색이 일정 수준 이상의 속도를 보장하는 알고리즘이다. 주메모리의 가격이 점점 저렴해지는 까닭에 요즘 추세는 해시 테이블을 많이 이용하기는 하지만, 메모리 자원을 효율적으로 사용해야 하는 환경에서는 고려할만한 자료구조이다.
GTree를 쓰레드 이진 트리로 구현되면 노드를 순회하는 것이 훨씬 빠를 것 같은데, 이부분이 구현되지 않은 것이 아쉽다. 쓰레드 이진 트리란, 예를 들면, GTreeNode 자료형의 right_child 멤버 변수가 FALSE 일 경우, 오른쪽 자식 노드가 아니라 다음으로 순회할 노드를 가르키는 의미로 사용하는 방식이다.
'Programmer > Computer Science' 카테고리의 다른 글
국내에서 IPv6 주소를 접하기 어려운 이유 (2) 2014.03.14 GLib의 GHashTable로 알아보는 해시 테이블의 충동 해결 방법 (1) 2013.09.17 XML 스키마 (0) 2012.12.28 DTD (0) 2012.12.27 XML (0) 2012.12.21 댓글