Write in JAVA:

Write an implementation of the Set class, with associated iterators using a Binary Search Tree. Add to each node a link to the parent node.

Stub program on C++ is in this folder. Complete ToDo-s to make program work. Students who write programs on Java and Python, consider this program as pseudo code.

#include #include #include #include #include #include

#include "BinarySearchTree.h"

template class Set { public:

typedef Key key_type; typedef Key value_type; typedef std::size_t size_type;

class iterator {

friend class Set;

public:

// TODO Define copy constructor

friend bool operator==( const iterator& lh, const iterator& rh) { return lh.node == rh.node; }

// TODO Define friend operator!=

iterator& operator++() { node = set->tree.next(node); return *this; }

const Key& operator*() { return node->element; }

private:

typedef typename BinarySearchTree::BinaryNode BinaryNode;

const Set *const set; BinaryNode * node;

iterator( const Set *const theSet, BinaryNode *const theNode ) : set(theSet), node( theNode ) {} };

iterator begin() { return iterator(this,tree.start()); } iterator end () { return iterator(this,nullptr); }

Set() {}

// Copy constructor Set( const Set &rhs ) : tree{ rhs.tree } {}

// Move constructor Set( Set &&rhs ) : tree{ std::move(rhs.tree) } {}

size_type size() const { // TODO implement method size using tree.start() and tree.next() }

// TODO Define method empty()

void clear() { tree.makeEmpty(); }

void insert( const Key &p ){ tree.insert(p); }

size_type erase( const Key& key ) {

return tree.remove(key) ? 1 : 0; }

size_type erase( const iterator& iter ) {

// TODO Implement method erase() }

iterator find( const Key &key ) const {

// TODO Implement method find() }

size_type count( const Key &key ) const {

return tree.find(key) ? 1 : 0; }

private:

BinarySearchTree tree;

template< class K> friend std::ostream operator<< ( std::ostream &os, const Set &set ) {

set.tree.printTree(os); return os; }

};

#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H

//#include

#include

// BinarySearchTree class // // CONSTRUCTION: zero parameter // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // bool contains( x ) --> Return true if x is present // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // void printTree( ) --> Print tree in sorted order // ******************ERRORS******************************** // Throws UnderflowException as warranted

template class BinarySearchTree { public:

class UnderflowException { }; class IllegalArgumentException { }; class ArrayIndexOutOfBoundsException { }; class IteratorOutOfBoundsException { }; class IteratorMismatchException { }; class IteratorUninitializedException { };

struct BinaryNode { Comparable element; BinaryNode *parent; BinaryNode *left; BinaryNode *right;

BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt, BinaryNode *p ) : element{ theElement }, parent{p}, left{ lt }, right{ rt } { }

BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt, BinaryNode *p ) : element{ std::move( theElement ) }, parent{p}, left{ lt }, right{ rt } { } };

BinarySearchTree( ) : root{ nullptr } { }

/** * Copy constructor */ BinarySearchTree( const BinarySearchTree &rhs ) : root{ nullptr } { root = clone( rhs.root ); }

/** * Move constructor */ BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root } { rhs.root = nullptr; } /** * Destructor for the tree */ ~BinarySearchTree( ) { makeEmpty( ); }

/** * Copy assignment */ BinarySearchTree& operator=( const BinarySearchTree & rhs ) { BinarySearchTree copy = rhs; std::swap( *this, copy ); return *this; } /** * Move assignment */ BinarySearchTree& operator=( BinarySearchTree && rhs ) { std::swap( root, rhs.root ); return *this; } /** * Find the smallest item in the tree. * Throw UnderflowException if empty. */ const Comparable & findMin( ) const { if( isEmpty( ) ) throw UnderflowException{ }; return findMin( root )->element; }

/** * Find the largest item in the tree. * Throw UnderflowException if empty. */ const Comparable & findMax( ) const { if( isEmpty( ) ) throw UnderflowException{ }; return findMax( root )->element; }

/** * Returns true if x is found in the tree. */ bool contains( const Comparable & x ) const { return contains( x, root ); }

/** * Test if the tree is logically empty. * Return true if empty, false otherwise. */ bool isEmpty( ) const { return root == nullptr; }

/** * Print the tree contents in sorted order. */ void printTree( std::ostream & out = std::cout ) const { if( isEmpty( ) ) out << "Empty tree" << " "; else printTree( root, out ); }

/** * Make the tree logically empty. */ void makeEmpty( ) { makeEmpty( root ); }

/** * Insert x into the tree; duplicates are ignored. */ void insert( const Comparable & x ) { insert( x, root, nullptr ); } /** * Insert x into the tree; duplicates are ignored. */ void insert( Comparable && x ) { insert( std::move( x ), root, nullptr ); } /** * Find x in the tree. Nothing is done if x is not found. */ BinaryNode* find( const Comparable &x ) const { return find(x,root); }

/** * Remove x from the tree. Nothing is done if x is not found. */ bool remove( const Comparable &x ) { return remove( find(x), root ); }

/** * Remove node t from the tree. */ bool remove( BinaryNode *const t ) { return remove( t, root ); }

BinaryNode* start() const { return mostLeft(root); }

static BinaryNode* next( BinaryNode *t ) { // We already traversed // - all left descendants // - node t itself

if ( !t ) return nullptr;

BinaryNode *q = t->right;

if ( q ) {

// There is right child, return right smallest grandchild

q = mostLeft(q);

} else {

// There is no right child. It means that node t and all its // descendants are traversed.

q = t; while (true) { q = q->parent; if ( !q || t == q->left ) break; t = q; } }

return q; }

private:

BinaryNode *root;

static BinaryNode* mostLeft( BinaryNode *q ) { if (q) { while ( q->left ) q = q->left; } return q; }

/** * Internal method to find an element in a subtree. * x is the item to find. * t is the node that roots the subtree. * Returns the found node or nullptr. */

// ****** RECURSIVE VERSION************************* // static BinaryNode* find( const Comparable &x, const BinaryNode *const t ) // { // return t == nullptr ? nullptr // : x < t->element ? find( x, t->left ) // : t->element < x ? find( x, t->right ) // : /* equal */ t; // }

static BinaryNode* find( const Comparable &x, BinaryNode *t ) { while( t != nullptr ) { if( x < t->element ) t = t->left; else if( t->element < x ) t = t->right; else return t; // Match }

return nullptr; // No match }

/** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ static void insert( const Comparable &x, BinaryNode* &t, BinaryNode *p ) { if( t == nullptr ) t = new BinaryNode{ x, nullptr, nullptr, p }; else if( x < t->element ) insert( x, t->left, t ); else if( t->element < x ) insert( x, t->right, t ); else ; // Duplicate; do nothing } /** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ static void insert( Comparable &&x, BinaryNode* &t, BinaryNode *p ) { if( t == nullptr ) t = new BinaryNode{ std::move( x ), nullptr, nullptr, p }; else if( x < t->element ) insert( std::move( x ), t->left, t ); else if( t->element < x ) insert( std::move( x ), t->right, t ); else ; // Duplicate; do nothing }

/** * Internal method to move node from one parent to another. * s is the old node * q is the new node to be moved under s's parent * Set the new root of the subtree. */

static void repointParent(

const BinaryNode *const s, // old node BinaryNode *const q // new node ) { BinaryNode *const p = s->parent; ( p->left == s ? p->left : p->right ) = q; if ( q ) q->parent = p; }

/** * Internal method to replace one node with another. * t is the node to replace * m is the mode that replaces it * Returns m. */ static BinaryNode* replace( BinaryNode * &t, BinaryNode *m ) { if (m) repointParent( m, nullptr ); repointParent( t, m ); delete t; return m; } /** * Internal method to remove from a subtree. * t is the node to remove * Set the new root of the subtree. */ static bool remove( BinaryNode *t, BinaryNode* &root ) { if( !t ) return false; // Item not found; do nothing

BinaryNode *m = ( t->left && t->right ) ? replace( t, mostLeft(t->right) ) // Two children : replace( t, t->left ? t->left : t->right );

if ( root == t ) root = m;

return true; }

/** * Internal method to find the smallest item in a subtree t. * Return node containing the smallest item. */ static BinaryNode * findMin( BinaryNode *const t ) { if( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); }

/** * Internal method to find the largest item in a subtree t. * Return node containing the largest item. */ static BinaryNode * findMax( BinaryNode *t ) { if( t != nullptr ) { while( t->right != nullptr ) t = t->right; }

return t; }

/** * Internal method to test if an item is in a subtree. * x is item to search for. * t is the node that roots the subtree. */

/****** RECURSIVE VERSION*************************

bool contains( const Comparable &x, BinaryNode *t ) const { if( t == nullptr ) return false; else if( x < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->right ); else return true; // Match } */

static bool contains( const Comparable &x, const BinaryNode *t ) { return find(x,const_cast(t)); }

/** * Internal method to make subtree empty. */ static void makeEmpty( BinaryNode * &t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; }

/** * Internal method to print a subtree rooted at t in sorted order. */ static void printTree( const BinaryNode *const t, std::ostream &out ) { if( t != nullptr ) { printTree( t->left, out ); out << t->element << " "; printTree( t->right, out ); } }

/** * Internal method to clone subtree. */ static BinaryNode* clone(

const BinaryNode *const t, // node to clone BinaryNode *const p = nullptr // parent of the clone node ) { if( t == nullptr ) return nullptr;

BinaryNode *const node = new BinaryNode{ t->element, nullptr, nullptr, p };

node->left = clone( t->left, node ); node->right = clone( t->right, node );

return node; } };

#endif