Introduction
This is just a quick coding project I did for fun.
One unique thing about this project is that, in addition to creating an unbalanced BST implementation, I also created a compact graph layout and visualization engine.
(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.
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 