1. Declare and implement a function restructure() , for performing an AVL tree r
ID: 3827140 • Letter: 1
Question
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?
Explanation / Answer
Since the code provided from yourside is not complete and as you have asked specifically
for the restructure function, I have not provided the output.
The code for restructure is as below.
template <typename E>
typename SearchTree<E>::TPos SearchTree<E>::restructure(const TPos& v) throw(BoundaryViolation)
{
TPos c = v;
TPos b = c.parent(); // parent
TPos a = b.parent(); // grandParent
TPos gp = a;
TPos ggp = a.parent(); // grandGrandParant
K a_k = a.pTN->entry.key();
K b_k = b.pTN->entry.key();
K c_k = c.pTN->entry.key();
if (a_k > b_k) // L
{
if (b_k > c_k) // *c < *b < *a : LL
{
TPos br; // right child of b
b.pTN->parent = a.pTN->parent;
a.pTN->left = br.pTN = b.pTN->right;
b.pTN->right = a.pTN;
a.pTN->parent = b.pTN;
c.pTN->parent = b.pTN;
br.pTN->parent = a.pTN;
if (ggp.pTN->left == gp.pTN)
ggp.pTN->left = b.pTN;
else if (ggp.pTN->right == gp.pTN)
ggp.pTN->right = b.pTN;
else {
cout << "Error in resturcture : wrong pointers in grand-grand parent for Entry (“;
cout <<v.pTN->entry.value() << "!!" << endl;
}
return b;
} else { // *b < *c < *a : LR
TPos cr, cl; // right child and left child of c
c.pTN->parent = a.pTN->parent;
a.pTN->left = cr.pTN = c.pTN->right;
b.pTN->right = cl.pTN = c.pTN->left;
c.pTN->right = a.pTN;
c.pTN->left = b.pTN;
b.pTN->parent = c.pTN;
a.pTN->parent = c.pTN;
cr.pTN->parent = a.pTN;
cl.pTN->parent = b.pTN;
if (ggp.pTN->left == gp.pTN)
ggp.pTN->left = c.pTN;
else if (ggp.pTN->right == gp.pTN)
ggp.pTN->right = c.pTN;
else {
cout << "Error in resturcture : wrong pointers in grand-grand parent for Entry (“;
cout <<v.pTN->entry.value() << "!!" << endl;
}
return c;
}
}
// *a < * b : R
else
{
// *a < *b < *c : RR
if (b_k < c_k){
TPos bl; // left child of b
b.pTN->parent = a.pTN->parent;
a.pTN->right = bl.pTN = b.pTN->left;
b.pTN->left = a.pTN;
a.pTN->parent = b.pTN;
c.pTN->parent = b.pTN;
bl.pTN->parent = a.pTN;
if (ggp.pTN->left == gp.pTN)
ggp.pTN->left = b.pTN;
else if (ggp.pTN->right == gp.pTN)
ggp.pTN->right = b.pTN;
else {
cout << "Error in resturcture : wrong pointers in grand-grand parent for Entry (“;
cout <<v.pTN->entry.value() << "!!" << endl;
}
return b;
}
// *a < *c < *b : RL
else {
TPos cr, cl; // right child and left child of c
c.pTN->parent = a.pTN->parent;
a.pTN->right = cl.pTN = c.pTN->left;
b.pTN->left = cr.pTN = c.pTN->right;
c.pTN->left = a.pTN;
c.pTN->right = b.pTN;
a.pTN->parent = c.pTN;
b.pTN->parent = c.pTN;
cl.pTN->parent = a.pTN;
cr.pTN->parent = b.pTN;
if (ggp.pTN->left == gp.pTN)
ggp.pTN->left = c.pTN;
else if (ggp.pTN->right == gp.pTN)
ggp.pTN->right = c.pTN;
else {
cout << "Error in resturcture : wrong pointers in grand-grand parent for Entry (“;
cout <<v.pTN->entry.value() << "!!" << endl;
}
return c;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.