From e528aec6d2d277338d7ddfdceba38d62eff08657 Mon Sep 17 00:00:00 2001
From: bculkin2442 <bjculkin@mix.wvu.edu>
Date: Tue, 29 Sep 2015 10:03:30 -0400
Subject: More data structure work.

Yet more imports from previous version.
---
 .../java/bjc/utils/data/bst/BinarySearchTree.java  | 128 +++++++++++++++++++++
 1 file changed, 128 insertions(+)
 create mode 100644 BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java

(limited to 'BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java')

diff --git a/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java b/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java
new file mode 100644
index 0000000..509cfcd
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/data/bst/BinarySearchTree.java
@@ -0,0 +1,128 @@
+package bjc.utils.data.bst;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Predicate;
+
+import bjc.utils.data.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));
+	}
+}
-- 
cgit v1.2.3