Module org.dyn4j
Package org.dyn4j

Class BinarySearchTree<E extends java.lang.Comparable<E>>

  • Type Parameters:
    E - Comparable
    All Implemented Interfaces:
    java.lang.Iterable<E>

    public class BinarySearchTree<E extends java.lang.Comparable<E>>
    extends java.lang.Object
    implements java.lang.Iterable<E>
    Represents an (optionally balanced) Binary Search Tree.

    Null elements are not allowed and duplicates can have unexpected behavior. Changing the value of the elements after being inserted into the tree is undefined. It's also undefined behavior if the elements are not consistent with equals.

    Use the isSelfBalancing() and setSelfBalancing(boolean) methods to enable or disable self balancing. A balanced tree minimizes the tree depth and improves search performance. When self balancing is enabled, each insert or removal rebalances the tree as necessary.

    This class can be used in conjunction with the BinarySearchTreeSearchCriteria interface to perform arbitrary searches on the tree.

    Since:
    2.2.0
    Version:
    3.2.3
    Author:
    William Bittle
    • Field Detail

      • root

        BinarySearchTreeNode<E extends java.lang.Comparable<E>> root
        The root node of the tree; null when empty
      • size

        int size
        The current size of the tree
      • selfBalancing

        boolean selfBalancing
        Whether to keep the tree balanced or not
    • Constructor Detail

      • BinarySearchTree

        public BinarySearchTree()
        Creates a new binary search tree with automatic balancing off.
      • BinarySearchTree

        public BinarySearchTree​(boolean selfBalancing)
        Creates a new binary search tree.
        Parameters:
        selfBalancing - true if the tree should automatically balance
      • BinarySearchTree

        public BinarySearchTree​(BinarySearchTree<E> tree)
        Copy constructor.

        This performs a deep copy of the elements in the tree. The values contained in the tree are shallow copied.

        Parameters:
        tree - the tree to copy
        Since:
        3.0.0
      • BinarySearchTree

        public BinarySearchTree​(BinarySearchTree<E> tree,
                                boolean selfBalancing)
        Copy constructor.

        This performs a deep copy of the elements in the tree. The values contained in the tree are shallow copied.

        Parameters:
        tree - the tree to copy
        selfBalancing - true if the tree should self balance
        Since:
        3.0.0
    • Method Detail

      • isSelfBalancing

        public boolean isSelfBalancing()
        Returns true if this tree is self balancing.
        Returns:
        boolean
        Since:
        3.0.0
      • setSelfBalancing

        public void setSelfBalancing​(boolean flag)
        Sets whether this tree should self balance.

        When self balancing is enabled, adding and removing elements will perform a post step to make sure the tree stays balanced. Balancing minimizes the tree's depth, thereby increasing search performance.

        If enabled and the tree contains more than 2 elements, the tree will be balanced before this method returns.

        Parameters:
        flag - true if the tree should self balance
        Since:
        3.0.0
      • insert

        public boolean insert​(E comparable)
        Inserts the given comparable into this binary tree.

        Returns false if the given comparable is null.

        Parameters:
        comparable - the comparable object to insert
        Returns:
        boolean true if the insert was successful
      • remove

        public boolean remove​(E comparable)
        Removes the comparable object from the tree returning true if the comparable was found and removed

        If the given comparable is null, false is returned.

        Parameters:
        comparable - the comparable object
        Returns:
        boolean true if the element was found and removed
      • removeMinimum

        public E removeMinimum()
        Removes the minimum value node from this tree.

        Returns null if the tree is empty.

        Returns:
        E the minimum value
      • removeMaximum

        public E removeMaximum()
        Removes the maximum value node from this tree.

        Returns null if the tree is empty.

        Returns:
        E the maximum value
      • getMinimum

        public E getMinimum()
        Returns the minimum value of the tree.

        Returns null if the tree is empty.

        Returns:
        E the minimum value
      • getMaximum

        public E getMaximum()
        Returns the maximum value of the tree.

        Returns null if the tree is empty.

        Returns:
        E the maximum value
      • contains

        public boolean contains​(E comparable)
        Attempts to find the given comparable object within the tree.
        Parameters:
        comparable - the comparable object to find
        Returns:
        boolean true if the given comparable object was found
      • getRoot

        public E getRoot()
        Returns the root of the tree.
        Returns:
        E the root value; null if the tree is empty
      • clear

        public void clear()
        Empties this tree.
      • isEmpty

        public boolean isEmpty()
        Returns true if this tree is empty.
        Returns:
        boolean true if empty
      • getHeight

        public int getHeight()
        Returns the maximum depth of the tree.
        Returns:
        int the maximum depth
        Since:
        3.0.0
      • size

        public int size()
        Returns the number of elements in the tree.
        Returns:
        int
      • iterator

        public java.util.Iterator<E> iterator()
        Returns the in-order (ascending) iterator.
        Specified by:
        iterator in interface java.lang.Iterable<E extends java.lang.Comparable<E>>
        Returns:
        Iterator<E>
      • tailIterator

        public java.util.Iterator<E> tailIterator​(E from)
        Returns the in-order (ascending) iterator starting from the given node.
        Parameters:
        from - the starting value
        Returns:
        Iterator<E>
      • headIterator

        public java.util.Iterator<E> headIterator​(E to)
        Returns the in-order (ascending) iterator.
        Parameters:
        to - the ending value
        Returns:
        Iterator<E>
      • subsetIterator

        public java.util.Iterator<E> subsetIterator​(E from,
                                                    E to)
        Returns the in-order (ascending) iterator.
        Parameters:
        from - the starting value
        to - the ending value
        Returns:
        Iterator<E>
      • inOrderIterator

        public java.util.Iterator<E> inOrderIterator()
        Returns a new iterator for traversing the tree in order.
        Returns:
        Iterator<E>
      • reverseOrderIterator

        public java.util.Iterator<E> reverseOrderIterator()
        Returns a new iterator for traversing the tree in reverse order.
        Returns:
        Iterator<E>
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • getHeight

        int getHeight​(BinarySearchTreeNode<E> node)
        Returns the maximum depth of the subtree of the given node.
        Parameters:
        node - the root node of the subtree
        Returns:
        int the maximum depth
        Since:
        3.0.0
      • size

        int size​(BinarySearchTreeNode<E> node)
        Returns the number of elements in the subtree.
        Parameters:
        node - the root node of the subtree
        Returns:
        int
      • contains

        boolean contains​(BinarySearchTreeNode<E> node)
        Returns true if the given node (not the node's comparable) is contained in this tree.

        This method performs a reference equals comparison on the nodes rather than a comparison on the node's comparable.

        Parameters:
        node - the node to find
        Returns:
        boolean
      • get

        BinarySearchTreeNode<E> get​(E comparable)
        Returns the node that contains the given value or null if the value is not found.
        Parameters:
        comparable - the comparable value
        Returns:
        BinarySearchTreeNode the node containing the given value; null if its not found
      • insertSubtree

        boolean insertSubtree​(BinarySearchTreeNode<E> node)
        Inserts the given subtree into this binary tree.

        This method copies the elements from the given subtree.

        Parameters:
        node - the subtree root node
        Returns:
        boolean true if the insertion was successful
      • insertSubtree

        protected boolean insertSubtree​(BinarySearchTree<E> tree)
        Inserts the given subtree into this binary tree.

        This method copies the elements from the given tree.

        Parameters:
        tree - the subtree
        Returns:
        boolean true if the insertion was successful
      • removeSubtree

        protected boolean removeSubtree​(E comparable)
        Removes the node containing the given value and the corresponding subtree from this tree.
        Parameters:
        comparable - the comparable to search for
        Returns:
        boolean true if the element was found and its subtree was removed
      • removeSubtree

        boolean removeSubtree​(BinarySearchTreeNode<E> node)
        Removes the given node (not the node's comparable) and the corresponding subtree from this tree.
        Parameters:
        node - the node and subtree to remove
        Returns:
        boolean true if the node was found and removed successfully
      • insert

        boolean insert​(BinarySearchTreeNode<E> item)
        Inserts the given node into the tree.
        Parameters:
        item - the new node to insert
        Returns:
        boolean true if the insertion was successful
        Since:
        3.0.0
      • remove

        boolean remove​(BinarySearchTreeNode<E> node)
        Removes the given node from this tree and returns true if the node (not the node's comparable) existed and was removed.
        Parameters:
        node - the node to remove
        Returns:
        boolean
      • remove

        BinarySearchTreeNode<E> remove​(BinarySearchTreeNode<E> node,
                                       E comparable)
        Returns the node removed if the comparable is found, null otherwise.
        Parameters:
        node - the subtree node to start the search
        comparable - the comparable object to remove
        Returns:
        BinarySearchTreeNode null if the given comparable was not found
      • removeNode

        void removeNode​(BinarySearchTreeNode<E> node)
        Internal method to remove the given node from the tree retaining all the subtree nodes.

        This method assumes that the node is contained in this tree.

        Parameters:
        node - the node to remove
      • balanceTree

        protected void balanceTree()
        Re-balances the entire tree.
        Since:
        3.0.0
      • balanceTree

        void balanceTree​(BinarySearchTreeNode<E> node)
        Balances the tree iteratively to the root starting at the given node.
        Parameters:
        node - the node to begin balancing
        Since:
        3.0.0