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
| import java.util.*;
class Program {
static class BST {
public int value;
public BST left;
public BST right;
public BST(int value) {
this.value = value;
}
public BST insert(int value) {
BST currentNode = this;
while (true) {
if (value < currentNode.value) {
if (currentNode.left == null) {
BST newNode = new BST(value);
currentNode.left = newNode;
newNode.left = null;
newNode.right = null;
break;
} else {
currentNode = currentNode.left;
}
} else {
if (currentNode.right == null) {
BST newNode = new BST(value);
currentNode.right = newNode;
newNode.left = null;
newNode.right = null;
break;
} else {
currentNode = currentNode.right;
}
}
}
return this;
}
public boolean contains(int value) {
BST currentNode = this;
while (currentNode != null) {
if (value == currentNode.value) {
return true;
} else if (value < currentNode.value) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
}
return false;
}
public BST remove(int value) {
remove(value, null);
return this;
}
public void remove(int value, BST parent) {
if (value < this.value) {
if (this.left != null)
this.left.remove(value, this);
} else if (value > this.value) {
if (this.right != null)
this.right.remove(value, this);
} else {
if (left != null && right != null) {
int minVal = right.getMin();
this.value = minVal;
right.remove(this.value, this);
} else if (parent == null) {
if (left != null) {
this.value = left.value;
right = left.right;
left = left.left;
} else if (right != null) {
this.value = right.value;
left = right.left;
right = right.right;
} else {
}
} else if (parent.left == this) {
parent.left = this.left != null ? this.left : this.right;
} else if (parent.right == this) {
parent.right = this.left != null ? this.left : this.right;
}
}
}
public int getMin() {
if (left == null) {
return this.value;
} else {
return this.left.getMin();
}
}
}
}
|
