C++: PLEASE HELP~!!! ~~~~~~~~
Implement bool AVLTree::deleteNode(string ss) method. Function deleteNode() tries to delete the node containing value ss. If there is no such node, it returns false. Otherwise, it deletes the node, check the balance of the tree, rebalance the tree if it is necessary. When you delete a node, consider three different scenarios:
-The node is a leaf
-The node has only ONE child subtree
-The node has two child subtrees
Important:
When you implement this project, do NOT use recursion to implement delete().
// delete the node containing value ss
// if there is not
such node, return false
// otherwise, delete the node, balance the tree, return true
bool AVLTree::deleteNode(string ss){
// please implement here
return true;
}
AVLTree.cpp (INCLUDE DELETENODE METHOD HERE)
#include <iostream>
#include <string>
#include "AVLTree.h"
#include <iomanip>
#include <queue>
using namespace std;
AVLTree::AVLTree(){
root = nullptr;
}
AVLTree::~AVLTree(){
}
AVLNode* AVLTree::getRoot(){
return root;
}
// search value ss in the AVL tree
bool AVLTree::find(string ss){
if (root == nullptr) {
return false;
}
AVLNode* node = root;
while (node != nullptr) {
if
(ss.compare(node->ssn) == 0) {
return true;
}
if
(ss.compare(node->ssn) < 0) {
node = node->left;
}
else{
node = node->right;
}
}
return false;
}
// return the height of the subtree rooted at node
// if subtree is empty, height is -1
// if subtree has one node, height is 0
int AVLTree::height(AVLNode* node){
if(node != nullptr){
return
node->height;
}
else{
return -1;
}
}
// return the balance factor of the node
int AVLTree::balanceFactor(AVLNode* node){
return height(node->left) -
height(node->right);
}
// update the height of the node
// this should be done whenever the tree is modified
void AVLTree::updateHeight(AVLNode* node){
int hl = height(node->left);
int hr = height(node->right);
node->height = (hl>hr ? hl : hr) +
1;
}
// rotate right the subtree rooted at node
// return the new root of the subtree
AVLNode* AVLTree::rotateRight(AVLNode* node){
AVLNode* lp =
node->left; // left child of
node
if (node->parent!=nullptr) { // node is not
root
if
(node->parent->left == node) { // node is a left child
node->parent->left = lp;
}else{
node->parent->right = lp; // node is
a right child
}
}
if (lp->right != nullptr)
{ //
pointer update
lp->right->parent
= node;
}
lp->parent = node->parent;
node->left = lp->right;
lp->right = node;
node->parent = lp;
updateHeight(node);
// after rotation, update height
updateHeight(lp);
// after rotation, update height
if (node == root) {
root = lp;
}
return lp; // lp is the new root of the
subtree
}
// rotate left the subtree rooted at node
// return the new root of the subtree
AVLNode* AVLTree::rotateLeft(AVLNode* node){
AVLNode* rp = node->right;
if (node->parent!=nullptr) {
if
(node->parent->left == node) {
node->parent->left = rp;
}else{
node->parent->right = rp;
}
}
if (rp->left != nullptr) {
rp->left->parent =
node;
}
rp->parent = node->parent;
node->right = rp->left;
rp->left = node;
node->parent = rp;
node->parent = rp;
updateHeight(node);
updateHeight(rp);
if (node == root) {
root = rp;
}
return rp;
}
// rebalance a tree rooted at node
// return the new root of the subtree
AVLNode* AVLTree::balance(AVLNode* node){
updateHeight(node);
if (balanceFactor(node) == 2) {
if
(balanceFactor(node->left) < 0) {
node->left = rotateLeft(node->left); // for left right
case
}
AVLNode* temp =
rotateRight(node);
updateHeight(temp);
return temp;
}
if (balanceFactor(node) == -2) {
if
(balanceFactor(node->right) > 0) {
node->right = rotateRight(node->right); // for right left
case
}
AVLNode* temp2 =
rotateLeft(node);
updateHeight(temp2);
return temp2;
}
return node;
}
// insert a new node with (ss, na) to
the AVL tree
// if there exists ss value, return false
// otherwise, insert it, balance the tree, return true
bool AVLTree::insert(string ss, string na){
// please implement here
bool isExist = find(ss);
if (isExist) return false;
AVLNode* newNode = new AVLNode(ss, na);
newNode->left = nullptr;
newNode->right = nullptr;
newNode->parent = nullptr;
// if the tree is empty, in other words root is
null, then no need to go further
if(root == nullptr) {
root = newNode;
updateHeight(root);
return true;
}
AVLNode* node = root;
while (node != nullptr) {
if
(ss.compare(node->ssn) == 0) {
// This should never reach
return false;
}
if
(ss.compare(node->ssn) < 0) {
// insert in the left subtree
if(node->left == nullptr) {
node->left = newNode;
newNode->parent = node;
break;
}
node = node->left;
}
else{
if(node->right == nullptr) {
node->right = newNode;
newNode->parent = node;
break;
}
node = node->right;
}
}
// balance the new formed tree
AVLNode* currentNode = newNode;
while(currentNode != nullptr) {
currentNode =
currentNode->parent;
}
currentNode = newNode;
bool isUnbalanced = false;
while(currentNode != nullptr) {
int balance =
balanceFactor(currentNode);
if(balance > 1 ||
balance < -1) {
isUnbalanced = true;
break;
}
}
if(isUnbalanced) {
balance(currentNode);
}
return true;
}
AVLNode* AVLTree::maxOfSubtree(AVLNode* node){
if (node == nullptr) {
return nullptr;
}
while (node->right != nullptr) {
node =
node->right;
}
return node;
}
// delete the node containing value ss
// if there is not such node, return false
// otherwise, delete the node, balance the tree, return true
bool AVLTree::deleteNode(string ss){
// please implement here
return true;
}
// internal function
// do not call it directly
void AVLTree::print(AVLNode* x, int indent){
if(x == nullptr) return;
if (x->right != nullptr) {
print(x->right,
indent+4);
}
if (indent != 0) {
cout <<
std::setw(indent) << ' ';
}
if(x->right != nullptr){
cout << " /\n"
<< std::setw(indent) << ' ';
}
cout << x->ssn << endl;
if (x->left != nullptr) {
cout <<
std::setw(indent) << ' ' <<" \\\n";
print(x->left,
indent+4);
}
}
// print out the structure of the binary tree
// use it for debugging, I love this function
void AVLTree::print(){
int count = 0;
print(root, count);
}
AVL.h
#include <iostream>
#include <string>
using namespace std;
struct AVLNode{
string ssn;
string name;
AVLNode *left;
AVLNode *right;
AVLNode *parent;
int height;
AVLNode(string ss, string na);
};
Code:
AVLNode.h
//Include libraries
#include <iostream>
#include <string>
//Use namespace
using namespace std;
//Define structure
struct AVLNode
{
//Declare variable
string ssn;
//Declare variable
string name;
//Declare variable
AVLNode *left;
//Declare variable
AVLNode *right;
//Declare variable
AVLNode *parent;
//Declare variable
int height;
//Call method
AVLNode(string ss, string na);
};
AVLNode.cpp
//Include libraries
#include <iostream>
#include <string>
#include "AVLNode.h"
//Use namespace
using namespace std;
//Define method
AVLNode::AVLNode(string ss, string na)
{
//Assign value
ssn = ss;
//Assign value
name = na;
//Assign value
height = 0;
//Assign value
left = nullptr;
//Assign value
right = nullptr;
//Assign value
parent = nullptr;
}
AVLTree.h
//Include libraries
#include <iostream>
#include <string>
#include "AVLNode.h"
//Use namespace
using namespace std;
//Define class
class AVLTree
{
//Create node
AVLNode* root;
//Define access specifier
public:
//Define constructor
AVLTree();
//Define destructor
~AVLTree();
//Define method
AVLNode* getRoot();
//Define method
bool find(string ss);
//Define method
int height(AVLNode* node);
//Define method
int balanceFactor(AVLNode* node);
//Define method
void updateHeight(AVLNode* node);
//Define method
AVLNode * rotateRight(AVLNode* node);
//Define method
AVLNode * rotateLeft(AVLNode* node);
//Define method
bool insert(string ss, string na);
//Define method
void print(AVLNode* x, int indent);
//Define method
void print();
//Define method
AVLNode* balance(AVLNode* node);
//Define method
AVLNode* maxOfSubtree(AVLNode* node);
//Define method
bool deleteNode(string ss);
//Define method
void levelOrder();
};
AVLTree.cpp
//Include libraries
#include <iostream>
#include <string>
#include "AVLTree.h"
#include <iomanip>
#include <queue>
using namespace std;
//Define method
AVLTree::AVLTree()
{
root = nullptr;
}
//Define method
AVLTree::~AVLTree()
{
AVLNode *nextNode = nullptr;
AVLNode *current = root;
while (current)
{
if (!current->left)
{
nextNode = current->right;
delete current;
}
else
{
nextNode = current->left;
current->left = nextNode->right;
nextNode->right = current;
}
current = nextNode;
}
}
//Define method
AVLNode* AVLTree::getRoot()
{
return root;
}
//Define method
bool AVLTree::find(string ss)
{
if (root == nullptr)
{
return false;
}
AVLNode* node = root;
while (node != nullptr)
{
if (ss.compare(node->ssn) == 0)
{
return true;
}
if (ss.compare(node->ssn) < 0)
{
node = node->left;
}
else
{
node = node->right;
}
}
return false;
}
//Define method
int AVLTree::height(AVLNode* node)
{
if(node != nullptr)
{
return node->height;
}
else
{
return -1;
}
}
//Define method
int AVLTree::balanceFactor(AVLNode* node)
{
return height(node->left) - height(node->right);
}
//Define method
void AVLTree::updateHeight(AVLNode* node)
{
int hl = height(node->left);
int hr = height(node->right);
node->height = (hl>hr ? hl : hr) + 1;
}
//Define method
AVLNode* AVLTree::rotateRight(AVLNode* node)
{
AVLNode* lp = node->left;
if (node->parent!=nullptr)
{
if (node->parent->left == node)
{
node->parent->left = lp;
}
else
{
node->parent->right = lp;
}
}
if (lp->right != nullptr)
{
lp->right->parent = node;
}
lp->parent = node->parent;
node->left = lp->right;
lp->right = node;
node->parent = lp;
updateHeight(node);
updateHeight(lp);
if (node == root)
{
root = lp;
}
return lp;
}
//Define method
AVLNode* AVLTree::rotateLeft(AVLNode* node)
{
AVLNode* rp = node->right;
if (node->parent!=nullptr)
{
if (node->parent->left == node)
{
node->parent->left = rp;
}
else
{
node->parent->right = rp;
}
}
if (rp->left != nullptr)
{
rp->left->parent = node;
}
rp->parent = node->parent;
node->right = rp->left;
rp->left = node;
node->parent = rp;
node->parent = rp;
updateHeight(node);
updateHeight(rp);
if (node == root)
{
root = rp;
}
return rp;
}
//Define method
AVLNode* AVLTree::balance(AVLNode* node)
{
updateHeight(node);
if (balanceFactor(node) == 2)
{
if (balanceFactor(node->left) < 0)
{
node->left = rotateLeft(node->left);
}
AVLNode* temp = rotateRight(node);
updateHeight(temp);
return temp;
}
if (balanceFactor(node) == -2)
{
if (balanceFactor(node->right) > 0)
{
node->right = rotateRight(node->right);
}
AVLNode* temp2 = rotateLeft(node);
updateHeight(temp2);
return temp2;
}
return node;
}
//Define method
bool AVLTree::insert(string ss, string na)
{
if (!root)
{
root = new AVLNode(ss, na);
return true;
}
else
{
AVLNode *newNode = new AVLNode(ss, na);
AVLNode *current = root;
AVLNode *parent = nullptr;
while (current)
{
if (ss == current->ssn)
{
return false;
}
else if (ss < current->ssn)
{
parent = current;
current = current->left;
}
else
{
parent = current;
current = current->right;
}
}
if (ss < parent->ssn)
{
parent->left = newNode;
newNode->parent = parent;
}
else
{
parent->right = newNode;
newNode->parent = parent;
}
while (parent)
{
parent = balance(parent);
parent = parent->parent;
}
return true;
}
return true;
}
//Define method
AVLNode* AVLTree::maxOfSubtree(AVLNode* node)
{
if (node == nullptr)
{
return nullptr;
}
while (node->right != nullptr)
{
node = node->right;
}
return node;
}
//Define method
bool AVLTree::deleteNode(string ss)
{
if (!root)
{
return false;
}
else
{
bool nodeFound = false;
AVLNode *current = root;
AVLNode *parent = nullptr;
AVLNode *nodeToRemove = nullptr;
AVLNode *nodeToRemoveParent = nullptr;
while (current)
{
if (ss == current->ssn)
{
nodeFound = true;
if (!current->left && !current->right)
{
if (parent->left == current)
{
parent->left = nullptr;
}
else
{
parent->right = nullptr;
}
nodeToRemove = current;
nodeToRemoveParent = parent;
break;
}
else if (current->left && !current->right)
{
if (current == root)
{
nodeToRemove = root;
root = root->left;
root->parent = nullptr;
break;
}
else
{
AVLNode *temp = current->left;
if (parent->left == current)
{
parent->left = temp;
temp->parent = parent;
}
else
{
parent->right = temp;
temp->parent = parent;
}
nodeToRemove = current;
nodeToRemoveParent = parent;
break;
}
}
else if (!current->left && current->right)
{
if (current == root)
{
nodeToRemove = root;
root = root->right;
root->parent = nullptr;
break;
}
else
{
AVLNode *temp = current->right;
if (parent->left == current)
{
parent->left = temp;
temp->parent = parent;
}
else
{
parent->right = temp;
temp->parent = parent;
}
nodeToRemove = current;
nodeToRemoveParent = parent;
break;
}
}
else if (current->left && current->right)
{
AVLNode *maxNode = maxOfSubtree(current->left);
AVLNode *maxNodeParent = nullptr;
AVLNode *curr = root;
while (curr)
{
if (maxNode->ssn == curr->ssn)
{
break;
}
else if (maxNode->ssn < curr->ssn)
{
maxNodeParent = curr;
curr = curr->left;
}
else
{
maxNodeParent = curr;
curr = curr->right;
}
}
current->ssn = maxNode->ssn;
current->name = maxNode->name;
if (!maxNode->left && !maxNode->right)
{
if (maxNodeParent->left == maxNode)
{
maxNodeParent->left = nullptr;
}
else
{
maxNodeParent->right = nullptr;
}
}
else if (maxNode->left && !maxNode->right)
{
AVLNode *temp = maxNode->left;
if (maxNodeParent->left == maxNode)
{
maxNodeParent->left = temp;
temp->parent = maxNodeParent;
}
else
{
maxNodeParent->right = temp;
temp->parent = maxNodeParent;
}
}
nodeToRemove = maxNode;
nodeToRemoveParent = maxNodeParent;
break;
}
}
else if (ss < current->ssn)
{
parent = current;
current = current->left;
}
else
{
parent = current;
current = current->right;
}
}
if (nodeFound)
{
delete nodeToRemove;
while (nodeToRemoveParent)
{
nodeToRemoveParent = balance(nodeToRemoveParent);
nodeToRemoveParent = nodeToRemoveParent->parent;
}
return true;
}
}
return false;
}
//Define method
void AVLTree::print(AVLNode* x, int indent)
{
if(x == nullptr) return;
if (x->right != nullptr)
{
print(x->right, indent+4);
}
if (indent != 0)
{
cout << std::setw(indent) << ' ';
}
if(x->right != nullptr)
{
cout << " /\n" << std::setw(indent) << ' ';
}
cout << x->ssn << endl;
if (x->left != nullptr)
{
cout << std::setw(indent) << ' ' <<" \\\n";
print(x->left, indent+4);
}
}
//Define method
void AVLTree::print()
{
int count = 0;
print(root, count);
}
//Define method
void AVLTree::levelOrder()
{
int totalNodes = 0;
if (root)
{
AVLNode *current = root;
AVLNode *parent = nullptr;
while (current)
{
if (!current->left)
{
totalNodes++;
current = current->right;
}
else
{
parent = current->left;
while (parent->right)
{
if (parent->right == current)
{
break;
}
else
{
parent = parent->right;
}
}
if (!parent->right)
{
parent->right = current;
current = current->left;
}
else
{
parent->right = nullptr;
totalNodes++;
current = current->right;
}
}
}
}
cout << "tree size . . . " << totalNodes << endl;
}
Main.cpp
//Include library
#include <iostream>
#include "AVLTree.h"
//Use namespace
using namespace std;
//Define main
int main()
{
//Create instance
AVLTree temp;
//Insert
temp.insert("12", "a");
//Insert
temp.insert("10", "b");
//Insert
temp.insert("09", "c");
//Insert
temp.insert("08", "d");
//Insert
temp.insert("06", "d");
//Insert
temp.insert("04", "d");
//Insert
temp.insert("02", "d");
//Display
temp.print();
//Display message
cout << "insert 07 " << endl;
//Insert
temp.insert("07", "d");
//Display
temp.print();
//Display message
cout << "Delete 12, 10, 09 06" << endl;
//Delete node
temp.deleteNode("12");
//Delete node
temp.deleteNode("10");
//Delete node
temp.deleteNode("09");
//Delete node
temp.deleteNode("06");
//Display
temp.print();
//Pause console window
system("pause");
}
C++: PLEASE HELP~!!! ~~~~~~~~ Implement bool AVLTree::deleteNode(string ss) method. Function deleteNode() tries to delete the node...
I need help to write this code in C++, I am struggling to find max node's parent's right child and max node's left child. Node* maxValueNode(Node* node) { Node* current = node; while (current && current->right != NULL) current = current->right; return current; } void deleteNode(BST* tree, Node* node, Node* parent) { //TODO - follow the lecture pseudocode to write the deleteNode function // - returns true if the value was deleted, false if not // - don't forget to...
Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary tree. Add this function to the class binaryTreeType and create a program to test this function. #include <iostream> using namespace std; //Definition of the Node template <class elemType> struct nodeType { elemType info; nodeType<elemType> *lLink; nodeType<elemType> *rLink; }; //Definition of the class template <class elemType> class binaryTreeType { public: //Overload the assignment operator. const binaryTreeType<elemType>& operator=(const binaryTreeType<elemType>&) { if (this != &otherTree) //avoid self-copy...
In C++ I need the printRange function, and the main.cpp program. Thanks. (Binary search tree) Write a function printRange that takes as input a binary search tree t and two keys, k1 and k2, which are ordered so that k1 < k2, and print all elements x in the tree such that k1 <= x <= k2. You can add this function in BinarySearchTree.h (click the link) that we used in the lecture and lab 7. public: void printRange(int k1,...
3. (Gaddis Exercises 20.4) Tree Height Write a recursive member function for the BinaryTree class that returns the height of the tree. The height of the tree is the number of levels it contains. Demonstrate the function in a driver program. CPP FILE CODE: #include "BinaryTree.h" #include <iostream> using namespace std; BinaryTree::BinaryTree() { root = NULL; } BinaryTree::~BinaryTree() { destroy(root); } bool BinaryTree::search(int data) { return search(data, root); } void BinaryTree::insert(int data) { insert(data, root); } void BinaryTree::traverseInOrder() { traverseInOrder(root);...
Using the following implementation of Tree class Node { public int iData; // data item (key) public double dData; // data item public Node leftChild; // this node's left child public Node rightChild; // this node's right child public void displayNode() // display ourself { System.out.print('{'); System.out.print(iData); System.out.print(", "); System.out.print(dData); System.out.print("} "); } } // end class Node //------------------------------------------------------------------ import java.io.IOException; import java.util.Stack; public class Tree { private Node root; // first node of tree // ------------------------------------------------------------- public Tree() // constructor { root = null; }...
After the header, each line of the database file rebase210.txt contains the name of a restriction enzyme and possible DNA sites the enzyme may cut (cut location is indicated by a ‘) in the following format: enzyme_acronym/recognition_sequence/…/recognition_sequence// For instance the first few lines of rebase210.txt are: AanI/TTA'TAA// AarI/CACCTGCNNNN'NNNN/'NNNNNNNNGCAGGTG// AasI/GACNNNN'NNGTC// AatII/GACGT'C// AbsI/CC'TCGAGG// AccI/GT'MKAC// AccII/CG'CG// AccIII/T'CCGGA// Acc16I/TGC'GCA// Acc36I/ACCTGCNNNN'NNNN/'NNNNNNNNGCAGGT// … That means that each line contains one enzyme acronym associated with one or more recognition sequences. For example on line 2:The enzyme acronym...
Hi there, I am working on a binary search tree code in c++. The program must store and update students' academic records, each node includes the student name, credits attempted, credits earned and GPA. I have made some progress with the code and written most of the functions in the .cpp file (already did the .h file) but i am struggling with what to put in the main and how to put an update part in the insert function. I...
Question - modify the code below so that for a node, the value of every node of its right subtree is less the node, and the value of each node of its left subtree is greater than the node. - create such a binary tree in the Main method, and call the following method: InOrder(Node theRoot), PreOrder(Node theRoot), PostOrder(Node theRoot), FindMin(), FindMax(), Find(int key) using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;...
Need help in the below question. Answer in java Start with the tree.java program (Listing 8.1) and modify it to create a binary tree from a string of letters (like A, B, and so on) entered by the user. Each letter will be displayed in its own node. Construct the tree so that all the nodes that contain letters are leaves. Parent nodes can contain some non-letter symbol like +. Make sure that every parent node has exactly two children....
C++ Binary Search Tree question. I heed help with the level 2 question please, as level 1 is already completed. I will rate the answer a 100% thumbs up. I really appreciate the help!. Thank you! searching.cpp #include <getopt.h> #include <iostream> #include <sstream> #include <stdlib.h> #include <unistd.h> using namespace std; // global variable for tree operations // use to control tree maintenance operations enum Mode { simple, randomised, avl } mode; // tree type // returns size of tree //...