Outcomes

By the end of this workshop, you should:
- Be comfortable using binary search trees to store numerical data
- Understand the benefits of balanced AVL trees

Aim

This workshop's app is a visualization of a binary search tree that contains the values 1 through 20. The order in which the values are inserted will be randomized causing the tree to take on a shape unique to that input sequence. The user is then challenged to guess the location of any given node within the tree.

The UI will start off looking like this:

It will prompt the user to click on each node in a random order. The nodes that the user identifies correctly will be displayed in green. The nodes that the user clicks on incorrectly will be displayed in red and the node they should have clicked on will be displayed in cyan.

Timing

In total, this workshop activity should take you around 2-3 hours to complete. Each milestone will take around 1 hour to completed, are therefore a good way to divide up the workshop into smaller sessions.

Tour of the code

Starter Code

We've provided a starter project for you with some skeleton code as a starting point.

It is made up of the following files (methods in bold are the ones you need to implement):

• MainActivity:
  • onCreate: Instantiates the BinaryTreeView object and inserts it into the UI.
  • onPressStart: Handler for the Start button.
• BinaryTreeView:
  • initialize: Inserts the nodes into the tree and generates the order in which the user will have to guess the nodes.
  • generateRandomSequence: Helper for the above. Generates a randomly ordered list of the numbers 1 through 20.
  • onDraw: Passes the draw call to the BinarySearchTree object.
  • updateMessage: Updates the text field at the top of the UI with the desired node.
  • onTouchEvent: Handler for user touch. Finds the node that was tapped by the user and reveals the correct node if the user chose the wrong node.
• BinarySearchTree:Wrapper class for the tree. Most of the actual work is handled by the TreeNode class below so a lot of these are wrappers that call the recursive method on TreeNode.
  • insert: Inserts a value into the tree. Special handler for empty tree case and passes the rest of the work to TreeNode.
  • positionNode: Wrapper that causes the nodes to position themselves on the screen.
  • draw: Wrapper.
  • click: Wrapper.
  • search: Helper that finds the node with a given value in the tree.
  • invalidateNode: Finds the node of the specified value and mark it as invalid in the UI.
• TreeNode
  • insert: Adds the given value to the tree.
  • getValue: Trivial getter.
  • positionSelf: Causes a node to compute its position on the canvas given its parent's position.
  • draw: Draws the node and the line to its children.
  • click: Click handler.
  • invalidate: Causes the node to reveal its value and draw itself in cyan.

Milestone 1: Inserting into a binary search tree

Your first task, and the first milestone, is to add values to the tree. Note that the empty tree case is handled in BinarySearchTree.insert. Implement TreeNode.insert to find the parent of the new node and add a new TreeNode as the appropriate child of its parent.

Smaller nodes

Remember that values smaller than a node must be stored in its left descendants and values greater than a node must be stored in its right descendants.

Since draw was implemented for you, you should be able to view the tree once you implement insert. You can (temporarily) change the logic in draw to always show the value of a node to verify that you are correctly inserting the values into the tree.

Milestone 2: Search

In the second milestone, you need to implement the code that supports the user trying to guess the location of a particular node. The handler for click which turns a node red or green is given to you. However, the code to reveal the correct node when a user clicks the wrong node is missing. In particular, you will need to implement BinarySearchTree.search to find the node that they were supposed to click.

Stop and Check

Try playing the game and see how good you are at finding a node's position. This is also a good time to try to spot any bugs in your code.

At this point you might notice that when you select the wrong node, although you reveal the correct node, its number remains in the searchSequence and you are asked to click on it later on. Avoid this by removing the mis-clicked number from the searchSequence (in BinaryTreeView.onTouchEvent). Once you have done this you have completed Milestone 2.

Milestone 3: AVL tree

The third and final milestone involves turning your binary tree into an AVL tree. This will make your tree smarter and avoids it getting imbalanced.

The first step of this is to keep track of the height of each node. Height is already a field of the TreeNode class and you need to set it in the TreeNode.insert method. The draw is already coded to show the height of a node when it is not zero so you can verify that you are correctly assigning height to each node (except the leaves whose height is, by definition, zero).

Having this precomputed height value, makes it easy for you to check the balance factor of a given node.

Balance Factor

Look back at the Wikipedia article in the preparation module if you don't remember what the balance factor is.

Once you have the heights calculated, you can re-balance the tree. This requires refactoring your insert code to do the following:

1. insert the new node (call it a) as you did before, then
2. find the first unbalanced ancestor of a (call it d)
3. find the child of d that's on the path to a (call it c)
4. find the grandchild of d that's on that path to a (call it b)
5. depending on the configuration of a, b, c, and d, perform one of the four possible rotations to re-balance the tree
6. update the node height for the affected nodes

Watch how your algorithm keeps the tree from falling out of balance.

Extensions

As usual, this activity contains opportunities for extending your work. If time permits, we would like everyone to attempt at least one extension, either from what is specified below or one that you have invented yourself:

• Before implementing the AVL tree, the visualization of the tree can get cluttered for highly imbalanced trees. This can lead to node collision like in the following screenshot:

Refactor positionSelf to better handle such cases. You may need to disable the rebalancing behavior to test this.

• Add another button to the UI that causes a single node to be added to the tree. Use this to visualize the rebalancing of the tree.

Consider

What might be another type of data which could be used in a balanced AVL tree? Can you implement the code for the tree to balance for this data?

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.