David M. Howard dmh2000@cwix.com
Sun Microsystems Certified Java Developer

Binary Search Tree with O(N) Balancing

This applet animates the building of a binary search tree. 20 values are inserted into the tree in increasing order, which is a pathological case for this data structure. The tree degenerates into a linear linked list.A rebalance of the tree is performed using a simple recursive rebalancing algorithm that is O(N) (Sedgewick,1998). The blue nodes highlight the nodes/subtree that changed on the most recent pass thru the tree.

Click "Start" to run the algorithm.

Click "Step" to step thru the algorithm.

Click "Reset" to clear and start over

David Howard October 1998

Home