C++:

Implement insert() method. Function insert() tries to insert (ss, na) to the AVL, if value ss exists in current AVL, insert() function returns false; otherwise, (ss, na) is inserted to the AVL tree and the tree is rebalanced if it is necessary. After insertion/balance checking/rebalance is done, insert() returns true.

Important:

When you implement this project, do NOT use recursion to implement insert()

One insertion may cause some node between the inserted node ant the root out of balance, you need to find the node and rebalance it. For one insertion, you need at most one rebalance.

AVLTree.cpp include insert 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 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); };