Project 4

Last modified: April 21 2008 09:52:29 AM

Introduction

In this project, you will be implementing and designing some of your own data structures.

---

Project Description

For this project, you will be implementing and testing two different data structures. Part of your grade will be determined by how well you test your implementations. That means, you will be required to submit a testing program along with your implementation.

Structure 1: AVL/Splay Tree

You will create a structure that combines the AVL tree's balance, with the splay tree's ability to bring recently searched for elements to the root of the tree. You will need to design the rotations in such a way to maintain balance and move the elements up to the root of the tree. You should maintain the AVL height invariant while still implementing the splay. You should design the rotation to the best of your abilities. While efficiency is important, you should be most concerned with correct functionality first and then efficiency.

Your tree should support the following operations:

• Insert an element into the tree
• Search to see if a particular element is in the tree
• A findMin function that will return the smallest element in the tree
• A findMax function that will return the largest element in the tree
• A function to return whether or not the tree is empty
• A function to remove all elements from a tree
• A function to print the tree in sorted order (no indication of tree structure)
• A function to print the tree so that it illuminates the trees structure. Typically structure is indicated through the use of parantheses. When the tree is printed using this function, you should indicate to the user how to interpret the print out. For example, if I printed A (B C) - I would say that B and C are the children of A, or I could use a notation where you print out ((B) A (C)) B and C are still the children of A. You choose the print out style, but you need to explain it.
• BONUS: Implement remove from the tree.

 

Structure 2: Graph

You will create a graph structure that is built based on an adjacency relation model. This means that if is an edge from u to v in the graph, then the ordered pair (u, v) is in the relation. A relation is a set, so there should be no duplicates.

However, to make your graph useful, you will need to support the following elements:

• loops in the graph (a node that has an arc that starts and ends with itself)
• both directed and undirected graphs
• both weighted and unweighted edges
• multiple arcs (with possibly different weights) from one node to another (called parallel arcs)
• nodes that do not connect to another node in the graph (called isolated nodes)

The graph should be able to perform the following functionality:

• Insert a node into the graph
• Remove a node from the graph
• Insert an edge between two nodes
• Remove an edge from between two nodes
• Tell whether two nodes are adjacent to each other and if applicable, give the weight of the edge
• Give the path between two nodes and give the length of the path
• Give a print of all the nodes in the graph (both connected and isolated)

Therefore, you will need to define ways to store this information, preferably inside the relation itself, but perhaps outside storage of this information would be neccessary. However, you should not store duplicate information. There should not be an adjacency matrix stored along side your adjacency relation for example.

Testing

Your testing program should demonstrate the required functionality of these two structures and run like a script (even if it takes user input). You should be explaining to the user what is going on at each step and how the testing is progressing. You should test for usual as well as unusual cases for each of the pieces of functionality described. Part of your grade will be based on how well you test your structures and their functionality. Both structures should be capable of handling larger data sets and should be able to store ANY type of data that the user wants.

Paper

The paper for this project will be smaller than the others. It should be more of a technical report in which you describe your design of the two structures and some implementation details. See grading guideline for more detailed description.

---