benchmarks/BinarySearchTree.java at master · ElephantTracksProject/benchmarks · GitHub

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
importjava.util.Random;

publicclassBinarySearchTree<TextendsComparable<T>>
{
privateTval;
privateBinarySearchTree<T> left;
privateBinarySearchTree<T> right;

publicBinarySearchTree() {
val = null;
left = null;
right = null;
 }

publicBinarySearchTree(TinitVal) {
this();
val = initVal;
 }

publicvoidinsert(TinsertVal) {
if (val == null) {
val = insertVal;
return;
 }

if (val.compareTo(insertVal) <= 0) {
if (right == null) {
right = newBinarySearchTree<T>(insertVal);
 } else {
right.insert(insertVal);
 }
 } elseif (left == null) {
left = newBinarySearchTree<T>(insertVal);
 } else {
left.insert(insertVal);
 }
 }

publicintheight() {
if (val == null) {
return0;
 } elseif (left == null && right == null) {
return1;
 } elseif (left == null) {
return1 + right.height();
 } elseif (right == null) {
return1 + left.height();
 } else {
return1 + Math.max(left.height(), right.height());
 }
 }

publicvoidinOrder() {
if (left != null) {
left.inOrder();
 }

if (val != null) {
System.out.println(val);
 }

if (right != null) {
right.inOrder();
 }
 }

publicstaticvoidmain(String[] args) {
BinarySearchTree<Integer> t1 = newBinarySearchTree<>();
BinarySearchTree<Integer> t2 = newBinarySearchTree<>();

for (inti = 0; i < 1000; i++) {
t1.insert(i);
 }

Randomrand = newRandom();

for (inti = 0; i < 1000; i++) {
t2.insert(rand.nextInt(10000));
 }

System.out.println("Height of tree 1 = " + t1.height());
t1.inOrder();

System.out.println("Height of tree 2 = " + t2.height());
t2.inOrder();
 }
}