Я работаю над проектом для школы, который включает в себя реализацию дерева AVL с использованием итеративной функции вставки, и у меня возникла проблема.
Я не уверен на 100%, что я не делаю, но моя программа не дает правильного вывода.
Вот что у меня есть для моей функции вставки:
bool AVLTree::insert(string ss, string na){
AVLNode* newNode = new AVLNode(ss, na);
updateHeight(newNode);
//Tree is empty, make the new Node the root of a new tree
if(getRoot() == nullptr){
root = newNode;
print();
return true;
}
//Tree is not empty
else{
AVLNode* checkPoint;
checkPoint = root;
while(checkPoint != nullptr){
//If the ssn is already in the tree
if(checkPoint->ssn.compare(newNode->ssn) == 0){
return false;
}
else if(checkPoint->ssn.compare(newNode->ssn) > 0){
if(checkPoint->left == nullptr){
break;
}
checkPoint = checkPoint->left;
}
else{
if(checkPoint->right == nullptr){
break;
}
checkPoint = checkPoint->right;
}
}
if(newNode->ssn.compare(checkPoint->ssn) < 0){
checkPoint->left = newNode;
}
else{
checkPoint->right = newNode;
}
updateHeight(checkPoint);
balance(root);
print();
return true;
}
Это моя функция, которую я придумал до сих пор, для моего проекта мне предоставили функцию баланса и updateHeight, которую я предоставлю здесь:
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;
И для высоты обновления:
void AVLTree::updateHeight(AVLNode* node){
int hl = height(node->left);
int hr = height(node->right);
node->height = (hl>hr ? hl : hr) + 1;
}
В основном моей задачей было реализовать функции вставки и удаления. Мой ввод для дерева avl в следующем порядке:
5, 8, 9, 3, 6, 7, 5
и мой вывод таков:
8
/ \
5 9
/ \
3 6
/ \
2 7
когда должно быть:
6
/ \
3 8
/ \ / \
2 5 7 9
Возвращаясь к моей функции вставки, я считаю, что проблема заключается в том, что я неправильно обновляю высоту каждый раз, когда вставляю узел. Программа отлично справляется с одинарными вращениями, но с двойными вращениями не работает. Любая помощь будет оценена по достоинству.
