Sunday, October 16, 2011
Red Black Tree is a balanced BST tree. Details are described on Wikipedia.
You can run this sample app directly on appspot (it works on iPhone too :-) )
Sample code can be found here: Browse on GitHub.
Let's start from initialization.
First, we need to create Canvas element and add it to HTML. getContext2D is called to obtain drawing context.
We register a timer to redraw frames frequently:
So doUpdate is called every 50 ms and whenever redrawFrame is set to true, it redraws Canvas contents.
In autoplay mode, we call processFrame in while loop. So whenever redraw procedure takes too long, we will process frames without redrawing them. This won't slow down animation on low resources.
Then, we need to draw a tree. We use drawTree procedure, which is recursive and draws nodes along with contents and connections between them:
The best part is that we can do regular Java unit tests on Red Black tree to verify correctness of implementation: