-
Notifications
You must be signed in to change notification settings - Fork 3
/
BSTUtils.java
45 lines (38 loc) · 1.53 KB
/
BSTUtils.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
package htsi.bst;
import java.util.*;
import java.util.Map.*;
import java.util.stream.*;
class BSTUtils {
public static <K extends Comparable<K>, V> boolean isValid(BST<K, V> bst) {
if (bst.isLeaf()) {
return true;
}
return isValid(bst.left()) && isValid(bst.right())
&& keys(bst.left()).allMatch(k -> k.compareTo(bst.key()) < 0)
&& keys(bst.right()).allMatch(k -> k.compareTo(bst.key()) > 0);
}
@SuppressWarnings("OptionalUsedAsFieldOrParameterType")
private static <K extends Comparable<K>, V> Stream<K> keys(Optional<BST<K, V>> bst) {
return bst.map(BST::keys).orElse(Collections.emptyList()).stream();
}
@SuppressWarnings("OptionalUsedAsFieldOrParameterType")
private static <K extends Comparable<K>, V> boolean isValid(Optional<BST<K, V>> optionalBST) {
return optionalBST.map(BSTUtils::isValid).orElse(true);
}
@SuppressWarnings("unchecked")
public static <K extends Comparable<K>, V> boolean equivalent(BST<K, V> bst1, BST<K, V> bst2) {
return new HashSet<>(bst1.toList()).equals(new HashSet<>(bst2.toList()));
}
// insertions Leaf = [ ]
// insertions (Branch l k v r ) = (k , v ) : insertions l + insertions r
public static <K extends Comparable<K>, V> List<Entry<K, V>> insertions(BST<K, V> bst) {
if (bst.isLeaf()) {
return Collections.emptyList();
}
List<Entry<K, V>> insertions = new ArrayList<>();
insertions.add(bst.entry);
bst.left().ifPresent(left -> insertions.addAll(insertions(left)));
bst.right().ifPresent(right -> insertions.addAll(insertions(right)));
return insertions;
}
}