Introduction
In 2010, I spent some time working on a Java Generics implementation of
a Binary Search Tree (BST). The developed version does not maintain optimal
tree balancing amid add() and remove() operations, however, I plan to
add red/black balancing later. (I'd also like to experiment with hashing the BST keys as an alternative to balancing the tree.) I may publish the source code for the graph layout engine I also coded some time in the future. Links to the core BST classes' source code are listed at the bottom of this page. (Here is the Wikipedia BST page.)
Graph Layout Algorithm
In order to validate the BST operations such as add() and remove(), I decided to develop a BST
graph layout algorithm to visualize the effects these
operations had on the graph. This particular layout algorithm is designed to support nodes of varying widths.
(Note: Even though there are algorithms published in the literature for this sort of layout algorithm, I developed this algorithm completely from scratch in order to give my brain some exercise.)
Essentially,
the layout algorithm positions node centroid
xcoordinates a minimum distance to the right of their predecessor
nodes. And,
for nodes at the same depth, it ensures they do not overlap while also
enforcing a minimum node spacing constraint. When there is a range of
xcoordinates a
node can legally occupy without violating spacing or ordering
constraints, the
layout algorithm places the node in the center of this range.
Below is an informal graphical diagram containing more details of the layout algorithm:
Algorithm Design Graph in Viewer
Out of curiosity, the madeup, handdrawn PowerPoint graph above used to design the graph layout algorithm was rendered with the resulting BST viewer implementation application described in the next section. The image below shows the above PowerPoint graph when viewed in the actual Java/Swing application:
Note that the nodes which could legally occupy a range of xcoordinates were indeed centered within their ranges. (This last step is not represented in the handdrawn PowerPoint slide.)
BstViewer Testing Application
A simple Java Swing/2D testing application was developed to exercise and validate the BST implementation and the graph layout algorithm. This tool has a simple popup context menu containing a few basic tests. Screenshots of this tool can be seen in the next section.
WMV Movie
A lowresolution video demonstration WMV movie of the BstViewer tool can be found here.
Screenshots
A few preliminary screenshots of random az graphs are shown below. Note that these images should be viewed at full resolution.

Here is a small, random graph/BST:
Here is a random BST with 500 nodes shown in "fit to screen" mode. As a result, the node text is not legible.
Here is a large, random BST with 50,000 nodes, also shown in "fit to screen" mode.
(The rendering code stops drawing node text (just draws filled rectangles) when the graphs get very large.)
Source Code
Here is the Java BST source code in its (asis) current state, including:
 A basic BtNode class
 A simple BST interface, Bst
 A class which implements the Bst interface: UnbalancedBst:
Note: The code, below, does not include the graph layout engine or the GUI code. Someday, I hope to complete this work and publish the final source code.
BtNode.java
Bst.java
UnbalancedBst.java

Copyright (c) Richard Creamer 2010  All Rights Reserved 