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
|
package bjc.utils.funcdata.bst;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.function.Predicate;
import bjc.utils.funcdata.bst.ITreePart.TreeLinearizationMethod;
/**
* A binary search tree, with some mild support for functional traversal.
*
* @author ben
*
* @param <T> The data type stored in the node.
*/
public class BinarySearchTree<T> {
private Comparator<T> comp;
private int nCount;
private ITreePart<T> root;
/**
* Create a new tree using the specified way to compare elements.
* @param cmp
*/
public BinarySearchTree(Comparator<T> cmp) {
nCount = 0;
comp = cmp;
}
/**
* Add a node to the binary search tree.
* @param dat The data to add to the binary search tree.
*/
public void addNode(T dat) {
nCount++;
if (root == null) {
root = new TreeNode<T>(dat, null, null);
} else {
root.add(dat, comp);
}
}
/**
* Balance the tree, and remove soft-deleted nodes for free.
* Takes O(N) time, but also O(N) space.
*/
public void balance() {
ArrayList<T> elms = new ArrayList<>(nCount);
root.forEach(TreeLinearizationMethod.INORDER, e -> elms.add(e));
root = null;
int piv = elms.size() / 2;
int adj = 0;
while((piv - adj) >= 0 && (piv + adj) < elms.size()) {
if(root == null) {
root = new TreeNode<T>(elms.get(piv), null, null);
} else {
root.add(elms.get(piv + adj), comp);
root.add(elms.get(piv - adj), comp);
}
adj++;
}
if((piv - adj) >= 0) {
root.add(elms.get(piv - adj), comp);
} else if((piv + adj) < elms.size()) {
root.add(elms.get(piv + adj), comp);
}
}
/**
* Get the root of the tree.
* @return The root of the tree.
*/
public ITreePart<T> getRoot() {
return root;
}
/**
* Soft-delete a node from the tree.
* Soft-deleted nodes stay in the tree until trim()/balance() is invoked,
* and are not included in traversals/finds.
* @param dat
*/
public void deleteNode(T dat) {
nCount--;
root.delete(dat, comp);
}
/**
* Check if a node is in the tree
* @param dat The node to check the presence of for the tree.
* @return Whether or not the node is in the tree.
*/
public boolean isInTree(T dat) {
return root.contains(dat, comp);
}
/**
* Traverse the tree in a specified way until the function fails
* @param tlm The way to linearize the tree for traversal
* @param p The function to use until it fails
*/
public void traverse(TreeLinearizationMethod tlm, Predicate<T> p) {
root.forEach(tlm, p);
}
/**
* Remove all soft-deleted nodes from the tree.
*/
public void trim() {
List<T> nds = new ArrayList<>(nCount);
traverse(TreeLinearizationMethod.PREORDER, d -> {
nds.add(d);
return true;
});
root = null;
nds.forEach(d -> addNode(d));
}
}
|
