Tree 01. BST(Binary Search Tree, 이진 탐색 트리)

14 Apr 2021 • Algorithms

MIT introduction to Algorithm (6.006) Lecture 5를 기반으로 정리한 내용입니다.

Runway Reservation Problem

공항에서 비행기들의 착륙 예정 시간을 생각해보자.

비행기에서 요청한 예정 시간을 \(t\) 라 하고, \(t\) 로부터 \(k\) 시간 내에 다른 착륙 요청이 없다면 $t$ 를 집합 $R$ 에 추가한다. 만약 비행기가 착륙하고 나면 $t$ 를 $R$ 에서 제외한다. $R = {41, 46, 49, 56}~ and ~ k = 3$ 이라면 다음과 같이 나타낼 수 있다.

Figure 1

  • 만약, 요청한 시간 $t$가 44라면, $46 \in R$ 이므로 $R$에 추가할 수 없다.
  • $t=53$ 이라면, 조건에 충족하므로 $R$ 에 추가할 수 있다.
  • $t=20$ 이라면, 이미 지난 시간으로 추가하지 않는다.

Goal: 이 시스템을 효율적으로 가동해서, $O(lgn)$ 내에 실행되게 한다.

  • Unsorted list / array
    • 삽입은 $O(1)$ 의 시간복잡도를 지니지만, $t$가 적합한 시간인지 체크하는데 $O(n)$ 의 시간이 걸린다.
  • Sorted data
    • Array: 오류를 찾기 위해 Binary Search를 시행할 수 있다.
      • 탐색하는데 $O(lgn)$ 의 시간이 걸리고, 비교하는데 $O(1)$ 의 시간이 걸린다.
      • 삽입하기 위해서는, 정렬을 유지하기 위해 다른 데이터를 이동시켜야 하므로 $O(n)$의 시간이 걸린다…!
    • Linked list라면, 삽입은 빨리 할 수 있으나, Binary Search를 하지 못하여 $O(n)$의 시간이 걸린다.
    • Heaps: (weak invariant)
      • $t < |k|$ 인지 체크하기 위해 모든 노드를 체크해야 한다. $\rightarrow O(n)$ 의 시간이 걸림!

만약, 삽입을 빠르게 할 수 있다면, sorted data에서 해결 가능함 $\rightarrow$ BST로 해결!

BST (Binary Search Trees, 이진 탐색 트리)

다음과 같이 더 작은 값은 왼쪽, 더 큰 값은 오른쪽에 넣는다는 규칙을 만들어진 트리를 BST라고 한다.

image-20210414131601819

Structure

node x = key(x)

pointers = parent(x), left(x) and right(x)

이러한 방식으로 각 노드는 key값과 부모노드, 자식노드의 포인터를 저장한 구조체로 이루어진다.

Invariant(불변성)

For any nodes x, if y is in the left subtree of x, key(y) ≤ key(x) and if y is in the right subtree, we have key(y) ≥ key(x)

항상 이와 같은 규칙을 따라서 저장이 되어 항상 부모 노드의 왼쪽 subtree는 부모 노드보다 작거나 같고, 부모 노드의 오른쪽 subtree는 부모 노드보다 크거나 같다는 성질을 지닌다.

Operations

  • key값을 정렬된 순서로 출력

    • 단순한 재귀 알고리즘을 통해 실행할 수 있으며, Inorder(중위 순회) tree walk로 구현한다.

    • 모든 노드를 지나야 하므로 $O(n)$ 의 시간복잡도를 지님.

    • Psuedo Code:

      1
2
3
4
5

      INORDER-TREE-WALK(x)
if x != NIL
	INORDER-TREE-WALK(x.left)
print x.key
INORDER-TREE-WALK(x.right)

  • Minimun

    • x.left가 NIL이 나올 때 까지 left로 이동 후 key값을 return.

  • Mamximum

    • x.right가 NIL이 나올 때 까지 right로 이동 후 key값을 return.

  • Successor (크기순으로 정렬했을때 현재 key값 다음 key값)

    • x.right가 존재한다면, x.right부터 시작하여 minimum을 찾으면 됨.

    • 그렇지 않다면, x의 successor를 y 라 했을 때, y는 left child가 x의 ancestor인 가장 작은 ancestor가 됨.

    • Psuedo Code:

      1
2
3
4
5
6
7
8

      TREE-SUCCESSOR(x)
if x.right != NIL
    return TREE-MINIMUM(x.right)
y = x.p
while y != NIL and x == y.right
    x = y
	y = y.p
return y

  • Prodecessor는 Successor와 비슷한 방법으로 하면 됨.

  • Search

    • root노드와 찾고자하는 key k가 주어지면, key k가 있는 노드의 주소를 반환하고 없으면 NIL를 반환한다.

    • BST가 만들어진 규칙에 따라 찾아가면 됨.

    • Recursive를 이용한 Psuedo Code:

      1
2
3
4
5
6

      TREE-SEARCH(x,k) //recursive
if x == NIL or k == x.key
	return x
if k < x.key
	return TREE-SEARCH(x.left, k)
else return TREE-SEARCH(x.right, k)

    • Iterative를 이용한 Psuedo Code:

      1
2
3
4
5
6

      ITERATIVE-TREE-SEARCH(x, k) //iterative
while x != NIL and k != x.key
	if k < x.key
		x = x.left
	else x = x.right
return x

  • Insertion

    • 주어진 규칙에 따라 트리를 타고 내려가면서, 적절한 위치에 도달하면 넣고자 하는 값 (z) 를 삽입한다.

    • Pesudo Code

      1
2
3
4
5
6
7
8
9
10
11
12
13
14

      TREE-INSERT(T, z) //T는 트리, z는 삽입하고자 하는 데이터
y = NIL
x = T.root
while x != NIL
	y = x
	if z.key < x.key
		x = x.left
	else x = x.right
z.p = y //끝까지 내려가서 부모를 설정
if y == NIL
	T.root = z // tree T was empty
else if z.key < y.key
	y.left = z
else y.right = z //왼쪽/오른쪽 결정

  • Deletion

    • 삭제 후 BST의 구조를 유지시켜야 해서 다른 과정보다 복잡하다.

    • z를 삭제하고자 하는 데이터라고 하자

    • z의 자식 노드가 없다면, z를 NIL로 만들어주면 된다.

    • z가 하나의 자식 노드를 가진다면, 자식이 z의 위치로 오고 부모노드를 설정해주면 된다.

    • z가 두 개의 자식 노드를 가진다면, z의 successor를 찾아 z 자리로 이동시키고, 부모노드와 자식노드의 포인터를 재설정 해주면 된다.

      2-children case

    • Pesudo Code:

      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

      TRANSPLANT(T, u, v) //포인터를 재설정 해주는 과정
if u.p == NIL
	T.root = v
else if u == u.p.left
	u.p.left = v
else u.p.right = v
if v != NIL
	v.p = u.p
    
TREE-DELET(T, z) //삭제
if z.left == NIL
	TRANSPLANT(T, z, z.right)
else if z.right == NIL
	TRANSPLANT(T, z, z.left)
else y = TREE-MINIMUM(z.right)
	if y.p != z
		TRANSPLANT(T, y, y.right)
		y.right = z.right
		y.right.p = y
TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y

  • 출력을 제외한 operation은 모두 $O(h)~ where ~ h = height$ 의 시간복잡도를 지닌다.

Apply to Problem

주어진 문제로 돌아와서, 데이터를 BST로 만들면 다음과 같아진다.

Figure 2

삽입을 통해 위와 같이 이진 탐색 트리를 만들 수 있으며 새로운 비행기 착륙 시간을 입력하고자 할 때, 탐색과 동시에 $\le |k|$ 를 체크하고 데이터를 삽입 할 수 있으므로 $O(h)$ 의 시간복잡도를 지닌다. 이때, $h$는 트리의 높이 이므로, Balenced BST인 경우 $O(h)=O(lgn)$ 이 되어 문제를 해결 할 수 있다.

또한, 가장 빠른 시간에 착륙하는 비행기는 Minimum을 이용해서 구할 수 있고, 특정 착륙 시간 다음 착륙 시간은 Successor를 이용하여 구할 수 있다.

하지만 최악의 경우, linked list와 크게 다를 바 없는 Unbalanced BST 만들어져서 시간복잡도가 커지는 문제가 발생할 수 있다. $\rightarrow$ AVL을 통해 해결!

Code (C)

BST의 틀을 작성한 코드이다. 문제를 해결한 코드를 먼저 작성했으나, BST의 구조를 보기에는 혼란스러운 점이 있어 다시 작성하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef	struct	s_bst{
	int key;
	struct s_bst *parent;
	struct s_bst *left;
	struct s_bst *right;
}				t_bst;

t_bst	*search_node(t_bst *node, int key) //recursive search
{
	if (node == NULL || node->key == key)
		return (node);
	if (node->key > key)
		return search_node(node->left, key);
	else 
		return search_node(node->right, key);
}

t_bst	*minimum_node(t_bst *min)
{
	while (min->left != NULL)
		min = min->left;
	return (min);
}

void	modify_deleted_node(t_bst **bst, t_bst *replace_node, t_bst *newnode)
{
	if (replace_node->parent == NULL) //root노드를 삭제하면, 새로운 노드가 root노드가 된다.
		*bst = newnode;
	else if (replace_node == replace_node->parent->left) //삭제될 노드의 자식 노드가 왼쪽 자식 노드면 왼쪽에 update 
		replace_node->parent->left = newnode;
	else replace_node->parent->right = newnode; // 오른쪽 자식 노드면 오른쪽에 update
	if (newnode != NULL) // 자식 노드가 없다면 그대로 올림.
		newnode = replace_node;
}

void	delete_node(t_bst **bst, int key)
{
	t_bst *min;
	t_bst *delete_node;
	t_bst *tmp;

	delete_node = search_node(*bst, key);
	tmp = delete_node;
	if (delete_node == NULL)
		return ;
	if (delete_node->left == NULL) //left가 NULL이면 right가 newnode로 update
		modify_deleted_node(bst, delete_node, delete_node->right); 
	else if (delete_node->right == NULL) //right가 NULL이면 left가 newnode로 update
		modify_deleted_node(bst, delete_node, delete_node->left);
	else 
	{
		min = minimum_node(delete_node->right); //지울 노드의 successor를 찾아온다.
		if (min->parent != delete_node)
		{
			modify_deleted_node(bst, min, min->right); //min이 삭제된 노드 자리로 올라온다.
			min->right = delete_node->right;
			min->right->parent = min;
		}
		modify_deleted_node(bst, delete_node, min);
		min->left = delete_node->left;
		min->left->parent = min;
	}
	free(tmp);
}

void	init_node(t_bst *newnode, int key)
{
	newnode->parent = NULL;
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->key = key;
}

void	inorder_to_print(t_bst *bst)
{
	if (bst != NULL)
	{
		inorder_to_print(bst->left);
		printf("%d, ", bst->key);
		inorder_to_print(bst->right);
	}
}

void	insert_node(t_bst **root, int key)
{
	t_bst *y;
	t_bst *x;
	t_bst *newnode;

	newnode = (t_bst*)malloc(sizeof(t_bst));
	init_node(newnode, key);
	y = NULL;
	x = *root;
	while (x)
	{
		y = x;
		if (key < x->key)
			x = x->left;
		else x = x->right;
	}
	newnode->parent = y;
	if (y == NULL)
		*root = newnode;
	else if (newnode->key < y->key)
		y->left = newnode;
	else y->right = newnode;
}

void	postorder_to_free(t_bst *bst)
{
	if (bst != NULL)	
	{	
		postorder_to_free(bst->left);
		postorder_to_free(bst->right);
		free(bst);
	}
}

int main()
{
	t_bst **root;
	int i;
	int j = 0;

	root = (t_bst**)malloc(sizeof(t_bst*));
	*root = NULL;
	srand(42);
	while (j < 50) // 1 ~ 100 까지 수 중에서 50개를 트리에 삽입
	{
		i = rand() % 100 + 1;
		insert_node(root, i);
		j++;
	}
	inorder_to_print(*root); //print 하기 위한 중위 순회
	printf("\n42가 있는지 확인합니다.\n");
	if (search_node(*root, 42))
		printf("존재하는 데이터 입니다.\n");
	else printf("존재하지 않는 데이터 입니다.\n");
	printf("41을 삭제합니다.\n");
	delete_node(root, 41);
	inorder_to_print(*root);
	postorder_to_free(*root); //free 하기 위한 후위 순회
	free(root);
	printf("\n");
}

주어진 문제를 기준으로 작성한 코드이다. 개인적 흥미를 위해 사용한 쓸데없는(?) 명령어들이 등장하고 코드가 너무 길어졌지만 전체적인 틀은 위의 내용을 기반으로 하여 작성하였다. Runaway Reservation System을 깔끔하게 구성하기 위해선 main에 무한루프와 switch문을 이용하여 삭제/삽입/탐색/출력 과정을 넣고, read 대신 fgets 같은 함수를 사용하면 깔끔하게 작동할 것이라 생각한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define K 3
#define ABS(x) ((x < 0) ? (-x) : (x))

typedef	struct	s_bst{
	int key;
	struct s_bst *parent;
	struct s_bst *left;
	struct s_bst *right;
}				t_bst;

t_bst	*search_node_to_delete(t_bst *node, int key) //recursive search
{
	if (node == NULL || node->key == key)
		return (node);
	if (node->key > key)
		return search_node_to_delete(node->left, key);
	else 
		return search_node_to_delete(node->right, key);
}

t_bst	*minimum_node(t_bst *min)
{
	while (min->left != NULL)
		min = min->left;
	return (min);
}

void	modify_deleted_node(t_bst **bst, t_bst *replace_node, t_bst *newnode)
{
	if (replace_node->parent == NULL) //root노드를 삭제하면, 새로운 노드가 root노드가 된다.
		*bst = newnode;
	else if (replace_node == replace_node->parent->left) //삭제될 노드의 자식 노드가 왼쪽 자식 노드면 왼쪽에 update 
		replace_node->parent->left = newnode;
	else replace_node->parent->right = newnode; // 오른쪽 자식 노드면 오른쪽에 update
	if (newnode != NULL) // 자식 노드가 없다면 그대로 올림.
		newnode = replace_node;
}

void	delete_node(t_bst **bst, int key)
{
	t_bst *min;
	t_bst *delete_node;
	t_bst *tmp;

	delete_node = search_node_to_delete(*bst, key);
	tmp = delete_node;
	if (delete_node == NULL)
		return ;
	if (delete_node->left == NULL) //left가 NULL이면 right가 newnode로 update
		modify_deleted_node(bst, delete_node, delete_node->right); 
	else if (delete_node->right == NULL) //right가 NULL이면 left가 newnode로 update
		modify_deleted_node(bst, delete_node, delete_node->left);
	else 
	{
		min = minimum_node(delete_node->right); //지울 노드의 successor를 찾아온다.
		if (min->parent != delete_node)
		{
			modify_deleted_node(bst, min, min->right); //min이 삭제된 노드 자리로 올라온다.
			min->right = delete_node->right;
			min->right->parent = min;
		}
		modify_deleted_node(bst, delete_node, min);
		min->left = delete_node->left;
		min->left->parent = min;
	}
	free(tmp);
}

void	init_node(t_bst *newnode, int key)
{
	newnode->parent = NULL;
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->key = key;
}

int		search_node(t_bst *node, int key) //iterative search, K조건을 위해 수정한 함수
{
	while (node != NULL && (ABS((key - (node->key))) >= K)) // K분 안에 착륙을 할 수 없음.
	{
		if (key < node->key)
			node = node->left;
		else 
			node = node->right;
	}
	return ((node == NULL) ? 1 : 0);
}

void	inorder_tree_walk(t_bst *bst)
{
	if (bst != NULL)
	{
		inorder_tree_walk(bst->left);
		printf("%d, ", bst->key);
		inorder_tree_walk(bst->right);
	}
}

void	insert_node(t_bst **root, int key)
{
	t_bst *y;
	t_bst *x;
	t_bst *newnode;

	newnode = (t_bst*)malloc(sizeof(t_bst));
	init_node(newnode, key);
	y = NULL;
	x = *root;
	while (x)
	{
		y = x;
		if (key < x->key)
			x = x->left;
		else x = x->right;
	}
	newnode->parent = y;
	if (y == NULL)
		*root = newnode;
	else if (newnode->key < y->key)
		y->left = newnode;
	else y->right = newnode;
}

void	postorder_tree_walk(t_bst *bst)
{
	if (bst != NULL)	
	{	
		postorder_tree_walk(bst->left);
		postorder_tree_walk(bst->right);
		free(bst);
	}
}

int main()
{
	t_bst **root;
	int R[] = {46, 41, 49, 37, 56};
	int i;
	char buf[6] = "";

	i = 0;
	root = (t_bst**)malloc(sizeof(t_bst*));
	*root = NULL;
	while (i < 5)
	{
		insert_node(root, R[i]);
		i++;
	}
	inorder_tree_walk(*root); //print 하기 위한 중위 순회
	printf("착륙 예정 시간을 입력하시오(2자리 정수)\n");
	read(0, buf, 2);
	i = atoi(buf);
	if (!search_node(*root, i))
		printf("해당 시간엔 착륙 할 수 없습니다.\n");
	else
	{
		insert_node(root, i);
		printf("요청한 시간에 예약되었습니다.\n");
	}
	printf("취소할 시간을 입력하세요");
	inorder_tree_walk(*root);

	read(0, buf, 2);
	i = atoi(buf);
	delete_node(root, i);
	printf("취소되었습니다.");
	inorder_tree_walk(*root);
	postorder_tree_walk(*root); //free 하기 위한 후위 순회
	free(root);
}

삽질🤦

연결 리스트도 제대로 구현 해 본적이 없는데, 구조체로 트리를 구현하려니 생각보다 고려할게 많았다. 삽입 과정에서 root 노드를 같이 만들다 보니 지역변수에서 만든 값이 날아가 버려서 처음엔 root노드를 계속 return 해줬으나, 매번 값을 return 하는 점이 맘에 안들어서 이중 포인터를 쓰는 방식으로 해결하였다.

또한 머릿속으로 그려볼때는 생각하지 못했던 메모리 문제에 발목을 잡혔다. 매번 동적 할당을 통하여 노드를 만들어 줘서 끝나고 free를 해줄 때 놓치지 않기 위해서 신경써야 했다. 후위 순회를 이용하여 문제를 해결하였으며, 전위(preorder) / 중위(inorder) / 후위(postorder) 순회를 이론만 알고 있었는데 처음으로 구현해 보았다.

Delete한 데이터 역시 free를 해줘야 하는데, 각 경우에 따라 노드가 사라지는 위치가 달라져서 어떻게 free를 해줘야 할지 무척 난감했다. 하지만 메모리 누수가 할당된 메모리를 가리키는 포인터를 잃었을때 복구할 방법이 없는게 문제라는 점에 착안하여 t_bst *tmp 를 선언하여 삭제할 노드를 가리키게 하고, 마지막에 free(tmp) 를 하여 해결하였다. 이 아이디어는 나중에 써먹을 수 도 있을것 같다…!

C언어에서 NIL이 없어서 NULL로 처리했으나, NULL인 노드의 key값을 어떻게 정할지 라는 의문이 생겼다. 단순히 NULL인 노드의 key값을 사용하지 않으면 해결될 문제이지만, NIL을 정의해서 사용하는 방법이 더 나았을것 같다.

매크로 활용에 있어서도 문제가 발생하였는데, ABS(key - (node->key)) 이렇게 사용하니까 매크로가 정상적으로 작동하지 않았다. -key - (node->key) 를 계산한 결과가 나왔는데, 구글링 해보니 매크로 함수는 연산 순서가 꼬이는 경우가 많아 잘 잡아줘야 하며 각 인자에도 괄호를 씌워주는게 좋다고 한다. (e.g. a*b를 매크로로 정의하고 a+1, b+1를 대입하는 경우) 그래서 작성한 매크로를 풀어서 써보니, ABS(key - (node->key))는 ((key - (node->key)<0) ? (-key -(node->key)) : (key - node->key)) 가 되어 꼬이게 되는 것을 확인할 수 있었다.

심심해서 표준입력을 read 함수로 읽어왔는데, 여기서도 의외의 문제가 발생하였다. 2바이트만 읽으려는 목적으로 char buf[3] = "" 으로 선언하였는데, 같은 버퍼에 read를 두번 하니 이미 이전에 읽었던 데이터가 남아있던 상태에서 읽어오면서 Segmentation fault가 발생하였다. lldb를 이용해 열심히 디버깅을 해보니, 이전 입력에서 EOF로 입력을 종료하지 않아 생기는 문제였으며 ctrl+d 를 이용하여 입력하니 해결이 되긴 되었다. 그러나 이번엔 printf함수의 실행 순서가 꼬이는 이상한 버그가 발생하였다. 디버깅이 힘들어서(귀찮… ㅎ) 이건 더 공부를 해봐야 겠다.

참조

MIT OCW 6.006 Introducion to Algorithms 강의 자료 및 강의 내용

Introduce to Algorithms, 3rd Edition

 Algorithms  MIT OCW  tree

modfied:16 Apr 2021

Comments

Related Posts