-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathBinarySearchTree.java
More file actions
332 lines (315 loc) · 11.5 KB
/
Copy pathBinarySearchTree.java
File metadata and controls
332 lines (315 loc) · 11.5 KB
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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
public class BinarySearchTree<E extends Comparable<E>> extends BinaryTree<E> implements ITree<E>{
protected enum Position {
LEFT, RIGHT
};
public BinarySearchTree(){
}
public Node<E> getNode(E data){
Node<E> node = root;
while(node != null){
if(data.compareTo(node.element) == 0){
return node;
}else if(data.compareTo(node.element) < 0){
node = node.left;
}else{
node = node.right;
}
}
return null;
}
protected Node<E> getLeafLeftNode(Node<E> node){
Node<E> tNode = node;
if(tNode == null)
return tNode;
while(tNode.left != null){
tNode = tNode.left;
}
return tNode;
}
@SuppressWarnings("unchecked")
@Override
public boolean add(E data){
Node<E> newNode = null;
if(this.creator == null)
newNode = new Node<E>(data);
else
newNode = this.creator.createNewNode(data, null);
if(root == null){
root = newNode;
root.parent = null;
}else{
Node<E> parent;
Node<E> t = root;
int cmp;
do{
parent = t;
cmp = data.compareTo(parent.element);
if(cmp < 0){
t = t.left;
}else if(cmp > 0){
t = t.right;
}else{
// 얼레는 그냥 덮어씌우는게 일반적인듯..?
System.out.println("데이터 중복안됨");
return false;
}
}while( t != null);
if(cmp < 0){
parent.left = newNode;
newNode.parent = parent;
}else{
parent.right = newNode;
newNode.parent = parent;
}
}
return true;
}
@SuppressWarnings("unchecked")
protected Node<E> addAndGetNode(E data){
Node<E> newNode = null;
if(this.creator == null)
newNode = new Node<E>(data);
else
newNode = this.creator.createNewNode(data, null);
if(root == null){
root = newNode;
root.parent = null;
}
insertNode(root, newNode);
return newNode;
}
// recursive add
private Node<E> insertNode(Node<E> currentParent, Node<E> newNode) {
if (currentParent == null)
return newNode;
else if (newNode.element.compareTo(currentParent.element) > 0){
currentParent.right = insertNode(currentParent.right, newNode);
currentParent.right.parent = currentParent;
}
else if (newNode.element.compareTo(currentParent.element) < 0 ){
currentParent.left = insertNode(currentParent.left, newNode);
currentParent.left.parent = currentParent;
}
return currentParent;
}
@Override
public E remove(E data){
Node<E> removeNode = getNode(data);
Node<E> replaceNode = getReplacementNode(removeNode);
replaceNodeWithNode(removeNode, replaceNode);
return data;
}
public Node<E> removeAndGetNode(E data){
Node<E> removeNode = getNode(data);
if(removeNode != null){
Node<E> replaceNode = getReplacementNode(removeNode);
replaceNodeWithNode(removeNode, replaceNode);
}
return removeNode;
}
protected Node<E> getReplacementNode(Node<E> nodeToRemoved) {
Node<E> replaceNode = null;
if(nodeToRemoved.left != null && nodeToRemoved.right == null){
replaceNode = nodeToRemoved.left;
}else if(nodeToRemoved.right != null && nodeToRemoved.left == null){
replaceNode = nodeToRemoved.right;
}else if(nodeToRemoved.left != null && nodeToRemoved.right != null){
// 오른쪽 노드에서 가장 왼쪽에 있는 노드를 찾는다.
// 왼쪽 노드에서 가장 오른쪽에 있는 노드를 찾아도 된다.
replaceNode = getLeafLeftNode(nodeToRemoved.right);
if(replaceNode == null){
// 삭제할 노드에 오른쪽 노드가 왼쪽 노드가 없다면
// 그냥 오른쪽 노드로 대신함
replaceNode = nodeToRemoved.right;
}
}
return replaceNode;
}
protected void replaceNodeWithNode(Node<E> nodeToRemoved, Node<E> replacementNode) {
// leaf 노드를 삭제한다면 replacementNode 가 null 일수도 있다.
if(replacementNode != null){
// 대체 할 노드의 오른쪽 왼쪽을 바꾸기 전에 미리 저장해 놓는다. 처음에 대체할 노드의 오른쪽 왼쪽부터 바꾼다.
// 1.왼쪽에 가장 오른쪽을 선택했을경우 데체할 노드의 왼쪽 자식은 있을수도 있다.
Node<E> replacementNodeLeft = replacementNode.left;
// 2.오른쪽에 가징왼쪽을 선택했을경우 대체할 노드의 오른쪽 자식은 있을수도 있다.
Node<E> replacementNodeRight = replacementNode.right;
// 대체할 노드 <-> 삭제할 노드의 양쪽 자식
// ** 삭제할 노드와 대체할노드가 바로 붙어 있다면 삭제할 노드의 부모를 대체할노드로 바꿔주기만하면됨**
// 삭제할 노드에 양쪽 자식을 대체할 노드에 넣어준다.
Node<E> nodeToRemoveLeft = nodeToRemoved.left;
// 삭제할 노드의 왼쪽이 있다면, **근데 삭제할노드의 왼쪽이 대체할노드가 아니라면**
if(nodeToRemoveLeft != null && !nodeToRemoveLeft.equals(replacementNode)){
replacementNode.left = nodeToRemoveLeft;
nodeToRemoveLeft.parent = replacementNode;
}
Node<E> nodeToRemoveRight = nodeToRemoved.right;
// 삭제할 노드의 오른쪽이 있다면, **근데 삭제할 노드의 오른쪽이 대체할 노드가 아니라면**
if(nodeToRemoveRight != null && !nodeToRemoveRight.equals(replacementNode)){
replacementNode.right = nodeToRemoveRight;
nodeToRemoveRight.parent = replacementNode;
}
// 대체할 노드의 부모 <-> 대체할 노드의 자식 (대체할 노드가 빠지므로)
// 삭제할 노드의 오른쪽 노드의 맨왼쪽 노드(대체할노드) 의 오른쪽 자식은 있을수도 있다.
Node<E> replacementParent = replacementNode.parent;
// 대체할 노드의 부모가 있고, **대체할 노드의 부모가 삭제할것은 아니라면**
if(replacementParent != null && !replacementParent.equals(nodeToRemoved)){
// 대체할 노드가 부모의 왼쪽이라면(1.오른쪽에서 가장 왼쪽을 선택했을경우)
if(replacementParent.left != null && replacementParent.left.equals(replacementNode)){
// 대체할 노드의 오른쪽을 대체할 노드의 부모의 왼쪽으로 연결해준다.
replacementParent.left = replacementNodeRight;
if(replacementNodeRight != null){
// 만약 대체노드의 오른쪽이 자식이 있다면 대체할 노드의 오른쪽의 부모를 대체할 노드의 부모로
replacementNodeRight.parent = replacementParent;
}
}else if(replacementParent.right != null && replacementParent.right.equals(replacementNode)){
// 1.삭제할 노드의 오른쪽의 가징 왼쪽 선택했으므로 대체할 노드의 부모의 오른쪽에 있을일이 없다.
replacementParent.right = replacementNodeLeft;
if(replacementNodeLeft != null){
replacementNodeLeft.parent = replacementParent;
}
}
}
}
// 삭제할 노드의 부모 <-> 대체 노드
Node<E> parent = nodeToRemoved.parent;
if(parent == null){
// 삭제할 노드가 루트 노드
root = replacementNode;
if(root != null)
root.parent = null;
}else if(parent.left != null && parent.left.equals(nodeToRemoved)){
// 삭제할노드가 부모의 왼쪽 이라면
parent.left = replacementNode;
if(replacementNode != null)
replacementNode.parent = parent;
}else if(parent.right != null && parent.right.equals(nodeToRemoved)){
// 삭제할노드가 부모의 오른쪽 이라면
parent.right = replacementNode;
if(replacementNode != null)
replacementNode.parent = parent;
}
}
public E remove2(E data){
Node<E> removeNode = getNode(data);
if(removeNode.left == null && removeNode.right == null){
// leaf node
Node<E> parent = removeNode.parent;
if(parent.left == removeNode){
parent.left = null;
}else if(parent.right == removeNode){
parent.right = null;
}
removeNode = null;
}
else if(removeNode.left != null && removeNode.right == null){
// 자식이 한개밖에없다.
Node<E> parent = removeNode.parent;
Node<E> child = removeNode.left;
if(parent.left == removeNode){
parent.left = child;
}else if(parent.right == removeNode){
parent.right = child;
}
removeNode = null;
}
else if(removeNode.right != null && removeNode.left == null){
// 자식이 한개밖에없다.
Node<E> parent = removeNode.parent;
Node<E> child = removeNode.right;
if(parent.left == removeNode){
parent.left = child;
}else if(parent.right == removeNode){
parent.right = child;
}
removeNode = null;
}
else if(removeNode.right != null && removeNode.left != null){
Node<E> parent = removeNode.parent;
Node<E> replaceNode = getLeafLeftNode(removeNode.right);
//System.out.println(replaceNode.element);
if(parent.left == removeNode){
parent.left = replaceNode;
replaceNode.left = removeNode.left;
if(replaceNode.right == null){
if(replaceNode != removeNode.right)
replaceNode.right = removeNode.right;
}
replaceNode.parent.left = null;
}else if(parent.right == removeNode){
parent.right = replaceNode;
replaceNode.left = removeNode.left;
// 대신할 노드에 왼쪽은 항상 없지만 오른쪽은 있을수도 있다.
if(replaceNode.right == null){
// 삭제할 노드에 오른쪽 노드가 대신할노드랑 같으면 서로 참조하게됨
if(replaceNode != removeNode.right)
replaceNode.right = removeNode.right;
}
replaceNode.parent.left = null;
}
removeNode = null;
}
return data;
}
public void rotateLeft(Node<E> node){
System.out.println("ROTATE LEFT AT " + node);
Node<E> parent = node.parent;
Position parentPosition = null;
if(parent != null){
if(node.equals(parent.left)){
parentPosition = Position.LEFT;
}else{
parentPosition = Position.RIGHT;
}
}
Node<E> greater = node.right;
Node<E> lesser = greater.left;
node.right = null;
greater.left = node;
node.parent = greater;
node.right = lesser;
if(lesser != null)
lesser.parent = node;
if(parentPosition != null){
if(parentPosition == Position.LEFT){
parent.left = greater;
}else{
parent.right = greater;
}
greater.parent = parent;
}else{
root = greater;
greater.parent = null;
}
}
public void rotateRight(Node<E> node){
System.out.println("ROTATE RIGHT AT " + node);
Node<E> parent = node.parent;
Position parentPosition = null;
if(parent != null){
if(node.equals(parent.left)){
parentPosition = Position.LEFT;
}else{
parentPosition = Position.RIGHT;
}
}
Node<E> lesser = node.left;
Node<E> greater = lesser.right;
node.left = null;
lesser.right = node;
node.parent = lesser;
node.left = greater;
if(greater != null)
greater.parent = node;
if(parentPosition != null){
if(parentPosition == Position.LEFT){
parent.left = lesser;
}else{
parent.right = lesser;
}
lesser.parent = parent;
}else{
root = lesser;
lesser.parent = null;
}
}
}