Binary Search Tree

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 un-balanced 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 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.

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