Binary Search Trees in Clojure
This weekend I was able to spend some more time exploring Clojure. I decided that it would be interesting to reimplement some of the Binary Search Tree work I had previously done in PHP. We start by creating a simple record definition which describes the contents of a Node.
Using this Node record, we are able to now construct an insertion function which uses Clojure’s parameter deconstruction to great effect.
cond macro helps document an extremely succinct algorithm for inserting a new node into a provided tree.
Removing a given value from the tree requires a little more work than its’ insertion counterpart.
cond (again) allows us to clearly document these actions, handling the three different states the given values Node could be in.
Note that the third state requires the use of the followingly documented
Minimum and Maximum Value
As a Binary Search Tree’s invariant is for every Nodes left branch to be less, and right branch to be greater, we can implement simple functions which return the minimum and maximum values present in the tree.
Following a similar traversal pattern found in the insertion algorithm we are able to check if a given value is present in the tree using the following function.
Count and Height
Statistical analysis on the created tree can be carried out in the form of checking the height of the tree (depth), along with the total Node count.
Asserting the Invariant
We are able to assert that the given tree maintains the invariance required to be a BST by using the following function.
Creating and Displaying the Tree
Using the following function we are able to create a new tree from a supplied sequence - which uses a
reduce to insert each value into the tree, building up the final result along the way.
There are many ways to concatenate sequences within Clojure, however, I feel that the approach below clearly expresses the desired intent. Using a combination of ‘syntax-quote’ and ‘unquote-splicing’ we are able to build up a list of the supplied tree’s contents.
Finally, we are able to use all these functions in a contrived example, highlighting each of them in action.