I am writing a program in C++ that will implement an AVL tree. the first part of the insertion should work where a node gets inserted like a normal BST node, but after that, I'm not so sure I did this correctly. I don't think my while loop in the insertion is working. I need to be able to check if the balence factor is correct starting from the leaf node to the root node which is why I have the while loop. here is the code:

BSTNode::BSTNode(int key) :

key_(key),

parent_(std::weak_ptr()),

left_(nullptr),

right_(nullptr) {

}

BSTNode::BSTNode(int key, std::weak_ptr parent) :

key_(key),

parent_(parent),

left_(nullptr),

right_(nullptr) {

}

bool BSTNode::IsLeaf() const {

return left_ == nullptr && right_ == nullptr;

}

bool BSTNode::HasLeftChild() const {

return left_ != nullptr;

}

bool BSTNode::HasRightChild() const {

return right_ != nullptr;

}

void BST::Balance(){

if (balance > 1 && key < node->left_->key)

return rightRotate(node);

if (balance < -1 && key > node->right_->key)

return leftRotate(node);

if (balance > 1 && key > node->left_->key)

{

node->left = leftRotate(node->left_);

return rightRotate(node);

}

if (balance < -1 && key < node->right_->key)

{

node->right = rightRotate(node->right_);

return leftRotate(node);

}

}

int BSTNode::rightRotate(std::shared_ptr y)

{

weak_ptr parent = y->parent;

shared_ptr x = y->left_;

shared_ptr t3 = y->right_;

shared_ptr t1 = x->left;

shared_ptr t2 = x->right;

// Perform rotation

x->right_ = y;

y->left_ = t2;

t2.parent=y;

y->parent=x;

x->parent= parent;

if(parent->left_-> == x)

parent->left = x;

if(parent->right_->key == x->key)

parent->right = x;

// Update heights

y->height = max(height(y->left), height(y->right))+1;

x->height = max(height(x->left), height(x->right))+1;

// Return new root

return x;

}

int BSTNode::leftRotate(std::shared_ptr x)

{

weak_ptr parent = x->parent;

shared_ptr t1 = x->left_;

shared_ptr y = x->right_;

shared_ptr t2 = y->left;

shared_ptr t3 = y->right;

// Perform rotation

y->left_ = x;

x->right_ = t2;

t2->parent=x;

x->parent=y;

y->parent= parent;

//determine if left child or right child

if(parent->left_->key == y->key)

parent->left_ = y;

else

parent->right = y;

// Update heights

x->height = max(height(x->left), height(x->right))+1;

y->height = max(height(y->left), height(y->right))+1;

// Return new root

return y;

}

void BSTNode::DeleteChild(std::shared_ptr v) {

if (left_ == v) {

left_ = nullptr;

} else if (right_ == v) {

right_ = nullptr;

} else {

std::cerr << "BSTNode::DeleteChild Error: non-child passed as argument ";

exit(EXIT_FAILURE);

}

}

void BSTNode::ReplaceChild(std::shared_ptr v, std::shared_ptr u) {

if (left_ == u || right_ == u) {

std::cerr << "BSTNode::ReplaceChild Error: child passed as replacement ";

}

if (left_ == v) {

left_ = u;

u->parent_ = v->parent_;

} else if (right_ == v) {

right_ = u;

u->parent_ = v->parent_;

} else {

std::cerr << "BSTNode::ReplaceChild Error: non-child passed as argument ";

exit(EXIT_FAILURE);

}

}

BST::BST() : root_(nullptr), size_(0) {}

int BST::getBalance(std::shared_prt N){

if (N == NULL)

return 0;

return height(N->left) - height(N->right);

}

int BST::height(std::shared_ptr N){

int t;

if (N == NULL)

return -1;

else

{

t = p->height;

return t;

}

}

void BST::Insert(int key) {

if (root_ == nullptr) {

root_ = std::make_shared(key);

size_++;

return;

}

std::shared_ptr currentNode = root_, lastNode = nullptr;

while (currentNode != nullptr) {

lastNode = currentNode;

currentNode = (key < currentNode->key_) ?

currentNode->left_ : currentNode->right_;

}

if (key < lastNode->key_) {

lastNode->left_ = std::make_shared(key, lastNode);

}

else {

lastNode->right_ = std::make_shared(key, lastNode);

}

size_++;

//Starting from w, travel up and find the first unbalanced node.

// Let z be the first unbalanced node, y be the child of z that comes on the path

//from w to z and x be the grandchild of z that comes on the path from w to z.

int balance = getBalance(lastNode);

if(balance!=-1 || balance!=1 || balance!=0){

Balance(lastNode);

}

bool BST::Delete(int key) {

std::shared_ptr currentNode = root_;

while (currentNode != nullptr) {

if (currentNode->key_ == key) {

if (currentNode->IsLeaf()) {

DeleteLeaf(currentNode);

} else if (currentNode->left_ == nullptr) {

assert(currentNode->right_ != nullptr);

std::shared_ptr parent = currentNode->parent_.lock();

parent->ReplaceChild(currentNode, currentNode->right_);

size_--; assert(size_ >= 0);

} else if (currentNode->right_ == nullptr) {

assert(currentNode->left_ != nullptr);

std::shared_ptr parent = currentNode->parent_.lock();

parent->ReplaceChild(currentNode, currentNode->left_);

size_--; assert(size_ >= 0);

} else {

currentNode->key_ = DeleteMin(currentNode);

}

}

currentNode = (key < currentNode->key_) ?

currentNode->left_ : currentNode->right_;

}

return false;

while(lastNode!=root_){

balance=getBalance(lastNode);

Balance(lastNode);

}

}