C++: Implement insert() method. Function insert() tries to insert (ss, na) to th

Question

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 <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
    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 <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);
};

Explanation / Answer

Insert() function:

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.