Skip to end of metadata
Go to start of metadata

Overview

For this assignment, I created simulations for the Heap and AVL Tree data structures.

Heap

First I simulated a max-heap, a complete binary tree in which every node is greater than its children. The first thing I did was create a working heap class to which I could add and remove elements in a main method. Then I performed serious modifications to transform it into an agent that would move slowly so that a user could see what it does. Before I get into that, though, I should explain how HeapSim and LandscapeDisplay function. I used the same LandscapeDisplay from Lab 8, but I replaced the step and run buttons with "add value," "add random," and "remove." I also made SimPanel implement MouseListener, listening for mouse clicks on specific nodes. The buttons cause LandscapeDisplay to call methods in HeapSim to add or remove a value. Clicking on SimPanel causes a JOptionPane to pop up, asking for the new value. SimPanel takes the provided value and the coordinates of the click and sends them over to HeapSim's alterNodeAt method. HeapSim has a private variable for its Heap, so it sends the request along to it (though in the case of alterNodeAt it first finds the nearest node to the mouse click and sends a reference to a node to Heap instead of coordinates). Apart from methods to deal with user requests, HeapSim has an initialize method that creates a new Heap and adds a single random value to it.

To add to a heap, you make a new node at the next position and then let it float up to a position that will maintain the ordering constraints of a heap. Normally, the "floating up" part can be done with a while loop or recursion. For the simulation, though, I wanted the display to update between each swap as the node floats up. I learned in the last lab that trying to call update() from the class is unlikely to work since, due to the way threads work, the request to update would probably not be executed until the add was completed, by which time it would be too late. My solution was to use the primaryUpdate method (called regularly as the simulation iterates) to do one swap per turn. The diagram below shows the steps taken when a user clicks "add value." The first four steps show how the click gets to Heap. The final step is the most interesting. It is basically a recursive method that is drawn out over several iterations, with the base case causing the recursion to cease by setting floatingUp to false.
Remove is done in much the same way: heap.remove() returns the largest value and moves the last leaf into the top position, then sets sinking to true and reheapIdx to 1. primaryUpdate calls sinkDown() if sinking is true; sinkDown is analagous to floatUp.

Setting a value is just a little more complecated. HeapSim finds the nearest node to the click using getNeighbors, with a vision of 3. If no node is that close, an error message is conveyed through a JOptionPane, and the method returns. Otherwise, it compares distances and sends the closest node to heap.set(node, value). Knowing the node is useful, but the index of the node is more important. I find the index by, starting with the top node, comparing the x-coordinate of the given node to the 'current' node, moving to the left child if the nodeToChange has a lower x value, and moving to the right child if it is greater. Once the index is found the parent and children can be immediately accessed for comparison. If the new value is bigger than the old value, then the node may need to floatUp, and appropriate steps are taken to make that happen. If it is less than the old value, the program prepares to sinkDown the node. One thing I noticed, however, was that the simulation would iterate before it updated again, so that, if the node needs to move, the user never sees the new value at the original position. To fix this, I added a boolean waiting. If waiting is true when primaryUpdate is called, it is set to false, but nothing else happens that iteration.

A few notes: normally when you swap in a heap, it is better to swap the values in the nodes rather than the nodes themselves. In my implementation, however, I have the nodes themselves moving. There is really no advantage to this, except that it would be easier to watch if the nodes slid to their new positions rather than instantly swapping, and if I were to make them slide, then the nodes would actually want to swap. Also, the nodes change color when they are being compared. The node that is the reason for the comparison is colored teal (the node just added or changed), and the node(s) it is comparing itself to is/are colored orange. The gif below shows a heap to which I added 23 nodes, then removed 8, and finally made about 4 changes to various nodes. Since my method of creating the gif only saves the graphic, I added labels to let you see which nodes I clicked on to change their values. Sorry about the speed, but the entire thing would start taking quite a long time if I slowed it down very much.











 
 
 
 
 

AVL Tree

An AVL Tree is a balanced binary search tree. In order to generalize LandscapeDisplay to use AVLSim, I created an interface called DataStructure that both HeapSim and AVLSim implement. This interface requires implementing classes to have the methods that LandscapeDisplay calls when buttons are clicked or a node is selected, so LandscapeDisplay can simply cast its reference to sim to be a DataStructure (it relys on the fact that the list of possible simulations are all DataStructures).  Like HeapSim, AVLSim simply calls tree.add(int value) and tree.remove(int value) when its corrosponding methods are called. To alter a node, however, it calls remove for the selected node and adds the new value. This is effectively the same as changing the value of a node, and is the easiest way to get the node to its correct position.

Adding and removing nodes from an AVL tree starts just as they would from a normal binary search tree -- the method searches for the correct location to add the node, or finds the node to remove and replaces it with the rightmost child in the left tree. The addition or removal could have disrupted the balance, though, so then a rebalancing method must be called, starting with the lowest node that might feel the unbalance and moving upward from it. An unbalance in an AVL tree is defined by the two subtrees of a node having heights that differ by more than one. Checking for unbalance is a step-by-step process, so I made a rebalance(LinkedNode n)  like I made floatUp in Heap; that is, I have a queue of nodesToRebalance, and if it is not empty when the simulation iterates, rebalance is called with the first node, and at the end of rebalance another node is added to the queue, if necessary (actually, there should never be more than one node in the queue, but if a user clicks on "add random" before a previous addition is finished, it is useful to let the first keep rebalancing, though it still could be messed up). rebalance only checks for unbalance -- when it finds unbalance, it adds Rotations to a queue called rotationsToExecute. A Rotation is an inner class that has a pointer to a node and an enum value LEFT or RIGHT. primaryUpdate first checks rotationsToExecute, and tells the Rotation to execute() if it is not empty. The steps taken after an addition are listed below. Removing node causes the same chain of event, but in the first step, the node that was moved is the one offered to nodesToRebalance, rather than the parent of the removed node (though there are some special cases where a different node is offered if the node that moved is null).
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Watching this simulation rotate is sort of interesting, but only if you can ponder what will happen ahead of time, which, unfortunately, you could not if I made a gif of additions and deletions. Instead, you just get to see the resulting AVL tree after 100 successful additions, and then after 99 deletions. The numbers were added and removed in a random order.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
It is interesting to note that fewer rotations are performed in removing than in adding. Also, the average number of rotations was higher when I had added only a few elements, but as it got larger, fewer additions caused the tree to become unbalanced.
 

Conclusion

Building the classes and figuring out how to show what was happening gave me a good understanding of heaps and AVL trees. I suppose I should have made red-black and kd trees as well, but I tried to be sociable over Thanksgiving, so that simply didn't happen. Maybe I'll do it later anyway, it would be an excelent form of review for the exam to build simulations for all of the data structures we studied, but that would probably take much longer than a more typical review, which probably will be satisfactory.
 

Labels