1. Declare and implement a function restructure() , for performing an AVL tree rotation operation, in the SearchTree class. The interface for the function is provided below:

template typename SearchTree::TPos SearchTree::restructure(const TPos& x) { Algorithm restructure(x):

Input: A node x of a binary search tree T that has both a parent y and a grandparent z Output: Tree T after a trinode restructuring (which corresponds to a single or double rotation) involving nodes x, y, and z process: 1: Let (a,b,c) be a left-to-right (inorder) listing of the nodes x, y, and z, and let (T0,T1,T2,T3) be a left-to-right (inorder) listing of the four subtrees of x, y, and z not rooted at x, y, or z. 2: Replace the subtree rooted at z with a new subtree rooted at b. 3: Let a be the left child of b and let T0 and T1 be the left and right subtrees of a, respectively. 4: Let c be the right child of b and let T2 and T3 be the left and right subtrees of c, respectively. }

SearchTree Header File:

#ifndef _SearchTree_H_ #define _SearchTree_H_

template class Entry { // a (key, value) pair public: // public types typedef K Key; // key type typedef V Value; // value type public: // public functions Entry(const K& k = K(), const V& v = V()) // constructor : _key(k), _value(v) { } const K& key() const { return _key; } // get key (read only) const V& value() const { return _value; } // get value (read only) void setKey(const K& k) { _key = k; } // set key void setValue(const V& v) { _value = v; } // set value private: // private data K _key; // key V _value; // value };

template class SearchTree { // a binary search tree public: // public types typedef typename E::Key K; // a key typedef typename E::Value V; // a value class Iterator; // an iterator/position public: // public functions SearchTree(); // constructor int size() const; // number of entries bool empty() const; // is the tree empty? Iterator find(const K& k); // find entry with key k Iterator insert(const K& k, const V& x); // insert (k,x) void erase(const K& k) throw(NonexistentElement); // remove key k entry void erase(const Iterator& p); // remove entry at p Iterator begin(); // iterator to first entry Iterator end(); // iterator to end entry int printSearchTree(); // print the SearchTree protected: // local utilities typedef BinaryTree BinaryTree; // linked binary tree typedef typename BinaryTree::Position TPos; // position in the tree TPos root() const; // get virtual root TPos finder(const K& k, const TPos& v); // find utility TPos inserter(const K& k, const V& x); // insert utility TPos eraser(TPos& v); // erase utility TPos restructure(const TPos& v) // restructure throw(BoundaryViolation); private: // member data BinaryTree T; // the binary tree int n; // number of entries public: class Iterator { // an iterator/position private: TPos v; // which entry public: Iterator(const TPos& vv) : v(vv) { } // constructor const E& operator*() const { return *v; } // get entry (read only) E& operator*() { return *v; } // get entry (read/write) bool operator==(const Iterator& p) const // are iterators equal? { return v == p.v; } Iterator& operator++(); // inorder successor friend class SearchTree; // give search tree access };// ...insert Iterator class declaration here };

template typename SearchTree ::Iterator SearchTree::printSearchTree(const K& k, const V& x) { if T.isExternal(v) then return v if K < key(v) then return printSearchTree(K, T.left(v)) else if K > key(v) then return printSearchTree(K, T.right(v)) return v }

template // inorder successor typename SearchTree::Iterator SearchTree::Iterator::operator++() { TPos w = v.right(); if (w.isInternal()) { // have right subtree? do { v = w; w = w.left(); } // move down left chain while (w.isInternal()); } else { w = v.parent(); // get parent while (v == w.right()) // move up right chain { v = w; w = w.parent(); } v = w; // and first link to left } return *this; }

template // constructor SearchTree::SearchTree() : T(), n(0) { T.addRoot(); T.expandExternal(T.root()); } // create the super root

template // get virtual root typename SearchTree::TPos SearchTree::root() const { return T.root().left(); } // left child of super root

template // iterator to first entry typename SearchTree::Iterator SearchTree::begin() { TPos v = root(); // start at virtual root while (v.isInternal()) v = v.left(); // find leftmost node return Iterator(v.parent()); }

template // iterator to end entry typename SearchTree::Iterator SearchTree::end() { return Iterator(T.root()); } // return the super root

template // find utility typename SearchTree::TPos SearchTree::finder(const K& k, const TPos& v) { if (v.isExternal()) return v; // key not found if (k < v->key()) return finder(k, v.left()); // search left subtree else if (v->key() < k) return finder(k, v.right()); // search right subtree else return v; // found it here }

template // find entry with key k typename SearchTree::Iterator SearchTree::find(const K& k) { TPos v = finder(k, root()); // search from virtual root if (v.isInternal()) return Iterator(v); // found it else return end(); // didn't find it }

template // insert utility typename SearchTree::TPos SearchTree::inserter(const K& k, const V& x) { TPos v = finder(k, root()); // search from virtual root while (v.isInternal()) // key already exists? v = finder(k, v.right()); // look further T.expandExternal(v); // add new internal node v->setKey(k); v->setValue(x); // set entry n++; // one more entry return v; // return insert position }

template // insert (k,x) typename SearchTree::Iterator SearchTree::insert(const K& k, const V& x) { TPos v = inserter(k, x); return Iterator(v); }

template // remove utility typename SearchTree::TPos SearchTree::eraser(TPos& v) { TPos w; if (v.left().isExternal()) w = v.left(); // remove from left else if (v.right().isExternal()) w = v.right(); // remove from right else { // both internal? w = v.right(); // go to right subtree do { w = w.left(); } while (w.isInternal()); // get leftmost node TPos u = w.parent(); v->setKey(u->key()); v->setValue(u->value()); // copy w's parent to v } n--; // one less entry return T.removeAboveExternal(w); // remove w and parent }

template // remove key k entry void SearchTree::erase(const K& k) throw(NonexistentElement) { TPos v = finder(k, root()); // search from virtual root if (v.isExternal()) // not found? throw NonexistentElement("Erase of nonexistent"); eraser(v); // remove it }

template // erase entry at p void SearchTree::erase(const Iterator& p) { eraser(p.v); }

template typename SearchTree::TPos SearchTree::restructure(const TPos& x) { TPos x = T; TPos y = x.left(); TPos z = x.right(); x.right() = z; x.left() = y; y.height() = max(height(x.left()), height(x.right())) + 1; z.height() = max(height(x.left()), height(x.right())) + 1; return x; }

#endif

Thank you, and is the header file correct?