Home‎ > ‎Java‎ > ‎

Binary Search Tree + Compact Graph Layout Algorithm

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 x-coordinates 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 x-coordinates 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 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.

WMV Movie

A low-resolution video demonstration WMV movie of the BstViewer tool can be found here.

Screenshots

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.)


Source Code

Here is the Java BST source code in its (as-is) 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