안녕하세요 :) 오늘은 Binary Tree와 Tree Traversal 바탕으로 Binary Search Tree를 만들어보겠습니다.
!) 자료구조 Tree를 잘 모르시다면?
!) 자료구조 Binary Tree를 잘 모르시다면?
!) 트리 순회를 잘 모르시다면?
1) What is BST?
이진트리의 탐색을 목적으로 저장할 데이터의 크기(key)에 따라 노드의 위치를 정한 트리입니다.
BST 역시 BT와 동일한 구조를 가지고 있습니다.
1) 모든 node는 서로 다른 key값을 가진다.
2) left-child의 경우, 그 parent보다 적은 값의 key를 가진다.
3) right-child의 경우, 그 parent보다 큰 값의 key를 가진다.
2) BT Operatrion
- Object find(Object k) : k값의 node를 찾습니다.
- ArrayList findAll(Object k) : k값을 지니고 있는 모든 노드를 찾습니다.
- Object insert(Object k) : k를 값으로 하는 node를 추가합니다.
- Object remove(Object k) : k값을(가지고 있는 node를) 제거합니다.
3) Find
|
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
|
public Object find(Object k) {
MyBinNode temp = this.root();
Object result = null;
while(true) {
if(temp == null) break;
if((int)temp.element() == (int)k) {
// find key
result = temp;
break;
}
else if((int)temp.element() < (int)k) {
// case - key is bigger than temp
temp = temp.right();
}
else {
// case - key is smaller than temp
temp = temp.left();
}
}
if(result == null)
System.out.println("Can't find Key!");
else
System.out.println("FIND KEY : " + ((MyBinNode)result).element());
return result;
}
|
cs |
1) 루트부터 탐색을 시작한다.
2) 찾고자 하는 값(k)과 node의 key값이 같으면 탐색을 멈추고 검색에 성공한다.
3) k값이 node의 key값보다 작다면 그 node의 left child로, 크다면 right child로 이동한다.
4) (3)의 과정을 반복하고 찾지 못한다면 검색을 실패한다.
4) Insert
|
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
|
public Object insert(Object k) {
MyBinNode temp = this.root();
while(true) {
if((int)temp.element() == (int)k) {
// case - key is already exist in tree
if(super.hasLeft(temp)) {
temp = temp.left();
}
else if(super.hasRight(temp)) {
temp = temp.right();
}
else {
System.out.println("Same Key Exception Occurs - same key no child !");
break;
}
}
else if((int)temp.element() < (int)k) {
// case - key is bigger than temp
if(!super.hasRight(temp)) {
// insert do it
super.inserRight(temp, k);
break;
}
else {
// continue search
temp = temp.right();
}
}
else {
// case - key is smaller than temp
if(!super.hasLeft(temp)) {
// insert do it
super.inserLeft(temp, k);
break;
}
else {
// continue search
temp = temp.left();
}
}
}
return k;
}
|
cs |
1) insert하고자 하는 k의 값을 트리에서 찾는다.
2) 만약, search에 성공한다면 이미 key값이 존재하므로 insert를 실패한다.
3) 찾지 못한다면, 그 자리에 k의 값을 key로 하는 node를 추가한다.
5) Remove
|
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
|
public Object remove(Object k) throws TwoChildrenException {
MyBinNode temp = this.root();
Object result = null;
while(true) {
if(temp == null) break;
if((int)temp.element() == (int)k) {
// find key and remove
if(this.hasLeft(temp) && this.hasRight(temp)) {
// case - internal both child
// find next node & copy & remove
MyBinNode nextNode = this.nextNode(temp);
// MyBinNode nextNode = this.nextNode2(temp);
temp.setElement(nextNode.element());
MyBinNode nextNodeParent = (MyBinNode)nextNode.parent();
result = super.remove(nextNode);
}
else {
// case - one child & external
result = super.remove(temp);
}
break;
}
else if((int)temp.element() < (int)k) {
// case - key is bigger than temp
temp = temp.right();
}
else {
// case - key is smaller than temp
temp = temp.left();
}
}
if(result == null)
System.out.println("Can't remove Key !");
return result;
}
}
|
cs |
1) insert하고자 하는 k의 값을 트리에서 찾는다.
2) 만약, search에 성공한다면 그 node를 삭제한다
3) 찾지 못한다면, remove를 실패한다.
case1. remove 할 node가 external 할 경우
단순 remove 연산을 진행합니다.
case2. remove 할 node의 children이 하나일 경우
children을 삭제한 node의 자리로 올려줍니다.
(위의 코드에선 external noded의 remove와 똑같은데, Binary Tree remove 연산에서 이 작업을 수행해줍니다.)
case2. remove 할 node의 children이 둘일 경우
삭제된 node의 nextNode를 찾은 후, 그 node를 삭제된 node의 자리로 옮겨주고, parent-child관계로 재정의 해줍니다.
6) 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
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
|
import java.util.ArrayList;
public class MyBST extends MyBinTree {
// Constructor
MyBST() { super(); }
MyBST(Object e) { super(e); }
public void inOrder(MyBinNode v) {
if(this.hasLeft(v)) {
inOrder(this.left(v));
}
System.out.print(v.element()+" ");
if(this.hasRight(v)) {
inOrder(this.right(v));
}
}
// using inorder
private MyBinNode nextNode(MyBinNode v) {
ArrayList inorderList = new ArrayList();
this.inorderNextNode(inorderList, v);
MyBinNode result = null;
for(int i=0; i<inorderList.size(); i++) {
MyBinNode temp = (MyBinNode)inorderList.get(i);
if((int)temp.element() == (int)v.element()) {
result = (MyBinNode)inorderList.get(i+1);
// System.out.println("@@@" + result.element());
break;
}
}
return result;
}
// using way
private MyBinNode nextNode2(MyBinNode v) {
MyBinNode result = null;
if(super.hasRight(v)) {
MyBinNode temp = v.right();
while(true) {
if(super.hasLeft(temp)) {
temp = temp.left();
}
else {
result = temp;
// System.out.println("@@@" + result.element());
break;
}
}
}
else {
System.out.println("No Next Node!");
}
return result;
}
public void inorderNextNode(ArrayList al, MyBinNode v) {
if(this.hasLeft(v)) {
inorderNextNode(al, super.left(v));
}
al.add(v);
if(this.hasRight(v)) {
inorderNextNode(al, super.right(v));
}
}
public Object find(Object k) {
MyBinNode temp = this.root();
Object result = null;
while(true) {
if(temp == null) break;
if((int)temp.element() == (int)k) {
// find key
result = temp;
break;
}
else if((int)temp.element() < (int)k) {
// case - key is bigger than temp
temp = temp.right();
}
else {
// case - key is smaller than temp
temp = temp.left();
}
}
if(result == null)
System.out.println("Can't find Key!");
else
System.out.println("FIND KEY : " + ((MyBinNode)result).element());
return result;
}
public ArrayList findAll(Object k) {
ArrayList findList = new ArrayList();
// using inorder traversal
this.inorderfindAll(findList, this.root(), k);
System.out.println("FIND ALL KEY : " + (int)k + ", COUNT : " + findList.size());
return findList;
}
public void inorderfindAll(ArrayList al, MyBinNode v, Object k) {
if(this.hasLeft(v)) {
inorderfindAll(al, this.left(v), k);
}
if((int)v.element() == (int)k)
al.add(k);
if(this.hasRight(v)) {
inorderfindAll(al, this.right(v), k);
}
}
public Object insert(Object k) {
MyBinNode temp = this.root();
while(true) {
if((int)temp.element() == (int)k) {
// case - key is already exist in tree
if(super.hasLeft(temp)) {
temp = temp.left();
}
else if(super.hasRight(temp)) {
temp = temp.right();
}
else {
System.out.println("Same Key Exception Occurs - same key no child !");
break;
}
}
else if((int)temp.element() < (int)k) {
// case - key is bigger than temp
if(!super.hasRight(temp)) {
// insert do it
super.inserRight(temp, k);
break;
}
else {
// continue search
temp = temp.right();
}
}
else {
// case - key is smaller than temp
if(!super.hasLeft(temp)) {
// insert do it
super.inserLeft(temp, k);
break;
}
else {
// continue search
temp = temp.left();
}
}
}
return k;
}
public Object remove(Object k) throws TwoChildrenException {
MyBinNode temp = this.root();
Object result = null;
while(true) {
if(temp == null) break;
if((int)temp.element() == (int)k) {
// find key and remove
if(this.hasLeft(temp) && this.hasRight(temp)) {
// case - internal both child
// find next node & copy & remove
MyBinNode nextNode = this.nextNode(temp);
// MyBinNode nextNode = this.nextNode2(temp);
temp.setElement(nextNode.element());
MyBinNode nextNodeParent = (MyBinNode)nextNode.parent();
result = super.remove(nextNode);
}
else {
// case - one child & external
result = super.remove(temp);
}
break;
}
else if((int)temp.element() < (int)k) {
// case - key is bigger than temp
temp = temp.right();
}
else {
// case - key is smaller than temp
temp = temp.left();
}
}
if(result == null)
System.out.println("Can't remove Key !");
return result;
}
}
|
cs |
최근댓글