Immutable Binary Trees (Part 2)

On Monday, I introduced a basic implementation of immutable binary trees in Java. At the end of that post, I wrote:

There are several problems with this implementation that I plan to address in a future post:

• The remove method creates a new node at each level, even if the element to remove does not exist.


• The use of null to indicate the lack of a left or right child opens us up to the potential of NullPointerExceptions and wastes space from those fields. (In particular, in a balanced binary tree, half the elements will be leaf nodes.)


• Currently, there is no way to create an empty tree, since every node has a value. If you look at the ImmutableTreeRunner implementation above, I had to generate my first random value before I could create the ImmutableBinaryTree.

This is that future post. I'll present a much cleaner, more memory-efficient implementation that solves these problems. That said, this is still not a good binary tree implementation to use. I'm not implementing any balancing, so it's generally going to be quite slow. It's just a more elegant unusable solution.

The first problem was largely laziness on my part, I suppose. (It would have been possible to better handle remove in the old implementation.) The other two problems can be addressed by accepting that not all immutable binary trees should be created equal, and establishing a class hierarchy:



That may look overly complicated, but all of the logic will actually degenerate into handling empty trees and handling non-empty trees. The NonEmptyTree subclasses only add fields and provide one-line implementations for NonEmptyTree's abstract methods.

Note that I gave the EmptyTree rounded edges in the diagram to distinguish it -- this will be implemented as a singleton. Conceptually, there is only one empty immutable tree). Also, this makes for some simpler code, as we can use == to see if a child is the empty tree.

First, let's look at the implementation of the ImmutableBinaryTree abstract base class:



We specialize the declared return type of add and remove, while still satisfying the ImmutableSet interface I put up on Monday. We declare an internal addAll helper method (though this could also be added to the ImmutableSet interface). Finally, we create two factory methods for immutable binary trees -- one that returns the empty tree and another that constructs a series of trees until all the given elements have been added.

Next we implement all of the abstract methods for the empty tree. These are all one-liners:



We also store the (untyped) singleton EmptyTree instance and provide a (typed) static accessor for it. In this case, working without the T type is perfectly legitimate -- there is no state influenced by T in instances of this class. That said, the Java compiler apparently can't tell that this is safe (which is fair, since usually it's not safe). So, I've used the @SuppressWarnings annotations to reassure the compiler that I know what I'm doing. (Note that a similar approach is used at least in the Apache Harmony implementation of Collections.emptyList(), which is solving almost exactly the same problem.)

Before thinking about the behaviour of non-empty trees, I think it makes sense to think about their state. Firstly, all non-empty trees represent a node with a value. So, NonEmptyTree will have a field of type T for that value. Additionally, non-empty trees have 0, 1, or 2 children. If they have 1 child, it is either a left or right child. This motivates the NonEmptyTree hierarchy presented above. By isolating the state (that is, the fields) into subclasses, we ensure that memory is not wasted on fields that are unused (that is, are permanently null). It also makes it easier to reason about the state being used in each subclass.

Fortunately, by ensuring that all of the subclasses provide a consistent exposure of state, that is, they supply a left and right child on demand (where they may be the singleton EmptyTree), we can safely implement all of the logic in NonEmptyTree:



Why did I declare emptyTree local variables to capture the empty tree instance before checking equality against passed parameters? It turns out that the Java type inferenceer (or at least the one used in my local version of Eclipse on a Mac) wouldn't allow me to check e.g. tree == EmptyTree.instance(). It's possible that I messed up with the covariance of the type parameter. Regardless, adding the local variable was an easy of making my intentions clear to the type inferencer.

The general flow is as follows:

• add is a special case of addAll, unless the current node already holds the value being added.


• remove either removes the current node (at which point, we merge the left and right children), or replaces the relevant child with the result of the remove operation applied to it.


• addAll either merges the newly added tree's children with this node's children (if they have the same root value), or replaces the relevant child after applying the addAll operation to it.


• replaceChildren runs through the five relevant cases for replacing the children of a given node:
  
  
  
  • If both children are equal to the current value, then nothing has changed. Return this.
  
  
  • If both new children are the EmptyTree singleton (and weren't before, or they would have been caught by the previous check), then we return a new Leaf.
  
  
  • If one new child is the EmptyTree, we return a new LeftBranch or RightBranch.
  
  
  • Otherwise, both children are non-empty so we return a new DualBranch, which is guaranteed to be different from the current node (by the first check).
  
  
  
  


• The toList and contains methods are fairly self-explanatory.
  

Finally, we have all of the specializations of NonEmptyTree, which are a series of constructors and one-line method implementations:











There are a couple of points that I found interesting working on this code:

• There is not a single null check in this code. Instead, that role has been absorbed by EmptyTree, which I like to think of as a sort of "type-safe" null. Instead of checking for null and deciding how to react in every situation, I've defined a "null-like" element, and specified how it should implement my interface in a consistent way. I did still check for EmptyTree in replaceChildren, to ensure that the most efficient concrete NonEmptyTree is returned. I could have just returned a new DualBranch, and the correctness of the algorithms would still hold.


• A Java object, as I understand it, occupies enough memory to hold a reference to its runtime class, and the space occupied by its fields. Since EmptyTree is a singleton, its memory consumption doesn't really matter, but should effectively be this single reference to its class. Leaf is a concrete class with a reference to its class and a reference to the contained value of the node. On the other extreme, DualBranch represents four references to: the class, the value, a left child, and a right child. Thanks to the immutable nature of this code, we are required to return new objects, which don't necessarily need to be of the same type as our current (runtime) class. We can make those objects as efficient as possible. If I had implemented a proper balancing strategy, half the nodes would be Leafs, and would occupy roughly half the memory of corresponding DualBranches (disregarding the space occupied by the values themselves, aside from their references).

While there's nothing new or clever in these posts, I've found them to be a good learning exercise, and have helped me reinforce some functional programming ideas. In particular, while the whole "type-safe null" idea expresseed by EmtpyTree is pretty standard fare in Haskell, it's still pretty novel to me as a (mostly) Java developer. Also, the particular refactoring in this post was motivated by the elegant simplicity of Scala's immutable List, which I feel that I now understand more clearly.

Of course, I did need to add those two @SuppressWarnings annotations in EmptyTree, which I believe Scala avoids by having Nil (the singleton empty list) have a type parameter of Nothing (which inherits from everything -- if this sounds weird but intriguing, read up on some Scala, it actually all makes sense). I don't believe it's possible to do the same in Java, so I'm happy to at least be consistent with Apache Harmony.

Immutable Binary Trees

I have been reading a fair bit about functional programming recently, and the advantages you can get in a concurrent execution environment by using immutable data types (or persistent data structures).

While it's not too hard to wrap your head around an immutable list structure with an efficient prepend operation, I wanted to try implementing a slightly more complicated immutable structure (but not as complicated as a trie). So, I decided to try implementing an immutable binary tree in Java, and then work on improving it a bit.

Note that this is not a "good" implementation. In particular, I'm not going to bother rebalancing the tree, so it's very possible for many operations to be O(n) instead of the O(log n) that a balanced tree would provide.

The main idea that I had trouble fully grasping when learning about immutable data structures is the idea that you usually don't need to copy everything when adding/removing an element. So, let's look at an example of a binary tree in pictures and consider what elements need to be replaced and what can be reused when we add a new element to the tree.

Consider the following tree:



The rules are simple: at each node, values less than the current node's value are stored in the left subtree, while values greater are stored in the right subtree.

Now, suppose we want to add the number 11 to the tree. It should be added as a right child of the 10 node. Since the current 10 node has no children (and is itself an immutable tree), we must allocate a new 10 node with 11 as a right child. The new 10 node will be the left child of a new 13 node, which can reuse the old 16 node as its right child (along with the children of 16). Finally, a new 8 node must be allocated with its right child pointing to the new 13 node and its left child pointing to the existing 4 node.

Here is a picture with the newly-allocated nodes highlighted in red:



In total, four new nodes were allocated: one for each level in the tree. For a balanced tree, this generalizes to O(log n) node allocations, or the same runtime efficiency of a mutable binary tree. The remainder of the tree continues to point to the old values. Assuming we aren't holding onto a reference to the old tree root, the original 8, 13, and 10 nodes would now be eligible for garbage collection. (Though if another thread were accessing the old version of the tree, it would not be affected by this change, avoiding a potential race condition.)

Now, let's take a look at how to implement a simple immutable binary tree in Java.

To start with, I'll create a simple ImmutableSet interface (which doesn't follow the java.util.Set interface, since that is fundamentally based on mutability -- e.g. the "normal" add method has a void return type):



I've included a toList method for testing purposes, since it was easier than implementing the Iterable interface.

The fields and constructor of the ImmutableBinaryTree implementation are as follows:


All fields must be final in an immutable data structure.

Here is the implementation of the add method:


We create a leaf node for the new element and add it as a subtree to the existing tree. The addSubtree method is reused in the implementation of remove below, and could be used to implement a public addAll method that allows merging of two ImmutableBinaryTrees.



The remove method has two base cases (when we don't recurse into child branches). If the element is not in the tree, we return the unmodified this. If the current element is to be removed, we merge the left and right subtrees, arbitrarily choosing to add the right subtree as a descendent of the left (assuming the left subtree is not null, or else we simply return the right subtree).

The contains method is effectively the same as it would be in a mutable binary tree:


The toList method does an in-order traversal of the tree to return an ordered list:


For debugging purposes, and to visualize the tree depth, I decided to override toString:


Finally, here is a runner I used to compare the correctness of my implementation for addition/removal against the standard mutable TreeSet from the Java standard library:


There are several problems with this implementation that I plan to address in a future post:

• The remove method creates a new node at each level, even if the element to remove does not exist.


• The use of null to indicate the lack of a left or right child opens us up to the potential of NullPointerExceptions and wastes space from those fields. (In particular, in a balanced binary tree, half the elements will be leaf nodes.)
  
• Currently, there is no way to create an empty tree, since every node has a value. If you look at the ImmutableTreeRunner implementation above, I had to generate my first random value before I could create the ImmutableBinaryTree.