Interface RedBlackTree<T>

Type Parameters:
T - Component type
All Superinterfaces:
Iterable<T>
All Known Implementing Classes:
RedBlackTreeModule.Empty, RedBlackTreeModule.Node

interface RedBlackTree<T> extends Iterable<T>
Purely functional Red/Black Tree, inspired by Kazu Yamamoto's Haskell implementation.

Based on

  • Method Details

    • empty

      static <T> RedBlackTree<T> empty(Comparator<? super T> comparator)
    • of

      static <T> RedBlackTree<T> of(Comparator<? super T> comparator, T value)
    • of

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

      static <T> RedBlackTree<T> ofAll(Comparator<? super T> comparator, 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.
    • color

      Return the RedBlackTree.Color of this Red/Black Tree node.

      An empty node is BLACK by definition.

      Returns:
      Either RED or BLACK.
    • comparator

      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.
    • difference

      default RedBlackTree<T> difference(RedBlackTree<T> tree)
    • 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.
    • intersection

      default RedBlackTree<T> intersection(RedBlackTree<T> tree)
    • 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:
      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:
      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:
      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 Iterable<T>
    • toString

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