Interface RedBlackTree<T>

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Interface Description
      static class  RedBlackTree.Color  
    • Method Detail

      • empty

        static <T> RedBlackTree<T> empty​(java.util.Comparator<? super T> comparator)
      • of

        static <T> RedBlackTree<T> of​(java.util.Comparator<? super T> comparator,
                                      T value)
      • of

        @SafeVarargs
        static <T> RedBlackTree<T> of​(java.util.Comparator<? super T> comparator,
                                      T... values)
      • ofAll

        static <T> RedBlackTree<T> ofAll​(java.util.Comparator<? super T> comparator,
                                         java.lang.Iterable<? extends T> values)
      • insert

        default RedBlackTree<T> insert​(T value)
        Inserts a new value into this tree.
        Parameters:
        value - A value.
        Returns:
        A new tree if this tree does not contain the given value, otherwise the same tree instance.
      • comparator

        java.util.Comparator<T> comparator()
        Returns the underlying Comparator of this RedBlackTree.
        Returns:
        The comparator.
      • contains

        boolean contains​(T value)
        Checks, if this RedBlackTree contains the given value.
        Parameters:
        value - A value.
        Returns:
        true, if this tree contains the value, false otherwise.
      • delete

        default RedBlackTree<T> delete​(T value)
        Deletes a value from this RedBlackTree.
        Parameters:
        value - A value
        Returns:
        A new RedBlackTree if the value is present, otherwise this.
      • emptyInstance

        RedBlackTree<T> emptyInstance()
        Returns the empty instance of this RedBlackTree.
        Returns:
        An empty ReadBlackTree
      • find

        Option<T> find​(T value)
        Finds the value stored in this tree, if exists, by applying the underlying comparator to the tree elements and the given element.

        Especially the value returned may differ from the given value, even if the underlying comparator states that both are equal.

        Parameters:
        value - A value
        Returns:
        Some value, if this tree contains a value equal to the given value according to the underlying comparator. Otherwise None.
      • isEmpty

        boolean isEmpty()
        Checks if this RedBlackTree is empty, i.e. an instance of Leaf.
        Returns:
        true, if it is empty, false otherwise.
      • left

        RedBlackTree<T> left()
        Returns the left child if this is a non-empty node, otherwise throws.
        Returns:
        The left child.
        Throws:
        java.lang.UnsupportedOperationException - if this RedBlackTree is empty
      • max

        default Option<T> max()
        Returns the maximum element of this tree according to the underlying comparator.
        Returns:
        Some element, if this is not empty, otherwise None
      • min

        default Option<T> min()
        Returns the minimum element of this tree according to the underlying comparator.
        Returns:
        Some element, if this is not empty, otherwise None
      • right

        RedBlackTree<T> right()
        Returns the right child if this is a non-empty node, otherwise throws.
        Returns:
        The right child.
        Throws:
        java.lang.UnsupportedOperationException - if this RedBlackTree is empty
      • size

        int size()
        Returns the size of this tree.
        Returns:
        the number of nodes of this tree and 0 if this is the empty tree
      • union

        default RedBlackTree<T> union​(RedBlackTree<T> tree)
        Adds all of the elements of the given tree to this tree, if not already present.
        Parameters:
        tree - The RedBlackTree to form the union with.
        Returns:
        A new RedBlackTree that contains all distinct elements of this and the given tree.
      • value

        T value()
        Returns the value of the current tree node or throws if this is empty.
        Returns:
        The value.
        Throws:
        java.util.NoSuchElementException - if this is the empty node.
      • iterator

        default Iterator<T> iterator()
        Returns an Iterator that iterates elements in the order induced by the underlying Comparator.

        Internally an in-order traversal of the RedBlackTree is performed.

        Example:

        
               4
              / \
             2   6
            / \ / \
           1  3 5  7
         
        Iteration order: 1, 2, 3, 4, 5, 6, 7

        See also Implement Iterator for BinaryTree I (In-order).

        Specified by:
        iterator in interface java.lang.Iterable<T>
      • toString

        java.lang.String toString()
        Returns a Lisp like representation of this tree.
        Overrides:
        toString in class java.lang.Object
        Returns:
        This Tree as Lisp like String.