Project BST - algorithms-in-action/algorithms-in-action.github.io GitHub Wiki

Project 2: Binary search tree variants - more details/updates

Currently AIA has an animation of an iterative coding of binary search trees and a recursive coding of AVL trees (a form of self-balancing binary search tree). We would like to extend the coverage of BSTs in AIA.

Improving the AVL tree animation

The current AVL tree animation is good (it was devloped by a student team in 2024 and has been refined somewhat since) but could be improved further. Specifically, we think the way certain components of the tree are highlighted is worth revisiting and the way the animation helps users understand the recursion could be improved. It is likely some prototyping will be required in order to get the best outcomes.

The current system highlights edges and nodes at various points (partly to show where the "current node" is in the recursive execution) and draws boxes around subtrees when a rotation is performed. One possibility is to rely on highlighting edges and nodes for rotations and use boxes to visualise the recursion. Nested boxes could show how recursion is used to process subtrees.

Recursive BST animation

We would like a new animation BSTs that uses a recursive coding. The relationship with AVL trees should be emphasised - the AVL tree insertion algorithm is essentially recursive BST insertion code with a couple of steps added at the end. The look of the two animations (including the pseudocode) should be as similar as possible. Also, a good visualisation of recursion for a simple algorithm (preferably very similar to the AVL version) would be beneficial.

Iterative BST animation

The current iterative BST animation may also require some minor modifications to make it look as similar as possible to the other BST/AVL algorithms.