From 8a8b457c98e207d809a7616e73eb59bfe197a7a5 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Thu, 31 Mar 2016 11:43:21 -0400 Subject: More code maintenance --- .../bjc/utils/funcdata/bst/BinarySearchTree.java | 129 ++++++++++++++------- 1 file changed, 84 insertions(+), 45 deletions(-) (limited to 'BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java') diff --git a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java index 2785626..ec0e4df 100644 --- a/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java +++ b/BJC-Utils2/src/main/java/bjc/utils/funcdata/bst/BinarySearchTree.java @@ -20,41 +20,42 @@ public class BinarySearchTree { /** * The comparator for use in ordering items */ - private Comparator comp; + private Comparator comparator; /** * The current count of elements in the tree */ - private int nCount; + private int elementCount; /** * The root element of the tree */ - private ITreePart root; + private ITreePart rootElement; /** * Create a new tree using the specified way to compare elements. * * @param cmp + * The thing to use for comparing elements */ public BinarySearchTree(Comparator cmp) { - nCount = 0; - comp = cmp; + elementCount = 0; + comparator = cmp; } /** * Add a node to the binary search tree. * - * @param dat + * @param element * The data to add to the binary search tree. */ - public void addNode(T dat) { - nCount++; + public void addNode(T element) { + elementCount++; - if (root == null) { - root = new BinarySearchTreeNode<>(dat, null, null); + if (rootElement == null) { + rootElement = new BinarySearchTreeNode<>(element, null, null); } else { - root.add(dat, comp); + rootElement.add(element, comparator); } } @@ -63,45 +64,79 @@ public class BinarySearchTree { * time, but also O(N) space. */ public void balance() { - FunctionalList elms = new FunctionalList<>(); + FunctionalList elements = new FunctionalList<>(); - root.forEach(TreeLinearizationMethod.INORDER, e -> elms.add(e)); + // Add each element to the list in sorted order + rootElement.forEach(TreeLinearizationMethod.INORDER, + element -> elements.add(element)); - root = null; + // Clear the tree + rootElement = null; - int piv = elms.getSize() / 2; - int adj = 0; + // Set up the pivot and adjustment for readding elements + int pivot = elements.getSize() / 2; + int pivotAdjustment = 0; - while ((piv - adj) >= 0 && (piv + adj) < elms.getSize()) { - if (root == null) { - root = new BinarySearchTreeNode<>(elms.getByIndex(piv), - null, null); + // Add elements until there aren't any left + while (adjustedPivotInBounds(elements, pivot, pivotAdjustment)) { + if (rootElement == null) { + // Create a new root element + rootElement = new BinarySearchTreeNode<>( + elements.getByIndex(pivot), null, null); } else { - root.add(elms.getByIndex(piv + adj), comp); - root.add(elms.getByIndex(piv - adj), comp); + // Add the left and right elements in a balanced manner + rootElement.add( + elements.getByIndex(pivot + pivotAdjustment), + comparator); + + rootElement.add( + elements.getByIndex(pivot - pivotAdjustment), + comparator); } - adj++; + // Increase the distance from the pivot + pivotAdjustment++; } - if ((piv - adj) >= 0) { - root.add(elms.getByIndex(piv - adj), comp); - } else if ((piv + adj) < elms.getSize()) { - root.add(elms.getByIndex(piv + adj), comp); + // Add any trailing unbalanced elements + if ((pivot - pivotAdjustment) >= 0) { + rootElement.add(elements.getByIndex(pivot - pivotAdjustment), + comparator); + } else if ((pivot + pivotAdjustment) < elements.getSize()) { + rootElement.add(elements.getByIndex(pivot + pivotAdjustment), + comparator); } } + /** + * Check if an adjusted pivot falls with the bounds of a list + * + * @param elements + * The list to get bounds from + * @param pivot + * The pivot + * @param pivotAdjustment + * The distance from the pivot + * @return Whether the adjusted pivot is with the list + */ + private boolean adjustedPivotInBounds(FunctionalList elements, + int pivot, int pivotAdjustment) { + return (pivot - pivotAdjustment) >= 0 + && (pivot + pivotAdjustment) < elements.getSize(); + } + /** * 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 + * @param element + * The node to delete */ - public void deleteNode(T dat) { - nCount--; + public void deleteNode(T element) { + elementCount--; - root.delete(dat, comp); + rootElement.delete(element, comparator); } /** @@ -110,45 +145,49 @@ public class BinarySearchTree { * @return The root of the tree. */ public ITreePart getRoot() { - return root; + return rootElement; } /** * Check if a node is in the tree * - * @param dat + * @param element * 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); + public boolean isInTree(T element) { + return rootElement.contains(element, comparator); } /** * Traverse the tree in a specified way until the function fails * - * @param tlm + * @param linearizationMethod * The way to linearize the tree for traversal - * @param p + * @param traversalPredicate * The function to use until it fails */ - public void traverse(TreeLinearizationMethod tlm, Predicate p) { - root.forEach(tlm, p); + public void traverse(TreeLinearizationMethod linearizationMethod, + Predicate traversalPredicate) { + rootElement.forEach(linearizationMethod, traversalPredicate); } /** * Remove all soft-deleted nodes from the tree. */ public void trim() { - List nds = new ArrayList<>(nCount); + List nodes = new ArrayList<>(elementCount); - traverse(TreeLinearizationMethod.PREORDER, d -> { - nds.add(d); + // Add all non-soft deleted nodes to the tree in insertion order + traverse(TreeLinearizationMethod.PREORDER, node -> { + nodes.add(node); return true; }); - root = null; + // Clear the tree + rootElement = null; - nds.forEach(d -> addNode(d)); + // Add the nodes to the tree in the order they were inserted + nodes.forEach(node -> addNode(node)); } -} +} \ No newline at end of file -- cgit v1.2.3