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.)
the layout algorithm positions node centroid
x-coordinates a minimum distance to the right of their predecessor
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
node can legally occupy without violating spacing or ordering
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 made-up, hand-drawn 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 x-coordinates were indeed centered within their ranges. (This last step is not represented in the hand-drawn 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.
A low-resolution video demonstration WMV movie of the BstViewer tool can be found here.
A few preliminary screenshots of random a-z 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.)
Here is the Java BST source code in its (as-is) current state, including:
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.
- A basic BtNode class
- A simple BST interface, Bst
- A class which implements the Bst interface: UnbalancedBst:
Copyright (c) Richard Creamer 2010 - All Rights Reserved