Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Latest commit

 

History

History
History
286 lines (200 loc) · 6.91 KB
/

BST_test.java

File metadata and controls

286 lines (200 loc) · 6.91 KB
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
package datastructures.BST;
import org.junit.Assert;
import org.junit.Assert.*;
import org.junit.Test;
import org.apache.log4j.LogManager;
import org.apache.log4j.Logger;
/**
* Created with IntelliJ IDEA.
* User: thorick.chow@gmail.com
* Date: 7/4/13
* Time: 3:47 PM
*/
public class BST_test {
private static Logger log =
LogManager.getLogger(BST_test.class);
/**
* Natural insert nodes such that the tree is balanced on insert
*
*/
//@Test
public void test_orderedNaturalInsertion() {
p("\n\n start test test_orderedNaturalInsertion");
BST<String> bst = make3levelBalanced();
}
//@Test
public void test_rootInsertion() {
p("\n\n start test test_rootInsertion");
p(" first step: create a balanced base tree");
BST<String> bst = make3levelBalanced();
p("\n\n now do root insert of new node");
Node<String> n = new StringNode("AAGG", "AAGG");
bst.insertRoot(n);
String treeString = bst.printTree();
p("after insert of "+n.toString()+", tree is ");
p(treeString);
}
//@Test
public void test_remove00_fromMiddle() {
p("\n\n start test test_remove00_fromMiddle");
p(" first step: create a balanced base tree");
BST<String> bst = make3levelBalanced();
Node<String> n = new StringNode("AANN", "AANN");
p("\n\n now do remove of node="+n.toString());
bst.remove(n);
p("\n\n after removal tree is now"+bst.printTree());
}
//@Test
public void test_remove01_fromLeaf() {
p("\n\n start test test_remove01_fromLeaf");
p(" first step: create a balanced base tree");
BST<String> bst = make3levelBalanced();
Node<String> n = new StringNode("AAKK", "AAKK");
p("\n\n now do remove of node="+n.toString());
bst.remove(n);
p("\n\n after removal tree is now"+bst.printTree());
}
@Test
public void test_remove02_fromRoot() {
p("\n\n start test test_remove02_fromRoot");
p(" first step: create a balanced base tree");
BST<String> bst = make3levelBalanced();
Node<String> n = new StringNode("AAII", "AAII");
p("\n\n now do remove of node="+n.toString());
bst.remove(n);
p("\n\n after removal tree is now"+bst.printTree());
// construct the expected result tree
// AAKK
// AAEE AANN
// AACC AAFF NULL AATT
BST<String> expected = new BST<String>();
Node<String> node = new StringNode("AAKK", "AAKK");
expected.insertRoot(node);
node = new StringNode("AAEE", "AAEE");
expected.insert(node);
node = new StringNode("AANN", "AANN");
expected.insert(node);
node = new StringNode("AACC", "AACC");
expected.insert(node);
node = new StringNode("AAFF", "AAFF");
expected.insert(node);
node = new StringNode("AATT", "AATT");
expected.insert(node);
int retVal = bst.compareTo(expected);
String message = "";
if (retVal != 0) {
message = "expected tree"+expected.printTree()+
"\n got tree"+bst.printTree();
}
Assert.assertEquals(message, 0, retVal);
/*
Node<String> t = bst.getRoot();
String expected = "AAKK";
Assert.assertEquals("expected root=" + expected + ", but we got " + t.toString(), expected, t);
Node<String> tL = t.getL();
expected = "AAEE";
Assert.assertEquals("expected node=" + expected + ", but we got " + tL.toString(), expected, tL);
Node<String> tR = t.getR();
expected = "AANN";
Assert.assertEquals("expected node=" + expected + ", but we got " + tR.toString(), expected, tR);
*/
}
//@Test
public void test_partition01() {
p("\n\n start test test_partition01");
p(" first step: create a balanced base tree");
BST<String> bst = make3levelBalanced();
p("\n now partition at k=2, set the 3rd smallest key as the root");
Node<String> newRoot = bst.partition(2);
p(" newly partitioned tree"+newRoot.printTree(4));
}
//@Test
public void test_partition02() {
p("\n\n start test test_partition02");
p(" first step: create a balanced base tree");
BST<String> bst = make3levelBalanced();
p("\n now partition at k=5, set the 6th smallest key as the root");
Node<String> newRoot = bst.partition(5);
p(" newly partitioned tree"+newRoot.printTree(4));
}
//@Test
public void test_balance00() {
p("\n\n start test test_balance00");
p(" first step: create a balanced base tree\n\n");
BST<String> bst = make3levelBalanced();
p("\n now partition at k=5, set the 6th smallest key as the root\n\n");
Node<String> newRoot = bst.partition(5);
p(" newly partitioned tree"+newRoot.printTree(4));
p("\n now rebalance the partitioned tree\n\n");
bst.setRoot(newRoot);
newRoot = bst.balance();
p("\n balanced tree is"+newRoot.printTree(4));
}
//@Test
public void test_balance01() {
p("\n\n start test test_balance01\n\n");
p(" create a worst case linear tree\n");
BST<String> bst = new BST<String>();
Node <String> n = new StringNode("AAAA", "AAAA");
bst.insert(n);
n = new StringNode("CCCC", "CCCC");
bst.insert(n);
n = new StringNode("EEEE", "EEEE");
bst.insert(n);
n = new StringNode("GGGG", "GGGG");
bst.insert(n);
n = new StringNode("IIII", "IIII");
bst.insert(n);
n = new StringNode("KKKK", "KKKK");
bst.insert(n);
p(" linear tree is"+bst.printTree());
bst.balance();
p(" balanced tree is"+bst.printTree());
}
public BST make3levelBalanced() {
BST<String> bst = new BST<String>();
// root node
Node<String> n = new StringNode("AAII", "AAII");
bst.insert(n);
String treeString = bst.printTree();
p("after insert of "+n.toString()+", tree is ");
p(treeString);
// now left child
n = new StringNode("AAEE", "AAEE");
bst.insert(n);
treeString = bst.printTree();
p("after insert of "+n.toString()+", tree is ");
p(treeString);
// now right child
n = new StringNode("AANN", "AANN");
bst.insert(n);
treeString = bst.printTree();
p("after insert of "+n.toString()+", tree is ");
p(treeString);
// start 3rd leaf level
n = new StringNode("AACC", "AACC");
bst.insert(n);
treeString = bst.printTree();
p("after insert of "+n.toString()+", tree is ");
p(treeString);
n = new StringNode("AAFF", "AAFF");
bst.insert(n);
treeString = bst.printTree();
p("after insert of "+n.toString()+", tree is ");
p(treeString);
n = new StringNode("AAKK", "AAKK");
bst.insert(n);
treeString = bst.printTree();
p("after insert of "+n.toString()+", tree is ");
p(treeString);
n = new StringNode("AATT", "AATT");
bst.insert(n);
treeString = bst.printTree();
p("after insert of "+n.toString()+", tree is ");
p(treeString);
return bst;
}
private void p(String s) {
log.debug(s);
}
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.