//-------------------------------------------------------------------- // // Laboratory 12 BSTree.jshl // // (Shell) Class definitions for the linked implementation of the // Binary Search Tree ADT -- including the recursive partners of // the public member functions // // The student is to complete all missing or incomplete method // implementations for this class // //-------------------------------------------------------------------- class RLZBSTree { // Data member private RLZBSTreeNode root; // Reference to the root node // Constructor // we just set the root to a valid empty value of null here. public RLZBSTree ( ) { root = null; } // a bit on searching // insert retrieve and remove all do simmillar searches. Insert and remove // simply find the parent for the given node, so we use a private function to // get the parent, and retreive simply does one jump to get the node itself. // after calling findParent. In case the node wanted is the parent, we return // null, so we expect the calling function to check that case their self. // we do this by starting at the root, and bouncing left if the key is less // than what we want, and right if it's more than what we want. we keep doing // this until we either // A) end up past the end of the tree. or // B) we find the node pointing to the node we want. // insert() recursively // insert does two things, first it handles the empty list, so our recursion // doesn't need to, next it calls the recursion method if we do have a list, // after making sure the newElement doesn't already exist, and that handles // the insert. public void insert (TreeElem newElement) { // check for empty list. if ( isEmpty() ) { root = new RLZBSTreeNode( newElement, null, null ); } // otherwise start searching else { insertRec(newElement, root); } } // note, we should always have a node since the reg insert took care of an // empty list, therefore we're looking for three things. // // A. The next spot to search will be null. so insert // B. The next spot has an element, so continue searching. // C. The item to be already in the list. private void insertRec( TreeElem newElement, RLZBSTreeNode current ) { // check for left side. if ( newElement.key() < ((RLZBSTreeElem)current.getElement()).key() ) { // case A, time to insert. if ( current.getLeft() == null ) { current.setLeft( new RLZBSTreeNode(newElement, null, null)); } // otherwise B, so keep searching else { insertRec( newElement, (RLZBSTreeNode)current.getLeft()); } } // check for right side. else if ( newElement.key() > ((RLZBSTreeElem)current.getElement()).key() ) { // again, it's A so we insert. if ( current.getRight() == null ) { current.setRight( new RLZBSTreeNode(newElement, null, null) ); } // otherwise it's B so we keep searching. else { insertRec( newElement, (RLZBSTreeNode)current.getRight() ); } } // NOTE: if it's not above, it must be C, so do nothing. } // Iterative version // insert( TreeElem ) // // This function inserts a TreeElem into the search tree // // Function works as follows // I. make sure there's a root, if not insert as root. // II. make sure it's not the same as the root // III. if not start searching for a parent to the new node to be inserted // IV. insert the node. /* public void insert ( TreeElem newElement ) // Insert element { // check to see if it's empty. if ( isEmpty() ) { root = new RLZBSTreeNode( newElement, null, null ); } else { // otherwise check to see if it's the node we're at. if ( newElement.key() != ((RLZBSTreeElem)root.getElement()).key() ) { RLZBSTreeNode current; // holds the parent to which we are inserting current = root; // we make this first so we can insert it as needed. // our search just bounces left or right until we either find the // element or we hit the end of the list. // NOTE: insert happens after the search. while ( current != null ) // search until we hit the end, we usually // top before this. { // handle if it's more if ( newElement.key() < ((RLZBSTreeElem)current.getElement()).key() ) { // found the spot. make a node and insert if ( current.getLeft() == null ) { RLZBSTreeNode newNode = new RLZBSTreeNode( newElement, null, null ); current.setLeft( newNode ); } // make sure the next element isn't ours. else if ( newElement.key() == ((RLZBSTreeElem)current.getLeft().getElement()).key() ) { break; } // otherwise continue down the tree. else { current = (RLZBSTreeNode)current.getLeft(); } } // hande if it's less. else if ( newElement.key() > ((RLZBSTreeElem)current.getElement()).key() ) { // if it's the end of the tree, insert. if ( current.getRight() == null ) { RLZBSTreeNode newNode = new RLZBSTreeNode( newElement, null, null ); current.setRight( newNode ); } // if it's there, we don't insert. else if ( newElement.key() == ((RLZBSTreeElem)current.getRight().getElement()).key() ) { break; } // otherwise keep looking else { current = (RLZBSTreeNode)current.getRight(); } } // this is inserted though it should never happen. we return null // just in case to prevent an endless loop. else { current = null; } } // end search. } // end if != root } // end if not empty. } */ // retrieve // we just check for the item, this method calls a method which recursively // searches the tree. public TreeElem retrieve( int searchKey ) { return retrieveRec( root, searchKey ); } // retrieveRec // // This method does the actual searching. We just keep searching until // either we find the item or we make it to the end of the list. we return // null if the item doesn't exist otherwise the item itself. public TreeElem retrieveRec( RLZBSTreeNode current, int searchKey ) { // check to see if we're done searching and we missed it. if ( current == null ) { return null; } // otherwise keep searching either left or right as needed else if ( ((RLZBSTreeElem)current.getElement()).key() > searchKey ) { return retrieveRec( (RLZBSTreeNode)current.getLeft(), searchKey ); } else if ( ((RLZBSTreeElem)current.getElement()).key() < searchKey ) { return retrieveRec( (RLZBSTreeNode)current.getRight(), searchKey ); } // check to see if we found it. else //( ((RLZBSTreeElem)current.getElement()).key() == searchKey ) { return (TreeElem)current.getElement(); } } /* // iterative retrieve method // we just find the node and then return it's TreeElem which is the object // it stored on insert. public TreeElem retrieve ( int searchKey ) // Retrieve element { RLZBSTreeNode current = root; // this does a simple search for the item we want. while ( current != null ) // we just keep waiting to see if we run out // of nodes. { // yeah the node is found end the search if ( searchKey == ((RLZBSTreeElem)current.getElement()).key() ) { break; } else if ( searchKey < ((RLZBSTreeElem)current.getElement()).key() ) // it was less than where we are, so we go left. { current = (RLZBSTreeNode)current.getLeft(); } else // searchKey must be greater than the current node so we go right. { current = (RLZBSTreeNode)current.getRight(); } } // end while current != null. // now that we found it, we get it's TreeElem if it exists or return null. if ( current != null ) // if we got something from the find, then we // return the TreeElem stored there. return (TreeElem)current.getElement(); // otherwise it doesn't exist so we return null. else return null; } */ // NOTE: for remove we just have a recursive version. I figure I'll write // a balance before I write an iterative remove. This recursive version of // remove is more complex than the one in the // book. It doesn't rethread on the way out, but it only does so by a series // of if statements while unloading the stack, so it's probably slower since // it takes up more complexity without any speed gain. But since this is // more an experiment for CS, and it's interesting, I'm leaving it. // remove() // this is pretty sloppy. First we handle removing root seperately in remove. // since we don't rethread this isn't as simple as in the book, so it's handled // seperately. // if not removing root, we call removeRec, which recursively hunts for the // correct element to remove. If it fails to find it it does nothing. // once the element is found, the actual removal is the same, though the code // appears in 3 forms, see how it's done on root for the clearest example. // stores the element to replace the deleted one. static so we don't make // multiple copies. used by remove and removeRec only when deleting. static RLZBSTreeElem replace; public void remove ( int deleteKey ) // Remove element { if ( !isEmpty() ) // can't delete from an empty list so skip. { // here's the break down for deleting an element, once we have an // element, we usually delete it from the parent since that needs to // do all the work. it goes in this element. // I) the left branch of the deleted item is passed to getSuccessor, that // finds a proper successor if it exists. // II) Once found, we make sure we're not manipulating the branch because // it's too thin, if so we shift the left branch up a node. // III) Either way, we end up placing the successor in the node. // IV) In the event there is no successor, we take the right branch // and make it the current tree / branch. if ( ((RLZBSTreeElem)root.getElement()).key() == deleteKey ) { // find a successor if it's there replace = getSuccessor( root.getLeft() ); // 1st case, we got a successor, just replace. if ( replace != null ) { // if there's no left-right tree, we gotta shorten the // left branch ourselves. if ( root.getLeft().getElement() == replace ) { root.setLeft( root.getLeft().getLeft() ); } // always change the current element. root.setElement( replace ); } // otherwise there's no left brance, replace with right branch. else { root = (RLZBSTreeNode)root.getRight(); } } // now for remove, we begin the search if there's a tree, and root // isn't being deleted. else { removeRec( root, deleteKey ); } } } // removeRec does the following // A. otherwise search for the parent of the deleted node. // B. if we get to a null in the search, we know it doesn't exist so exit. // C. once found, we pop off the stack once and thenremove simmilarly to how // we did in remove. Note that the root variable is now current.getLeft() // or current.getRight() depending on which pop was last. private void removeRec( TreeNode current, int deleteKey ) { if ( current != null ) // make sure we didn't stop searching. { if ( deleteKey < ((RLZBSTreeElem)current.getElement()).key() ) { removeRec( current.getLeft(), deleteKey ); // delete while removing the stack. so check to make sure we got // the right parent. if ( current.getLeft() != null && ((RLZBSTreeElem)current.getLeft().getElement()).key() == deleteKey ) { // finds the proper replacement if the child left of the deleted // is passed to it. replace = getSuccessor( current.getLeft().getLeft() ); // 1st case, we got a successor, just replace. if ( replace != null ) { // if there's no left-right tree, we gotta shorten the // left branch ourselves. if ( current.getLeft().getLeft().getElement() == replace ) { current.getLeft().setLeft( current.getLeft().getLeft().getLeft() ); } current.getLeft().setElement( replace ); } // otherwise there's no left brance, replace with right branch. else { current.setLeft( current.getLeft().getRight() ); } } // end if found left. } // end if going left. else if ( deleteKey > ((RLZBSTreeElem)current.getElement()).key() ) { removeRec( current.getRight(), deleteKey ); // make sure we don't keep deleting after the first pop off the stack. if ( current.getRight() != null && ((RLZBSTreeElem)current.getRight().getElement()).key() == deleteKey ) { // find the successor, remember we use the left-side-rightmost element. replace = getSuccessor( current.getRight().getLeft() ); // again, if a standard successor is found, use it if ( replace != null ) { // if there's no left-right branch we have to delete for // get successor. if ( replace == current.getRight().getLeft().getElement() ) { current.getRight().setLeft( current.getRight().getLeft().getLeft() ); } current.getRight().setElement( replace ); } else { current.setRight( current.getRight().getRight() ); } } // end found on right side. } // end go right. // otherwise it's found, so we start unpopping the stack and do the // removal. } // if current is null we fall through. } // getSuccessor() // this grabs the rightmost element from the left tree it was given. // getSuccessor() ends up also deleting itself providing it is not from the // node originally passed. If it is, the removes handle the deletion of // it's self. // this saves the successor when found, we make it static so there's only // one copy and save on memory. static RLZBSTreeElem success; private RLZBSTreeElem getSuccessor( TreeNode current ) { // start by making sure there was a left tree, otherwise we return null. if ( current == null ) { return null; } // next, if there's more right subpaths go right. else if ( current.getRight() != null ) { // just saves the return on the way in success = getSuccessor( current.getRight() ); // once the successor was found, we delete it on the first pop off // the stack. if ( current.getRight().getElement() == success ) { current.setRight( current.getRight().getLeft() ); } return success; // just standard for recursion. } // this is the point when we find the successor, we just return it's // element. else return (RLZBSTreeElem)current.getElement(); } // writeKeys just calls a recursive function, inOrder, which recursively // prints the keys inOrder. public void writeKeys ( ) // Output keys { inOrder( root ); } private void inOrder( TreeNode current ) { if ( current != null ) { inOrder( current.getLeft() ); System.out.print( " " + ((RLZBSTreeElem)current.getElement()).key() ); inOrder( current.getRight() ); } } // clears the tree, in practice root is just set to null. public void clear ( ) // Clear tree { root = null; } // determines if the tree is empty. Basically if root is not set we know // it is empty. public boolean isEmpty ( ) // Is tree empty? { if ( root == null ) { return true; } else { return false; } } public boolean isFull ( ) // Is tree full? // Java throws an OutOfMemoryError when no more memory remains, // so here false is always naively returned. { return false; } public void showStructure ( ) // Outputs the keys in a binary search tree. The tree is output // rotated counterclockwise 90 degrees from its conventional // orientation using a "reverse" inorder traversal. This operation is // intended for testing and debugging purposes only. { if ( root == null ) System.out.println("Empty tree"); else { System.out.println( ); showSub(root, 1); System.out.println( ); } } //-------------------------------------------------------------------- // // In-lab operations // //-------------------------------------------------------------------- public void writeLessThan ( int searchKey ) // Output keys // < searchKey { } // height() // // just calls a recursive function that does the addition while traversing // the tree. public int height ( ) // Height of tree { return heightRec(root); } // the recursive element of height, just checks for a null node passed, if // null, the height of the current section is 0, and we stop recursing. // if not null, we recurse the left and right nodes looking for more height, // we end up then returning the max of the two nodes + 1 for the current node. private int heightRec( TreeNode current ) { if ( current == null ) return 0; else return 1 + max(heightRec(current.getLeft()), heightRec(current.getRight()) ); } // max() // // this just compares two numbers passed, and returns the larger of the two. private int max( int x, int y ) { if ( x > y ) return x; else return y; } // Recursive partners of the public member methods // ----- insert these methods here. private void showSub ( TreeNode p, int level ) // Recursive partner of the showStructure( ) method. Outputs the // subtree whose root node is pointed to by p. Parameter level is the // level of this node within the tree. { int j; // Loop counter if ( p == null ) return; TreeElem q = (TreeElem)p.getElement( ); // Cast Object to TreeElem showSub(p.getRight( ), level + 1); // Output right subtree for ( j = 0 ; j < level ; j++ ) // Tab over to level System.out.print("\t"); System.out.print(" " + q.key( )); // Output key if ( ( p.getLeft( ) != null ) && // Output "connector" ( p.getRight( ) != null ) ) System.out.print("<"); else if ( p.getRight( ) != null ) System.out.print("/"); else if ( p.getLeft( ) != null ) System.out.print("\\"); System.out.println( ); showSub(p.getLeft( ), level + 1); // Output left subtree } } // class BSTree