-
Notifications
You must be signed in to change notification settings - Fork 43
/
BST.java
55 lines (45 loc) · 1.2 KB
/
BST.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
// https://www.coursera.org/learn/algorithms-part1/lecture/7An9B/binary-search-trees
import java.util.LinkedList;
public class BST<Key extends Comparable<Key>, Value>
{
private Node root;
private class Node
{
private Key key;
private Value val;
private Node left, right;
public Node(Key key, Value val)
{
this.key = key;
this.val = val;
}
}
// put method via recursive way
public void put(Key key, Value val)
{ root = put(root, key, val); }
private Node put(Node x, Key key, Value val)
{
if (x == null) return new Node(key, val);
int cmp = key.copmpareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);
else if (cmp > 0) x.right = put(x.right, key, val);
else if (cmp == 0) x.val = val;
return x;
}
public void get(Key key)
{
Node x = root;
while (x != null)
{
int cmp = key.copmpareTo(x.key);
if (cmp < 0) x = x.left;
else if (cmp > 0) x = x.right;
else if (cmp == 0) return x.val;
}
return null;
}
public void delete(Key key)
{}
public Iterable<Key> iterator()
{}
}