forked from espadrine/succinct-cybernetics
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary-search.js
More file actions
140 lines (127 loc) · 3.88 KB
/
Copy pathbinary-search.js
File metadata and controls
140 lines (127 loc) · 3.88 KB
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
// A binary search tree is a binary tree (a rooted tree with vertices with up to
// 2 children) where every vertex on the left branch holds keys lower than that
// of the current vertex, and every vertex on the right branch holds keys
// higher.
function BinarySearchTree() {}
BinarySearchTree.prototype = {
key: null,
// Not having a value can make this work like a set
// with a findMin over the keys.
value: null,
left: null,
right: null,
// Ensure that search(key) returns the value for that key.
// O(log n) with random input, O(n) worst-case.
insert: function(key, value) {
if (this.key == null) {
// This is below a leaf or the tree is empty.
this.key = key;
this.value = value;
} else if (key < this.key) {
this.leftInsert(key, value);
} else if (key > this.key) {
this.rightInsert(key, value);
} else {
// this.key == key; the key was already there.
}
},
leftInsert: function(key, value) {
if (this.left == null) {
this.left = new BinarySearchTree();
}
this.left.insert(key, value);
},
rightInsert: function(key, value) {
if (this.right == null) {
this.right = new BinarySearchTree();
}
this.right.insert(key, value);
},
// Return the value that was inserted.
// O(log n) with random input, O(n) worst-case.
search: function(key) {
if (this.key == null) {
// We reached a leaf without success; that key was never inserted.
return null;
} else if (key < this.key) {
if (this.left != null) {
return this.left.search(key);
} else { return null; }
} else if (key > this.key) {
if (this.right != null) {
return this.right.search(key);
} else { return null; }
} else {
return this.value;
}
},
// Ensure that search(key) returns null.
// O(log n) with random input, O(n) worst-case.
delete: function(key) {
if (this.key == null) {
return;
} else if (key < this.key) {
if (this.left != null) {
this.left.delete(key);
}
} else if (key > this.key) {
if (this.right != null) {
this.right.delete(key);
}
} else {
// We found the key to delete.
if (this.left == null && this.right == null) {
// We have no children, we just disappear.
this.key = this.value = null;
} else if (this.left == null) {
// We have one child, we switch place with it.
this.replaceWith(this.right);
} else if (this.right == null) {
this.replaceWith(this.left);
} else {
// We have two children. Replace with the biggest vertex on the left,
// and delete that biggest vertex downward.
var max = this.left.findMax();
// It cannot be null here.
this.key = max.key;
this.value = max.value;
this.left.delete(max.key);
}
}
},
replaceWith: function(tree) {
this.key = tree.key;
this.value = tree.value;
this.left = tree.left;
this.right = tree.right;
},
// Return the biggest vertex.
findMax: function() {
if (this.right == null) {
return this;
} else {
return this.right.findMax();
}
},
// In-order walk. O(n).
walk: function(f) {
if (this.left != null) {
this.left.walk(f);
}
if (this.key != null) {
f(this.key, this.value);
}
if (this.right != null) {
this.right.walk(f);
}
},
};
// Usage.
var tree = new BinarySearchTree();
tree.insert("orange", "A citrus fruit with a slightly sour flavour.");
tree.insert("banana", "An elongated curved tropic fruit with a creamy flesh.");
tree.insert("strawberry", "A sweet fruit of a plant of the genus Fragaria.");
console.log("An orange is " + tree.search("orange"));
tree.delete("orange");
console.log("Once deleted, an orange is " + tree.search("orange") + ".");
tree.walk(function(key, value) { console.log("- " + key + ": " + value); });