C#을 이용해 만들었습니다.
이진 공간 분할법(BSP: Binary Space Partitioning)에 대해 공부하다가 BSP는 결국 이진 트리 기반의 알고리즘인 것을 알게 되었다.
이진 트리는 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 구조 인데
문득, 이진 트리에 대해서 알고 있지만 실제로 만들어보면 도움이 되지 않을까? 라는 생각이 들었고 이진 트리 중에서 가장 많이 쓰이고 유용하다고 생각되는 이진 탐색 트리를 만들어보게 되었다.
참고로 C#에서는 SortedDictionary<TKey,TValue> 클래스 로 이진 탐색 트리를 지원하고 있다.
1. C#으로 구현
노드의 값이 정수형 숫자인 노드를 통해 이진 탐색 트리를 만들 예정이다.
1-1. 노드 클래스
노드는 값, 왼쪽 노드 포인터, 오른쪽 노드 포인터로 구성한다.
C#에서는 포인터를 지원하지 않기 때문에 포인터 대신 클래스 인스턴스를 참조하게 해서 구현할 것이다.
이제 코드로 구현해보자.
1
2
3
4
5
6
class Node
{
public int _data = 0; // 값
public Node _leftNode = null; // 왼쪽 노드
public Node _rightNode = null; // 오른쪽 노드
}
1-2. 이진 탐색 트리
이제 이진 탐색 트리를 구현해보자.
구현 방법은 BinarySearchTree 라는 클래스를 정의하고 클래스 인스턴스를 통해 삽입 및 검색을 할 것이다.
1-2-1. 데이터 삽입
일단 데이터를 삽입하는 것부터 만들어보자.
데이터를 삽입하려면 우리는 아래의 단계를 거쳐야 한다.
“노드 생성”은 노드 인스턴스를 생성해서 그 안에 값을 넣는다는 의미이다.
첫 시작은 노드가 존재하는지 즉 루트 노드가 존재하는지 먼저 봐야 한다
루트 노드가 없다면, 루트 노드를 생성해주고 종료해주면 된다.
루트 노드가 있다면, 노드를 탐색해서 삽입한 값을 가지는 새로운 노드를 생성해준다.
물론 값을 가지는 노드가 이미 존재한다면 노드는 생성되지 않을 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
public void Insert(int data)
{
if (_root == null)
{
_root = new Node
{
_data = data
};
return;
}
SettingNewNode(_root, data);
}
1-2-2. 노드 생성
노드를 탐색 및 올바른 위치에 생성하는 함수는 재귀 함수로 구현했고, 위의 플로우 차트를 코드로 작성한 것임으로 자세한 설명은 생략한다.
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
void SettingNewNode(Node targetNode,int data)
{
if (targetNode != null)
{
if (data < targetNode._data)
{
if (targetNode._leftNode != null)
{
SettingNewNode(targetNode._leftNode, data);
}
else
{
targetNode._leftNode = new Node
{
_data = data
};
}
}
else if(data > targetNode._data)
{
if (targetNode._rightNode != null)
{
SettingNewNode(targetNode._rightNode, data);
}
else
{
targetNode._rightNode = new Node
{
_data = data
};
}
}
}
}
2. 너비 우선 탐색으로 노드 확인하기
이제 데이터 삽입(Insert)과 노드를 생성하는 것까지 구현했다.
하지만 정말 데이터가 정상적으로 들어갔을까? 란 궁금증이 생긴다….
궁금증을 해결하기 위해 너비 우선 탐색(BFS)를 이용해서 노드를 전체적으로 탐색해보자!!
2-1. 너비 우선 탐색 구현 방법
너비 우선 탐색은 큐를 이용해서 구현할 것이다.
먼저 간단하게 설명하면
큐를 통해 루트 노드부터 시작해서 좌 → 우로 이동하면서 한 레벨씩 큐에 넣고 처리하는 방식이다.
그림을 통해 자세히 알아보자
아래와 같이 이진 트리가 구성되어 있다고 가정하자
시작하기 전에 루트 먼저 큐에 넣어 둔다.
큐가 비어있을 때까지 큐에서 데이터를 하나씩 꺼내 가지고 있는 자식 노드를 다시 큐에 넣는다.
여기서 중요한건 데이터를 꺼낼 때 왼쪽 자식 노드 → 오른쪽 자식 노드 순으로 꺼낸다.
깊게 들어가지 않고 하나의 레벨을 쭉 탐색하고 다음 레벨로 넘어가기 때문에 그래서 “너비 우선” 탐색이다.
큐에 루트인 0이 있고 여기서 한 사이클을 돌아보자
그럼 0을 꺼내면서 0이 가지고 있는 자식 노드 1 2 를 큐에 다시 넣을 것이다.
그 다음 사이클을 순서대로 보면
큐에서 다시 한 개의 데이터를 꺼낸다. 그럼 1번 노드가 꺼내질 것이고 1번 노드의 자식인 3, 4번 노드를 다시 큐에 넣는다.
그 다음 큐에서 2번 노드를 꺼내고 2번 노드의 자식인 5 6 번 노드를 큐에 넣는다.
이렇게 계속 진행하다 보면 루트 노드부터 시작해서 왼쪽 자식 노드 → 오른쪽 자식 노드 순으로
모든 노드를 탐색할 수 있다는 것을 알 수 있다.
2-2. 코드로 구현
코드로 구현하기 앞서 너비 우선 탐색을 통해 우리는 무엇을 얻어야 하는지 확인해보자
- 각 레벨에 해당하는 노드 내용을 확인할 수 있어야 한다
- 노드의 부모 노드가 누군지 알 수 있어야 한다
- 노드가 부모 기준으로 왼쪽 자식 노드인지 오른쪽 자식 노드인지 알아야 한다
이제 코드로 하나씩 구현해보자
2-2-1. 루트 노드 존재 확인
모든 노드의 위치를 파악하기 앞서 루트 노드가 비어 있는지 먼저 확인해야 한다
루트 노드가 없다면 트리 구조 자체가 존재하지 않는다는 의미이기 때문이다.
1
2
3
4
if(_root == null)
{
return "존재하는 노드가 없습니다.";
}
그 다음 루트 노드가 있다면 큐에 루트 노드를 넣어준다.
1
2
3
4
5
6
7
8
9
if(_root == null)
{
return "존재하는 노드가 없습니다.";
}
int level = 0;
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(_root);
2-2-2. 탐색하기
탐색을 위한 초기 세팅을 완료했다. 이제 탐색을 진행하면 된다.
위에서 확인한 것처럼 큐가 비어있을 때까지
큐에서 데이터를 꺼내서 하나씩 확인하고 노드의 자식 노드들을 큐에 다시 넣어주면 된다.
여기서 우리는 레벨마다 어떤 데이터가 존재하는지 체크하려고 한다.
그래서 큐가 비어 있을 때까지 계속 꺼내기만 한다면 꺼낸 노드가 어떤 레벨에 있는 노드인지 확인하기가 어렵다.
그러므로, 탐색하기 전에 큐 안에 데이터 개수를 파악하고 파악한 개수만큼 탐색할 것이다.
그럼 그 레벨에 해당하는 노드들을 전부 확인할 수 있다.
그림으로 보자면,
아래와 같이 큐에 데이터가 2개 있다면 현재 큐의 개수는 2개이다.
여기서 1 2 노드는 레벨 1의 노드라고 친다.
여기서 1번 노드를 꺼내고 노드의 자식들을 큐에 넣는다면 아래와 같이 될 것이다
이 때 큐에 데이터가 없을 때까지 계속 데이터를 꺼낸다면 레벨 1에 해당하는 노드는 1 2 노드인데
레벨 2의 3 4 노드도 있기 때문에 레벨 1의 노드만 알기가 어렵다.
그렇기 때문에, 1 번 노드를 꺼내기 전에 큐의 개수를 파악해서 다른 변수 A에 저장해두고
큐에서 데이터를 꺼낼 때마다 A -= 1 를 해주면 A==0 일 때 해당하는 레벨의 노드를 전부 파악했다는 것을 알 수 있다.
A==0 일 때 다시 큐의 개수를 파악하고 위 내용을 반복한다면 모든 레벨에 해당하는 노드를 파악할 수 있다.
이중 반복문을 사용해서 큐에 데이터가 없을 때까지 배열이나 리스트에 넣는 방법도 있겠지만 반복문 안에 반복문을 넣는 이중 반복문은 효율이 좋지 않기 때문에 쓰지 않았다.
위 내용을 코드로 옮겨보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(_root);
int level = 0;
int nodeCountPerLevel = 0;
while (queue.Count > 0)
{
if(nodeCountPerLevel == 0)
{
nodeCountPerLevel = queue.Count;
}
nodeCountPerLevel--;
Node node = queue.Dequeue();
if (node != null)
{
if (node._leftNode != null)
queue.Enqueue(node._leftNode);
if (node._rightNode != null)
queue.Enqueue(node._rightNode);
}
}
기능적인 코드는 완성했으니 이제 콘솔에 출력할 수 있게 처리해보자.
2-2-3. 콘솔에 탐색 결과 출력하기
데이터를 탐색하는 동안 문자열이 계속 수정됨으로 StringBuilder 를 사용했다.
https://learn.microsoft.com/ko-kr/dotnet/standard/base-types/stringbuilder
위에서 우리는 아래 3가지 내용을 확인할 수 있어야 한다고 정리했다. 다시 한번 살펴보자
- 각 레벨에 해당하는 노드 내용을 확인할 수 있어야 한다
- 노드의 부모 노드가 누군지 알 수 있어야 한다
- 노드가 부모 기준으로 왼쪽 자식 노드인지 오른쪽 자식 노드인지 알아야 한다
부모 노드를 알 수 있게 Node 클래스를 수정해보자
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Node
{
public enum NodeType
{
NONE,
LEFT,
RIGHT,
}
public int _data = 0;
public Node _leftNode = null;
public Node _rightNode = null;
public Node _parent = null; // 부모 노드
public NodeType _nodeType = NodeType.NONE; // 부모 기준으로 노드 타입(왼쪽, 오른쪽)
}
새로 생성한 변수를 노드를 생성할 때 초기화해주자
1
2
3
4
5
6
7
// 왼쪽 자식 노드일 때
targetNode._leftNode = new Node
{
_data = data,
_parent = targetNode,
_nodeType = Node.NodeType.LEFT
};
1
2
3
4
5
6
7
// 오른쪽 자식 노드일 때
targetNode._rightNode = new Node
{
_data = data,
_parent = targetNode,
_nodeType = Node.NodeType.RIGHT
};
이제 모든 준비는 끝났다.
콘솔로 탐색 결과를 출력해보자
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
public string ShowAllNodeLocation()
{
if(_root == null)
{
return "존재하는 노드가 없습니다.";
}
StringBuilder desc = new StringBuilder();
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(_root);
int level = 0;
int nodeCountPerLevel = 0;
while (queue.Count > 0)
{
if(nodeCountPerLevel == 0)
{
desc.AppendLine();
desc.AppendLine($"===== level {level++} =====");
nodeCountPerLevel = queue.Count;
}
nodeCountPerLevel--;
Node node = queue.Dequeue();
if (node != null)
{
if (node._leftNode != null)
queue.Enqueue(node._leftNode);
if (node._rightNode != null)
queue.Enqueue(node._rightNode);
if(node._parent == null)
desc.Append($"\n루트 노드: {node._data}\n");
else
desc.Append($"\n{node._parent._data} 노드의 {node._nodeType} 자식 노드 - {node._data}\n");
}
}
return desc.ToString();
}
3. 결과
이진 탐색 트리를 기반으로 데이터를 삽입하고 제대로 삽입이 되었는지 확인하는 전체를 탐색하는 코드를 구현했다.
정상적으로 구현이 되었다면, 당연히 데이터 찾기와 삭제도 구현만 한다면 문제 없이 될 것이다.
데이터 찾기와 삭제는 개별적으로 구현해보도록 하자!!
삭제는 조금 까다롭긴 하다. 하지만 위 내용을 통해 이진 탐색 트리를 구현했고 특정 노드가 자식을 몇 개나 가지고 있는지 알 수 있기 때문에 구현하기는 쉬울 것이다.
이제 테스트를 통해 결과를 확인해보자.
아래와 같이 이진 탐색 트리를 만들 것이다.
1
2
3
4
5
6
7
8
9
10
11
BinarySearchTree binaryTree = new BinarySearchTree();
binaryTree.Insert(12);
binaryTree.Insert(6);
binaryTree.Insert(2);
binaryTree.Insert(8);
binaryTree.Insert(16);
binaryTree.Insert(14);
binaryTree.Insert(20);
Console.WriteLine(binaryTree.ShowAllNodeLocation());
정상적인 구조로 콘솔에 출력된 것을 볼 수 있다.
4. 전체 코드
전체 코드도 같이 첨부했다.
실제 작업에 사용하기 위해 만든 코드는 아니다 보니 참고용으로 보면 좋을 것 같다.
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
class Node
{
public enum NodeType
{
NONE,
LEFT,
RIGHT,
}
public int _data = 0;
public Node _leftNode = null;
public Node _rightNode = null;
public Node _parent = null;
public NodeType _nodeType = NodeType.NONE;
}
class BinarySearchTree
{
Node _root;
public string ShowAllNodeLocation()
{
if(_root == null)
{
return "존재하는 노드가 없습니다.";
}
StringBuilder desc = new StringBuilder();
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(_root);
int level = 0;
int nodeCountPerLevel = 0;
while (queue.Count > 0)
{
if(nodeCountPerLevel == 0)
{
desc.AppendLine();
desc.AppendLine($" ===== level {level++} =====");
nodeCountPerLevel = queue.Count;
}
nodeCountPerLevel--;
Node node = queue.Dequeue();
if (node != null)
{
if (node._leftNode != null)
queue.Enqueue(node._leftNode);
if (node._rightNode != null)
queue.Enqueue(node._rightNode);
if(node._parent == null)
desc.Append($"\n 루트 노드: {node._data}\n");
else
desc.Append($"\n {node._parent._data} 노드의 {node._nodeType} 자식 노드 - {node._data}\n");
}
}
return desc.ToString();
}
/// <summary>
/// 본글에는 없는 데이터 찾기 메소드
/// </summary>
/// <param name="data"></param>
public void Find(int data)
{
if(_root == null)
{
Console.WriteLine("트리가 비어 있습니다.");
return;
}
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(_root);
while(queue.Count > 0)
{
Node node = queue.Dequeue();
if (node._data == data)
{
Console.WriteLine($"{data} 를 가진 노드 발견");
return;
}
if (node != null)
{
if (node._leftNode != null)
queue.Enqueue(node._leftNode);
if (node._rightNode != null)
queue.Enqueue(node._rightNode);
}
}
Console.WriteLine($"{data}를 가진 노드가 없습니다");
}
public void Insert(int data)
{
if (_root == null)
{
_root = new Node
{
_data = data
};
return;
}
SettingNewNode(_root, data);
}
void SettingNewNode(Node targetNode,int data)
{
if (targetNode != null)
{
if (data < targetNode._data)
{
if (targetNode._leftNode != null)
{
SettingNewNode(targetNode._leftNode, data);
}
else
{
targetNode._leftNode = new Node
{
_data = data,
_parent = targetNode,
_nodeType = Node.NodeType.LEFT
};
}
}
else if(data > targetNode._data)
{
if (targetNode._rightNode != null)
{
SettingNewNode(targetNode._rightNode, data);
}
else
{
targetNode._rightNode = new Node
{
_data = data,
_parent = targetNode,
_nodeType = Node.NodeType.RIGHT
};
}
}
}
}
}