Reference no: EM132136223

1. Implement the Binary Search Tree (BST) in C++, using the Node class template provided below. Please read the provided helper methods in class BST, especially for deleteValue(), make sure you get a fully understanding of the recursive algorithm, by comparing it with Algorithms 3.4.15 and 3.4.16 from page 128 to 130. Are they equivalent?

template <class T>
class Node {
public:
T value;
Node *left;
Node *right;

Node(T val) {
value = val;
left = NULL;
right = NULL;
}

Node(T val, Node<T> left, Node<T> right) {
value = val;
left = left;
right = right;
}
};

template <class T>
class BST {

private:
Node<T> *root;
intheightHelper(Node<T> *root) {
if (!root) return 0;
else return 1 + max(heightHelper(root->left), heightHelper(root->right));
}
bool deleteValueHelper(Node<T>* parent, Node<T>* current, T value) {
if (!current) return false;
if (current->value == value) {
if (current->left == NULL || current->right == NULL) {
Node<T>* temp = current->left;
if (current->right) temp = current->right;
if (parent) {
if (parent->left == current) {
parent->left = temp;
} else {
parent->right = temp;
}
} else {
this->root = temp;
}
} else {
Node<T>* validSubs = current->right;
while (validSubs->left) {
validSubs = validSubs->left;
}
T temp = current->value;
current->value = validSubs->value;
validSubs->value = temp;
return deleteValueHelper(current, current->right, temp);
}
delete current;
return true;
}
return deleteValueHelper(current, current->left, value) ||
deleteValueHelper(current, current->right, value);
}

public:
void add(T val) {
}

// print items in ascending order
void print() {
}

intnodesCount() {

}

intheight() {
return heightHelper(this->root);
}

bool deleteValue(T value) {
return this->deleteValueHelper(NULL, this->root, value);
}
};

Then test it with the following list of last names in our class:
intmain() {
constsize_tarraySize{17};
array <string, arraySize>names{"Taylor", "Tian", "Wheeler",
"Wilmot", "Hoffmann", "Fall", "Kline", "Aparicio",
"Li", "Hess", "Stenseng", "Weiss", "Hood", "Christiansen",
"Dale", "Seward", "Han"};

BST<string> *bst = new BST<string>();

for(size_ti{0}; i<names.size(); ++i)
bst->add(names[i]);
bst->print();
cout<<endl;
cout<<"Nodes count: "<<bst->nodesCount();
cout<<endl;
cout<<"Height: "<<bst->height();
cout<<endl;

bst->deleteValue("Tian");
cout<<"Tian removed: ";
bst->print();
cout<<endl;

bst->deleteValue("Kline");
cout<<"Kline removed: ";
bst->print();
cout<<endl;

return 0;
}

2. Implement the simplified Heap class for integers, in C++. Refer to the algorithms in the textbook.

The required methods are:
- Siftdown (algorithm 3.5.7)
- heapify (algorithm 3.5.12)
- print (to print the array of integers)
Test your heap's heapify method,using the following sequence of integers as initial status of the array.Display the before and after status.
42, 58, 11, 33, 81, 65, 32, 19, 24, 57, 13, 47, 66, 41, 95