Re-organize collection.Tree

[danieldietrich]

The current Tree type hierarchy is a little bit bulky.

As discussed recently, interfaces and implementations go hand-in-hand. Let me describe here, how we take the collection interfaces to the next level:

            Traversable
                 |
               Tree
              /    \
     BinaryTree    ...
           /  \
RedBlackTree  ...

All trees in Javaslang are designed to have a value at each node. Also the empty tree exists for all tree interfaces.

Tree<T> := Nil | Branch(T value, Seq<Tree> children)

BinaryTree<T> := Nil | Branch(BinaryTree<T> left, T value, BinaryTree<T> right)

// enum Color { RED, BLACK } handled internally
RedBlackTree<T> := Nil | Branch(RedBlackTree<T> left, T value, RedBlackTree<T> right)

Tree (formerly: RoseTree) is the most general tree data structure. It has

• a root
• (inner) nodes
• leaves
• an arbitrary amount of children

BinaryTree is an unbalanced binary search tree. Each node has at most two children: left and right. They are the simplest form of binary search trees. They perform poorly on ordered data and might take up to O(n) time.

RedBlackTree is a very efficient balanced binary search tree, maybe the fastest solution (with some tweaks) which exists so far. A color is internally used to keep the tree aproximately balanced. Then no operation takes more than O(log n) time.

[danieldietrich]

One more word on the interface design mentioned above (here slightly simplified):

interface Tree<T> extends Traversable<T> {
    boolean isEmpty();
    boolean isBranch();
    boolean isLeaf();
    Seq<Tree<T>> getChildren();
    // ...
    static <T> Nil<T> nil() { ... }
    static <T> Branch<T> of(T value, Seq<Branch<T>> children) { ... }
    // ...
    class Nil<T> extends Tree<T> { ... }
    class Branch<T> extends Tree<T> { ... }
}

interface BinaryTree<T> extends Tree<T> {
    BinaryTree left();
    BinaryTree right();
    @Override Seq<BinaryTree<T>> getChildren();
    // ...
    static <T> Nil<T> nil() { ... }
    static <T> Branch<T> of(BinaryTree left, T value, BinaryTree right) { ... }
    // ...
    class Nil<T> extends BinaryTree<T> { ... }
    class Branch<T> extends BinaryTree<T> { ... }
}

interface RedBlackTree<T> extends BinaryTree<T> {
    Color getColor();
    @Override RedBlackTree left();
    @Override RedBlackTree right();
    @Override Seq<RedBlackTree<T>> getChildren();
    // ...
    static <T> Nil<T> nil() { ... }
    static <T> Branch<T> of(RedBlackTree left, T value, RedBlackTree right) { ... }
    // ...
    class Nil<T> extends RedBlackTree<T> { ... }
    class Branch<T> extends RedBlackTree<T> { ... }
    enum Color { RED, BLACK }
}

Please note, that currently no back-reference to root nodes is modeled.

Please note also, that children are of type Seq, this implies that it is possible to model trees of infinite size (by using Stream instead of List).

[danieldietrich]

More on implementing Traversable here: #113

[danieldietrich]

See also #220 (comment)