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 #include #include "AVLTree.h" #include #include 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 << " / " << std::setw(indent) << ' '; } cout << x->ssn << endl; if (x->left != nullptr) { cout << std::setw(indent) << ' ' <<" \\ "; 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 #include using namespace std;

struct AVLNode{ string ssn; string name; AVLNode *left; AVLNode *right; AVLNode *parent; int height; AVLNode(string ss, string na); };