-
Notifications
You must be signed in to change notification settings - Fork 1
/
BinarySearchTree.java
113 lines (99 loc) · 1.87 KB
/
BinarySearchTree.java
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
package Data_Structures;
public class BinarySearchTree {
Node root;
static class Node {
int key;
int value;
Node l;
Node r;
Node p;
public Node(int key, int value, Node p) {
this.key = key;
this.value = value;
this.p = p;
}
}
Node search(Node t, int key) {
if (t == null || t.key == key)
return t;
if (key < t.key)
return search(t.l, key);
else
return search(t.r, key);
}
public Node search(int key) {
return search(root, key);
}
Node insert(Node t, Node p, int key, int value) {
if (t == null) {
t = new Node(key, value, p);
} else {
if (key < t.key)
t.l = insert(t.l, t, key, value);
else
t.r = insert(t.r, t, key, value);
}
return t;
}
public void insert(int key, int value) {
root = insert(root, null, key, value);
}
void replace(Node a, Node b) {
if (a.p == null)
root = b;
else if (a == a.p.l)
a.p.l = b;
else
a.p.r = b;
if (b != null)
b.p = a.p;
}
void remove(Node t, int key) {
if (t == null)
return;
if (key < t.key)
remove(t.l, key);
else if (key > t.key)
remove(t.r, key);
else if (t.l != null && t.r != null) {
Node m = t.r;
while (m.l != null)
m = m.l;
t.key = m.key;
t.value = m.value;
replace(m, m.r);
} else if (t.l != null) {
replace(t, t.l);
} else if (t.r != null) {
replace(t, t.r);
} else {
replace(t, null);
}
}
public void remove(int key) {
remove(root, key);
}
void print(Node t) {
if (t != null) {
print(t.l);
System.out.print(t.key + ":" + t.value + " ");
print(t.r);
}
}
public void print() {
print(root);
System.out.println();
}
// Usage example
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(3, 1);
tree.insert(2, 2);
tree.insert(4, 5);
tree.print();
tree.remove(2);
tree.remove(3);
tree.print();
tree.remove(4);
}
}