Дерево C++ AVL — замена рекурсии ⇐ C++

[Anonymous]

Моя программа AVL
деревья хорошо работают при количестве записей примерно до 5000, но не больше. Проблема, вероятно, будет в переполнении памяти в стеке из-за рекурсии. Может ли кто-нибудь подсказать мне, что изменить, чтобы не нарушить функциональность. Полная программа: https://onecompiler.com/cpp/42yawu385 - количество тестов можно изменить
template
void Tree::Updateheight(Node* root)
{
if(root != NULL)
{
int val = 1;

if(root->left != NULL)
val = root->left->height + 1;

if(root->right != NULL)
val = max(val, root->right->height + 1);

root->height = val;
}
}

// Function to handle Left Left Case
template
typename Tree::Node* Tree::LLR(Node* root)
{
Node* tmpnode = root->left;
root->left = tmpnode->right;

if(tmpnode->right != nullptr)
tmpnode->right->parent = root;

tmpnode->right = root;
tmpnode->parent = root->parent;

root->parent = tmpnode;

if(tmpnode->parent != nullptr && root->value < tmpnode->parent->value)
{
tmpnode->parent->left = tmpnode;
}
else
{
if (tmpnode->parent != NULL)
tmpnode->parent->right = tmpnode;
}

// Make tmpnode as the new root
root = tmpnode;

// Update the heights
Updateheight(root->left);
Updateheight(root->right);
Updateheight(root);
Updateheight(root->parent);

// Return the root node
return root;
}

template
typename Tree::Node* Tree::RRR(Node* root)
{
Node* tmpnode = root->right;
root->right = tmpnode->left;

if(tmpnode->left != NULL)
tmpnode->left->parent = root;

tmpnode->left = root;
tmpnode->parent = root->parent;

root->parent = tmpnode;

if(tmpnode->parent != NULL && root->value < tmpnode->parent->value)
{
tmpnode->parent->left = tmpnode;
}
else
{
if(tmpnode->parent != NULL)
tmpnode->parent->right = tmpnode;
}

// Make tmpnode as the new root
root = tmpnode;

// Update the heights
Updateheight(root->left);
Updateheight(root->right);
Updateheight(root);
Updateheight(root->parent);

// Return the root node
return root;
}

// Function to handle Left Right Case
template
typename Tree::Node* Tree::LRR(Node* root)
{
root->left = RRR(root->left);
return LLR(root);
}

// Function to handle right left case
template
typename Tree::Node* Tree::RLR(Node* root)
{
root->right = LLR(root->right);
return RRR(root);
}

template
void Tree::printInorder(Node* root) const {
if (root == nullptr)
return;

// Traverse the left subtree
printInorder(root->left);

// Visit the root node
cout value right);
}

template
typename Tree::Node* Tree::Balance(Node* root)
{
int firstheight = 0;
int secondheight = 0;

if(root->left != NULL)
firstheight = root->left->height;

if(root->right != NULL)
secondheight = root->right->height;

if(abs(firstheight - secondheight) == 2)
{
if(firstheight < secondheight)
{
int rightheight1 = 0;
int rightheight2 = 0;

if(root->right->right != NULL)
rightheight2 = root->right->right->height;

if(root->right->left != NULL)
rightheight1 = root->right->left->height;

if(rightheight1 > rightheight2)
{
root = RLR(root);
}
else
{
root = RRR(root);
}
}
else
{
int leftheight1 = 0;
int leftheight2 = 0;

if (root->left->right != NULL)
leftheight2 = root->left->right->height;

if (root->left->left != NULL)
leftheight1 = root->left->left->height;

if (leftheight1 > leftheight2)
{
root = LLR(root);
}
else
{
root = LRR(root);
}
}
}

return root;
}

template
typename Tree::Node* Tree::Insert(Node* root, Node* parent, T value, bool &success)
{
if(root == NULL)
{
root = new Node(value);
success = true;

if (root == NULL)
cout left = NULL;
root->right = NULL;
root->parent = parent;
root->value = value;
}
}
else if (root->value > value)
{

root->left = Insert(root->left, root, value, success);

int firstheight = 0;
int secondheight = 0;

if(root->left != NULL)
firstheight = root->left->height;

if(root->right != NULL)
secondheight = root->right->height;

if(abs(firstheight - secondheight) == 2)
{
if(root->left != NULL && value < root->left->value)
{
root = LLR(root);
}
else
{
root = LRR(root);
}
}
}
else if (root->value < value)
{
root->right = Insert(root->right, root, value, success);

int firstheight = 0;
int secondheight = 0;

if (root->left != NULL)
firstheight = root->left->height;

if (root->right != NULL)
secondheight = root->right->height;

// Balance the Tree if the current node is not balanced
if(abs(firstheight - secondheight) == 2)
{
if (root->right != NULL && value < root->right->value)
{
root = RLR(root);
}
else
{
root = RRR(root);
}
}
}

Updateheight(root);

return root;
}

template
typename Tree::Node* Tree::Delete(Node* root, T value, bool &find)
{
if(root != NULL)
{
if (root->value == value)
{
find = true;

if(root->right == nullptr && root->left != nullptr)
{
if(root->parent != nullptr)
{
if(root->parent->value < root->value)
root->parent->right = root->left;
else
root->parent->left = root->left;

Updateheight(root->parent);
}

root->left->parent = root->parent;
root->left = Balance(root->left);

return root->left;
}
else if (root->left == nullptr && root->right != nullptr)
{
if(root->parent != nullptr)
{
if(root->parent->value < root->value)
root->parent->right = root->right;
else
root->parent->left = root->right;

Updateheight(root->parent);
}

root->right->parent = root->parent;
root->right = Balance(root->right);

return root->right;
}
else if(root->left == nullptr && root->right == nullptr)
{
if (root->parent->value < root->value)
{
root->parent->right = NULL;
}
else
{
root->parent->left = nullptr;
}

if(root->parent != nullptr)
Updateheight(root->parent);

root = nullptr;
return nullptr;
}
else
{
Node* tmpnode = root;
tmpnode = tmpnode->right;

while (tmpnode->left != nullptr)
{
tmpnode = tmpnode->left;
}

int val = tmpnode->value;

root->right = Delete(root->right, tmpnode->value, find);
root->value = val;
root = Balance(root);
}
}
else if (root->value < value)
{
root->right = Delete(root->right, value, find);
root = Balance(root);
}
else if(root->value > value)
{
root->left = Delete(root->left, value, find);
root = Balance(root);
}

if(root != NULL)
{
Updateheight(root);
}
}
else
{
// cout

Подробнее здесь: https://stackoverflow.com/questions/791 ... -recursion