/
bst.js
73 lines (54 loc) · 1.66 KB
/
bst.js
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
Benchmark.prototype.setup = function() {
var BinarySearchTree = function() {
this.items = [];
};
BinarySearchTree.prototype = {
leftChildIndex: function(index) {
return index * 2;
},
rightChildIndex: function(index) {
return index * 2 + 1;
},
getValueOf: function(index) {
var candidate = this.items[index - 1];
return (typeof candidate !== 'undefined' ? candidate : null);
},
add: function(item) {
var node = 1;
while (this.getValueOf(node) !== null) {
if (this.getValueOf(node) > item) {
node = this.leftChildIndex(node);
} else {
node = this.rightChildIndex(node);
}
}
this.items[node - 1] = item;
},
find: function(item) {
var node = 1;
while (this.getValueOf(node) !== null) {
if (this.getValueOf(node) > item) {
node = this.leftChildIndex(node);
} else if (this.getValueOf(node) < item) {
node = this.rightChildIndex(node);
} else {
break;
}
}
return this.getValueOf(node);
}
};
// now set up the values
var arr = [];
var vals = [];
var bst = new BinarySearchTree();
for (var i = 0; i < 100000; i++) {
candidate = Math.floor(Math.random() * 10000000);
// we store the values in a separate
// array just so it's outside of the other
// data structures
vals.push(candidate);
arr.push(candidate);
bst.add(candidate);
}
};