Chat with us, powered by LiveChat Top-Down Splay Trees Using Inheritance | All Paper
+1(978)310-4246 credencewriters@gmail.com
  

Assignment 5 – Top-Down Splay Trees Using InheritanceMake sure you have read and understand the Modules Information About Programming Assignments and Style Rules for Assignments before submitting this assignment.Top Down Splaying With IntsThis week you will implement splay trees using top-down splaying, as presented in the modules. In a colorful twist, you will realize the generic by deriving from the base class FHsearch_tree. You can use our FHavlTree generic as a model for how to handle derived generic class syntax (but don’t work in that file, please!). Your job will be far easier than what was done in AVL trees, because:we don’t have to change the node type (so we can use the base FHs_treeNode without any modification or sub-classing),we don’t have to add any data members to the tree, andsome of the methods that required overriding in AVL trees due to the height member (like cloneSubtree()) can be left un-overridden, as their base class implementations will work fine for the splay tree.The SpecDerive the generic class FHsplayTree from FHsearch_tree. Override the following public methods:public boolean insert( E x )public boolean remove( E x )Their meanings are identical to their base class counterparts. The implementation will use splay(), described below. Their algorithms are given in the modules. The private find() (seen below) also uses splay() and, like the base class counterpart, returns null if the item is not in the tree. The public version of find() does not require overriding because the base class version will automatically call the derived protected find() that you will define here. Similarly, contains() will work without being overridden for the same reason.Add the following public method:public E showRoot() – which returns (doesn’t really show) the m_root data, or null if there is nothing in the tree. This is useful for debugging and proving that the class really is splaying.Add the following protected (or private) methods:FHs_treeNode splay( FHs_treeNode root, E x ) – this method is analyzed in depth in the modules and a detailed algorithm is given there.FHs_treeNode rotateWithLeftChild( FHs_treeNode k2 ) – this is (almost) identical with the version found in FHavlTree.java. Make the trivial adjustments and you’ve got it.FHs_treeNode rotateWithRightChild( FHs_treeNode k2 ) – this is (almost) identical with the version found in FHavlTree.java. Make the trivial adjustments and you’ve got it.FHs_treeNode find( FHs_treeNode root, E x ) – this is the private partner of the public find().Implementation RequirementsAssume that the underlying data type, E, implements Comparable, as we have been doing for all search trees.Do not use “header nodes”. In other words, do not use the “clever” solution you find in the text which has “header nodes” and “null nodes” that are used to shorten code. If you turn in code that uses header nodes or adds a null node to your private data, I won’t award any points for the submission – it is an example of code that is “too clever by a half”. Translate the algorithms presented in the modules directly and clearly, without short-cuts, so we can see the connection between your code and the algorithms and diagrams studied.Do not provide public/private pairs or unnecessary methods. If a public method is not recursive, it doesn’t need a private version. And I will restate that you don’t need to rewrite base class methods if the are the same in this derived class. If the only difference is that they call a derived private method, then the base class version will be fine without being overridden.When implementing the algorithm, the variables leftTree and rightTree are merely node references, not actual trees. It would be unnecessarily complicated to declare these as some sort of tree objects. They simply point to the root nodes of their respective growing trees which are augmented one node-at-a-time as the algorithm progresses (though the addition of new maxes or mins on each one).Implementation HintsThe only trick that you will continue to use (we have been doing it all week now) is to let the private methods return a node type that the client can use to modify some node or link. For example, when calling splay() you can’t just call it – you have to capture the return, as in: someNode = splay(someNode, x);
The point is, splay() will be modifying someNode and possibly replacing the node to which it points completely. So the client needs to point to the new object, and this is the only way to accomplish that.Here is a short main that represents the 32-node Integer tree in the text. Once you have it running, compare the results with the diagrams in the text. In particular, make sure that the heights at the various stages are the same as indicated by the diagram in the text. (They can be off-by-one without penalty, as minor adjustments in implementation can result in heights which are +1 or -1 someone else’s implementation.)// CIS 1C Assignment #5
// Instructor Solution Client

import cs_1c.*;

class PrintObject implements Traverser
{
public void visit(E x)
{
System.out.print( x + ” “);
}
};

//——————————————————
public class Foothill
{
// ——- main ————–
public static void main(String[] args) throws Exception
{
int k;
FHsplayTree searchTree = new FHsplayTree();
PrintObject intPrinter = new PrintObject();

searchTree.traverse(intPrinter);

System.out.println( “Initial size: ” + searchTree.size() );
for (k = 1; k <= 32; k++) searchTree.insert(k); System.out.println( "New size: " + searchTree.size() ); System.out.println( "nTraversal"); searchTree.traverse(intPrinter); System.out.println(); for (k = -1; k < 10; k++) { // searchTree.contains(k); // alternative to find() - different error return try { searchTree.find(k); } catch( Exception e ) { System.out.println( " oops " ); } System.out.println( "splay " + k + " --> root: ”
+ searchTree.showRoot()
+ ” height: ” + searchTree.showHeight() );
}
}
}
cs_1c_package_v_7.jar.zip

Unformatted Attachment Preview


Our essay writing service fulfills every request with the highest level of urgency.
attachment

error: Content is protected !!